Deletion in BST:
1) Node to be deleted is leaf:
Simply remove from the tree.
80 80
/ \ delete(50) / \
60 100 ---------> 60 100
/ \ / \ \ / \
50 70 90 110 70 90 110
2) Node to be deleted has only one child:
Swap the child to the node and delete the new child.
80 80
/ \ delete(60) / \
60 100 ---------> 70 100
\ / \ / \
70 90 110 90 110
3) Node to be deleted has both children:
A. Find inorder successor of the node.
B. Copy contents of the inorder successor to the node and delete the inorder successor.
(Inorder predecessor can also be used).
80 90
/ \ delete(80) / \
70 100 ---------> 70 100
/ \ \
90 110 110
Note: Inorder successor is needed only when right child is not empty.
Inorder successor can be obtained as the minimum value in right sub tree of the node.
No comments:
Post a Comment