DinS          Written on 2017/4/29

This is the second part of Binary Search Tree. Read the first part here.

6. Pred and Succ

Sometimes we want to locate the predecessor and successor of a given node. By predecessor I mean the node whose key is smaller than the given node but bigger than all other nodes smaller than the given node. Successor works the same way. It’s the smallest node among bigger nodes.

Given a node k, to locate the pred of k there’re two cases.

(1) if k’s left subtree is nonempty, return the max key in the left subtree.

(2) otherwise follow parent pointers until you get to a key that is smaller than k. This happens the first time you turn left.

For example, given the node 13, the pred of it belongs to the first case. We first go to the left subtree of node 13 and go along the right child until we can’t go anywhere. The route is as follows:

Another example, given the node 6, the pred of it belongs to the second case. We first go to the parent of 6, which is 7. Since 7 is bigger than 6, we keep on going and reach 13. The same story goes on and we reach 5. 5 is smaller than 6 and we get the pred of 6. Note that from 6 to 13 we always turned right. From 13 to 5 we turned left.

Succ is similar, you just do some replacing and done.

Given a node k, to locate the succ of k there’re two cases.

(1) if k’s right subtree is nonempty, return the min key in the right subtree.

(2) otherwise follow parent pointers until you get to a key that is bigger than k. This happens the first time you turn right.

For example, given the node 5, the succ of it belongs to the first case. We first go to the right subtree and go along the left child to get the min key.

Another example, given the node 10, the succ of it belongs to the second case. We keep on going through the parent to get 13 which is bigger than 10.

To locate pred or succ, we may need to go from bottom to top. This takes O(height) time.

7. Delete

Deletion is much harder than all previous operations because it may break the Property and we need to do something to fix it up.

To delete the node k in a BST, we first search for it and locate the node. The there’re three cases.

(1) Easy case: node k has no children. Simply delete k.

(2) Medium case: node k has one child. “Splice out” k, which means the child assumes the position previously held by k.

(3) Hard case: node k has two children. Locate k’s predecessor l and swap k and l. Because we know k has two children, to locate pred belongs to the first case. As a result we know that l is the max key in the left tree. That means after swapping k has at most one child. Now that we have reduced the hard case to the easy or medium case, we can apply the same method to solve the problem.

Pseudo codes:

|    deleteBST(BST, target)

|    {

|             k = BinSearchBST(target)

|             l = pred(k)

|             if (!hasChild(k)) delete(k)

|             elseif (hasOneChild(k))

|             {

|                       rewire(k->parent, k->lc || k->rc)

|                       delete(k)

|             }

|             else

|             {

|                       swap(k, l)

|                       if (hasOneChild(k)) rewire(k->parent, k->lc || k->rc)

|                       delete(k)

|             }

|    }

e.g. Easy case.

We want to delete node 10 in this BST.

Since 10 has no children, we simply delete it. Property maintained.

e.g. Medium case.

We want to delete node 7 in this BST.

Since 7 has one child, we’ll first rewire its child 10 to its parent 13. Looks like this.

Now node 7 becomes isolated. We just delete it. Property maintained.

e.g. Hard case.

We want to delete node 13 in this BST.

We find that 13 has two children. In this case we find its pred which is 10. And we swap these two nodes.

At this time Property is broken, but don’t worry. Now than 13 becomes the leaf node, we simply delete it.

After that we find Property is maintained now.

As for the efficiency of deletion, the real deleting operation only takes O(1). Search operation takes O(height). Pred takes O(height). In conclusion deletion takes O(height) time.

8. Rotations

If two B.S.T. have the same in-order traversal, we say the two trees are equivalent. This is a very interesting conclusion because this means that two B.S.T. which are different in topological structure are actually the same tree.

This is an example.

Here comes rotation. The idea is we can locally rewire subtrees at a node to get the same tree in O(1) time. Depending on specific conditions, rotations are divided into two kinds.

(1) Left rotation, or zag

The nodes x and y and subtrees A, B and C form a B.S.T. The left B.S.T. and the right B.S.T. have the same in-order traversal, so we say they are equivalent. Visually, it is as if we left rotate the node x to get the right tree.

(2) Right rotation, or zig

As is clear from the pictures, right rotation is the opposite operation of left rotation.

Rotation is a key technique for balanced binary search tree. It’s used to rebalance the tree after insertion and deletion.

9. Can we do better?

All operations for B.S.T. depend on its height. However, Search Tree Property can’t guarantee the height of tree. In the worst case the height of tree can become O(n). As a concrete example, if we insert {0,1,2,3,4}, we’ll get this tree.

This is not a tree but a list!

B.S.T. is a good idea, but if we can’t control the height, we’ll never get a high-performance data structure. Luckily, many talented people have devoted their energy to this problem and come up with many ways to control the height of tree. These are called balanced binary search tree. Some famous versions are AVL, splay tree and red-black tree. We’ll discuss them later.