Page 129 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Here it is:

L 3

9

1 8 11

0 2

So our general algorithm is: to delete N, if it has two subtrees, replace the value in N with the
largest value in its left subtree and then delete the node with the largest value from its left
subtree.

Note The largest value in the left subtree will never have two subtrees. Why? Because if
it’s the largest value it cannot have a right subtree.

Finally, there is nothing special about the left subtree. We could do the same thing with the right
subtree: just use the smallest value in the right subtree.

To delete a node from a binary search tree the method to be used depends on whether a node to
be deleted has one child, two children, or has no child.

6.4.1 Deletion of a Node with Two Children

If the node to be deleted has two children; then the value is replaced by the smallest value in
the right sub tree or the largest key value in the left sub tree; subsequently the empty node is
recursively deleted. Consider the BST in Figure 6.2.

Figure 6.2 Binary search tree

10

6 12

5 9
11

4 7

8

If the node 6 is to be deleted then first its value is replaced by smallest value in its right subtree

i.e. by 7. So we will have Figure 6.3.

124 LOVELY PROFESSIONAL UNIVERSITY