Page 128 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 6: Binary Search Tree and AVL Trees

which we normally draw: Notes

L 6

1 9

0 2 8 11

Finally, let us consider the only remaining case: how to delete a node having two subtrees. For
example, how to delete `6’? We’d like to do this with minimum amount of work and disruption
to the structure of the tree.
The standard solution is based on this idea: we leave the node containing `6’ exactly where it is,

but we get rid of the value 6 and find another value to store in the `6’ node. This value is taken
from a node below the `6’s node, and it is that node that is actually removed from the tree.
So, here is the plan. Starting with:

L 6

3 9

1 8 11

0 2

Erase 6, but keep its node:

L ?

3 9

1 8 11

0 2

Now, what value can we move into the vacated node and have a binary search tree? Well, here’s
how to figure it out. If we choose value X, then:

1. Everything in the left subtree must be smaller than X.
2. Everything in the right subtree must be bigger than X.
Let’s suppose we’re going to get X from the left subtree. (2) is guaranteed because everything in
the left subtree is smaller than everything in the right subtree. What about (1)? If X is coming from
the left subtree, (1) says that there is a unique choice for X - we must choose X to be the largest
value in the left subtree. In our example, 3 is the largest value in the left subtree. So if we put 3 in
the vacated node and delete it from its current position we will have a BST with 6 deleted.

LOVELY PROFESSIONAL UNIVERSITY 123