How to write remove function in the Binary Search Tree? I have no idea how to do

ID: 665542 • Letter: H

Question

How to write remove function in the Binary Search Tree?

I have no idea how to do with origAncestor.

TYPE _removeLeftMost(Node* curr, Node* parent, Node* origAncestor)
{
   /* FIXME you will write this function */
   TYPE removeThisVar;
   return removeThisVar;
}

/* This function is used to remove a node from a subtree of the BST

   param: curr       The root of the subtree we are currently examining for the value
   param: val       The value to be removed from the subtree
   post: a node containing val has been removed from the tree and freed
   ret: the node where we currently reside in the tree.
           Note that this function uses recursion to put the tree back together as stack
           frames are removed.
*/
Node* _removeNodeFromSubtree(Node* curr, TYPE val)
{

}

--------------------------------------------------------

Full BST.c

--------------------------------------------------------

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "assert.h"
#include "type.h"
#include "BST.h"

/* ************************************************************************
Helper Functions
************************************************************************ */
/* This function allocates a node on the heap for use in the tree datastructure.

   param: val       value to store in the newly created node
   post:   the newly created node is allocated, initialized, and returned.
   ret: a Node, allocated on the heap, storing the argument value
*/
Node* _createNode(TYPE val)
{
   Node* newNode = (Node*) malloc(sizeof(Node));
   assert(newNode!=0);
   newNode->value = val;
   newNode->left = newNode->right =0;
   return newNode;

}

/* This function compares two tasks. Note that this function does NOT use
   TYPE. This is because if we change TYPE, we will get a compile error on the
   _compare function, making us remember to write a new one for that type.

   param: left, right       Items to be compared
   ret:   -1 if left < right
           1 if left > right
           0 otherwise
*/
int _compare(Task left, Task right)
{
   if(left.priority < right.priority)
       return -1;
   else if(left.priority > right.priority)
       return 1;
   return 0;
}

/* ************************************************************************
   Binary Search Tree Basic Functions
************************************************************************ */
/* This function can be used to initialize the data fields in the tree.

   param: tree       The tree to be initialized
   post: tree's datafields are all initialized.
*/
void initBST(BST* tree)
{
   tree->root = NULL;
   tree->size = 0;
}

/* Allocate and initialize a binary search tree.

   post: the newly created tree is allocated, initialized, and returned
   ret:   a newly created tree, allocated on the heap.
*/
BST* newBST()
{
   BST* tree = (BST*)malloc(sizeof(BST));
   assert(tree);

   initBST(tree);
   return tree;
}

/* Helper function used to free a subtree of the BST rooted at a particular node.

   param: root       Root of the subtree to be freed
   pre:   root is in the tree
   post:   all memory in the underlying tree structure is freed
*/
void _freeSubTreeBST(Node* root)
{
   if(!root)
       return;
   _freeSubTreeBST(root->left);
   _freeSubTreeBST(root->right);
   free(root);
}

/* This function will free all the nodes in the argument tree. To be used with init.

   param: tree       Tree to have its nodes freed
   post:   tree has had its nodes freed
   post:   tree has had its datafields cleared
*/
void freeBST(BST* tree)
{
   _freeSubTreeBST(tree->root);
   tree->size = 0;
   tree->root = 0;
}

/* This function will free all the nodes in the argument tree IN ADDITION to freeing the
   datastructure pointer provided as well.

   param: tree       Tree to have its nodes freed and be freed
   post:   tree has had its nodes freed
   post:   tree has had its datafields cleared
   post:   tree has been freed
*/
void deleteBST(BST* tree)
{
   freeBST(tree);
   free(tree);
}

/* Helper function used to compute the height of a subtree rooted at a particular node.

   param: root       Root of the subtree to compute the height of
   ret:   The height of the subtree rooted at root
*/
int _heightOfSubTree(Node* root)
{
   if(root==NULL)
   {
       return 0;
   }
   else
   {
       int leftDepth =_heightOfSubTree(root->left);
       int rightDepth = _heightOfSubTree(root->right);

       if (leftDepth > rightDepth)
       {
           return(leftDepth+1);
       }
       else
       {
           return(rightDepth+1);
       }
   }
}

/* This function computes the height of an argument BST

   param:   tree   BST to have its height computed
   ret:   the height of the argument tree
*/
int heightBST(BST* tree)
{
   return _heightOfSubTree(tree->root);
}

/* Helper function which stores a subtree rooted at root into the argument array.

   param: root       Root of the subtree to be stored in the array
   param: index   Index where the root should reside in the argument array
   param: levelOrder   Array where the tree is to be stored
   post: levelOrder has the subtree rooted at root stored inside it.
*/
void _storeInArray(Node* root, int index, Node** levelOrder)
{
   if (!root)
       return;

   levelOrder[index] = root;
   _storeInArray(root->left, 2*index + 1, levelOrder);
   _storeInArray(root->right, 2*index + 2, levelOrder);
}

