Friday, 24 November 2017

Deletion from a Binary Search Tree

1. Deletion of a leaf node is easy.  For example, if a leaf node is left child, we set the left child field of its parent to NULL and free the node.  

2. The deletion of a non-leaf node that has only a single child is also easy.  We erase the node and then place the single child in the place of the erased node.  

3. When we delete a non-leaf node with two children, we replace the node with either the largest element in its left sub-tree or the smallest elements in its right sub-tree.  Then we proceed by deleting this replacing element from the sub-tree from which it was taken.


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput