Deleting Nodes from a Binary Search Tree: Cases and Implementation, Study notes of Computer Science

Download Deleting Nodes from a Binary Search Tree: Cases and Implementation and more Study notes Computer Science in PDF only on Docsity! Trees – 3 Deletion in BST -leaf node - node with one child - node with two children Deleting a node from a Binary Search Tree Deletion of a node is not so straightforward as is the case of insertion. It would depend on which particular node is being deleted. In fact, we note that there can be three separate cases and each case needs to be handled somewhat differently. The various cases are: (1) deletion of a leaf node, (2) deletion of an internal node with a single child (either a left or right subtree), (3) deletion of an internal node with two children (having both left subtree and right subtree. ) We’ll examine each case separately: Deletion of a leaf Node Since a leaf node has empty left and right subtrees, deleting a leaf node will render a tree with one less node but which remains a BST. This is illustrated below: A BST with a leaf node Still a BST Marked for deletion. 5 1 6 73 2 4 5 1 6 73 2 Deletion of a Node with two child nodes The last case of deletion from a BST is the most difficult to handle. There is no one-step operation that can be performed since the parent’s right or left reference cannot refer to both the children at the same time. There are basically two different approaches that can be used to handle this case: deletion via merging and deletion via copying We shall take up deletion via copying approach here,which essentially reduce to the following scenario: A deleted node with two children must be replaced by a value which is one of:  The largest value in the deleted node’s left subtree.  The smallest value in the deleted node’s right subtree. The above technique means that we need to be able to find, either the immediate predecessor or the immediate successor node to the node which is being deleted and replace the deleted node with this value. As an example, consider the following BST and suppose that we are deleting the value 18 from this tree. 43 59 18 67 13 32 63 72 25 Since the node containing 18 has two children it fits into this category for deletion. Its immediate predecessor is the rightmost node in its left subtree (which is 13), so our first choice would be to move 13 into the node currently occupied by 18, this is shown below: We could have, just as easily, found the immediate successor of 18 which is the leftmost node in its right subtree and put this value into the place currently occupied by 18. This case is shown below. 43 59 13 67 32 63 72 25 43 59 25 67 13 32 63 72 Notice that in both cases, the node which is physically deleted from the BST is a leaf node, and this is the trivial deletion case. Also notice, that while there is no fundamental difference is selecting the immediate predecessor or the immediate successor as the replacement for the deleted value, in reality there may be a difference. The example above, illustrates, to some degree, this difference which results from a potential difference in the heights of the two subtrees. In the example above, the immediate predecessor was the better choice since it was only one level away from the node to be deleted and therefore our search to find this node would be shorter than the search to find the immediate successor which was two levels away. While a few levels difference in the location of the immediate predecessor and immediate successor may not make much difference, it will be noticeable if there is a big difference between the two heights and obviously, the shorter the height the quicker the search and this is the way to go. Now L can be deleted from its old position. It is simply a leaf node. Its deletion results in the final tree Whose inorder traversal is C D E G J K L P R T U W Y C L D G K J LE T R P U W Y C L D G K JE T R P U W Y The node N can also be removed by replacing it with its immediate successor , the smallest node (left most node) of the right subtree and making the appropriate links. In this case node P becomes the right child of C Now the old value (leaf node P) can be deleted, resulting in the tree The subtree G becomes the left child of P and the subtree T becomes the right child of P. C P D G K J LE T R P U W Y C P D G K J LE T R U W Y In order traversal: C D E G J K L P R T U W Y. Here is a code to delete a node from a BST containing integer values. It returns the tree after deleting the node with value x struct treenode *delete_tree (int x, struct treenode* p) { //Deleting from an empty subtree if( p == NULL ) return p; else if( x< p->data ) p->left = delete_tree( x, p->left ); else if(x> p->data ) p->right = delete_tree( x, p->right ); //found the node to be deleted else if( p->left != NULL && p->right != NULL) { //the node has two children // Replace the node with minimum element in its right subtree p->data = findmin(p->right) -> data; // Now delete the old copy of the min. element p->right = delete_tree( p->data, p->right ); } else //node has One child OR both links are NULL { if(p->left != NULL) p = p->left; else p = p->right; } return p; }