/* Prints a BST to the console using a nice formatting.

   param: tree       Tree to be printed to the console
   post:   tree has been printed to the console

   IMPORTANT NOTE! some input to this function pay cause exponential memory to be consumed
   as a result of the tree in array storage scheme.
*/
void printBST(BST* tree)
{
   int height = heightBST(tree);
   int levelOrderSize = pow(2, height+1)-1;
   int i, j, depth, lastDepth;
   int leftSpace;

   Node** levelOrder = (Node**)malloc(levelOrderSize*sizeof(Node*));
   for(i = 0; i < levelOrderSize; ++i)
       levelOrder[i] = NULL;
   _storeInArray(tree->root, 0, levelOrder);

   printf("***[ Size: %d Height: %d ]", tree->size, heightBST(tree));

   lastDepth = -1;
   leftSpace = 0;
   for(i = 0; i <= height; ++i)
       leftSpace = leftSpace * 2 + 1;
   for(i = 0; i < levelOrderSize; ++i)
   {
       depth = log(i+1)/log(2);
       if(lastDepth != depth)
       {
           leftSpace /= 2;
           printf(" ");
           for(j = 0; j < leftSpace; ++j)
               printf(" ");
       }
       else
           for(j = 0; j < leftSpace * 2 + 1; ++j)
               printf(" ");

       if(levelOrder[i])
           printf("%d", levelOrder[i]->val.priority);
       else
           printf("??");
       lastDepth = depth;
   }
   printf(" ");
   free(levelOrder);
}

/* ************************************************************************
Bag Interface Functions (and Helpers)
************************************************************************ */
/* Add a node to the subtree rooted at the argument node

   param: curr       Root of the subtree where the node should be added.
   param: val       value to store in the new node when it is added
   post: a node is allocated storing val, which has been added to the tree
   ret: the node where we currently reside in the tree. Note that
           this function is recursive, so as the function returns, we will
           connect the tree together.
*/
Node* _addNodeToSubtree(Node* curr, TYPE val)
{
if(curr==0)
   {
       return _createNode(val);
   )
   if (val<curr->value)
   {
       curr->left = _addNodeToSubtree(curr->left,val);
   }
   else if(val->curr->value)
   {
       curr->right= _addNodeToSubtree(curr->right,val);
   }
   return curr;
}

/* Adds a node to the BST

   param: tree       BST to have a node added to it
   param: val       value to store in the new node
   post: a node, allocated on the heap, has been added to the BST storing val
*/
void addBST(BST* tree, TYPE val)
{
   tree->root = _addNodeToSubtree(tree->root, val);
   tree->size++;
}

/* Helper function which can be used to determine if a particular value is
   present in the subtree rooted at the argument node.

   param: curr       Root of the subtree to search for the value
   param: val       value for which to search the the subtree
   ret: 1 if the value is in the subtree, 0 otherwise
*/
int _containsSubTree(Node* curr, TYPE val)
{
   while(curr!= NULL)
   {
       if(_compare(val,curr->val) ==0)
       {
           return 1;
       }
       else if(_compare(val,curr->val)==1)
       {
           curr = curr->right;
       }
       else if(_compare(val,curr->val)==-1)
       {
           curr= curr->left;
       }
       return 0;
}

/* This function can be used to determine if a particular value is present in the BST.

   param: tree       BST to search for the argument value
   param: val       Value to search for in the BST
   ret: 1 if the value is in the BST, 0 otherwise
*/
int containsBST(BST* tree, TYPE val)
{
   return _containsSubTree(tree->root, val);
}

/* This function is used to remove and deallocate the leftmost descendent of the argument node

   param: curr       The node whose leftmost descendent we wish to find
   param: parent   curr's parent, included to make the operation easier to perform
   param: origAncestor       the node on which the original leftmost call was given
   post:   the leftmost descendent of curr is removed from the tree and freed
   ret:   the value stored in the leftmost descendent of curr
*/
TYPE _removeLeftMost(Node* curr, Node* parent, Node* origAncestor)
{
   /* FIXME you will write this function */
   TYPE removeThisVar;
   return removeThisVar;
}

/* This function is used to remove a node from a subtree of the BST

/* This function is used to remove a node from the BST, if present.

   param: tree       The tree to search for the argument value
   param: val       the value to be removed from the tree.
   post: if val is present in any of the nodes, it has been removed.
           if not, nothing has happened
*/
void removeBST(BST* tree, TYPE val)
{
   if(containsBST(tree, val))
   {
       tree->root = _removeNodeFromSubtree(tree->root, val);
       tree->size--;
   }
}

---------------------------------------------

BST.h

---------------------------------------------

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "assert.h"
#include "type.h"
#include "BST.h"

}

/* Allocate and initialize a binary search tree.

/* Helper function used to free a subtree of the BST rooted at a particular node.

/* This function will free all the nodes in the argument tree. To be used with init.

/* This function computes the height of an argument BST

   param:   tree   BST to have its height computed
   ret:   the height of the argument tree
*/
int heightBST(BST* tree)
{
   return _heightOfSubTree(tree->root);
}

/* Helper function which stores a subtree rooted at root into the argument array.

/* Prints a BST to the console using a nice formatting.

       if(levelOrder[i])
           printf("%d", levelOrder[i]->val.priority);
       else
           printf("??");
       lastDepth = depth;
   }
   printf(" ");
   free(levelOrder);
}

/* Adds a node to the BST

/* This function can be used to determine if a particular value is present in the BST.

/* This function is used to remove and deallocate the leftmost descendent of the argument node

/* This function is used to remove a node from a subtree of the BST

/* This function is used to remove a node from the BST, if present.

--------------------------------------------------------------

Explanation / Answer

Binary Search Tree:

A binary search tree (BST) is a binary tree, where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right subtree.

Performing Delete Operation:

When ever we want to delete a node, there may be there possibilities arise.

i) To bee deleted is a leaf: We simply remove from the tree as follows.

ii) To be deleted Node has only one child: We just copy the child to the node and delete the child

iii) To be deleted Node has two children: Now find inorder successor of the node, then copy contents of the inorder successor to the node and delete the inorder successor. Remember that inorder predecessor can also be used.

Program for Binary Search Tree: Deletion Operation

// C program to demonstrate delete/remove operation in Binary Search Tree
#include<stdio.h>
#include<stdlib.h>

struct node
{
int key;
struct node *left, *right;
};

// Utility function for creating a new BST node
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// Utility function for inorder traversal of BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}

// Utility function for insert a new node with given key in BST
struct node* insert(struct node* node, int key)
{
if (node == NULL) return newNode(key); // If the tree is empty, return a new node

if (key < node->key) // Otherwise, recur down the tree
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);

return node; // return the (unchanged) node pointer
}

/* Given a non-empty binary search tree, return the node with minimum key value found in the tree.
Remember that the entire tree does not need to be searched. */
struct node * minValueNode(struct node* node)
{
struct node* current = node;

/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;

return current;
}

/* Given a binary search tree and a key, this function deletes the key and returns the new root */
struct node* deleteNode(struct node* root, int key)
{
if (root == NULL) return root; // base case

// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if (key < root->key)
root->left = deleteNode(root->left, key);

// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if (key > root->key)
root->right = deleteNode(root->right, key);

// if key is same as root's key, then This is the node
// to be deleted
else
{
if (root->left == NULL) // node with only one child or no child
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}

// node with two children: Get the inorder successor (smallest
// in the right subtree)
struct node* temp = minValueNode(root->right);

// Copy the inorder successor's content to this node
root->key = temp->key;

// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}

int main()
{
/* Let us create following BST
54
/
32 76
/ /
21 43 65 87 */
struct node *root = NULL;
root = insert(root, 54);
root = insert(root, 32);
root = insert(root, 21);
root = insert(root, 43);
root = insert(root, 76);
root = insert(root, 65);
root = insert(root, 87);

printf("Inorder traversal of the given tree is: ");
inorder(root);

printf(" Delete 21 ");
root = deleteNode(root, 21);
printf("Inorder traversal of Newly modified tree is: ");
inorder(root);

printf(" Delete 32 ");
root = deleteNode(root, 32);
printf("Inorder traversal of Newly modified tree is: ");
inorder(root);

printf(" Delete 54 ");
root = deleteNode(root, 54);
printf("Inorder traversal of the modified tree ");
inorder(root);
printf(" ");
   return 0;
}

OUTPUT:

Inorder traversal of the given tree is:
21 32 43 54 65 76 87
Delete 21
Inorder traversal of Newly modified tree is:
31 43 54 65 76 87
Delete 32
Inorder traversal of Newly modified tree is:
43 54 65 76 87
Delete 54
Inorder traversal of Newly modified tree is:
43 64 76 87.

Navigate

How to write programs in sql for the following question: 1. how to show columns

How to write remove function in the Binary Search Tree? I have no idea how to do

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

How to write remove function in the Binary Search Tree? I have no idea how to do

Question

Explanation / Answer

Related Questions

Navigate