Suppose that instead of each node \(x\) keeping the attribute \(x.p\), pointing to \(x\)’s parent, it keeps \(x.succ\), pointing to \(x\)’s successor. Give pseudocode for SEARCH, INSERT, and DELETE on a binary search tree \(T\) using this representation. These procedures should operate in time \(O(h)\), where \(h\) is the height of the tree \(T\). (Hint: You may wish to implement a subroutine that returns the parent of a node.)
First we implement the PARENT procedure which will be useful in further procedures.
PARENT(T, x)
1 if T.root == x:
2 return NIL
3 y = TREE-MAXIMUM(x).succ
4 if y == NIL:
5 y = T.root
6 else:
7 if y.left == x:
8 return y
9 y = y.left
10 while y.right ≠ x:
11 y = y.right
12 return y
TREE-SEARCH(x, k) does not need to change since it does not use the parent property on any nodes. TREE-INSERT, however, needs to track the predecessor of the node being inserted so its successor value can be properly updated. Othewise the structure of this procedure remains lagely unchanged.
TREE-INSERT(T, z)
1 y = NIL
2 x = T.root
3 pred = NIL
4 while x ≠ NIL:
5 y = x
6 if z.key < x.key:
7 x = x.left
8 else:
9 pred = x
10 x = x.right
11 if y = = NIL:
12 T.root = z
13 z.succ = NIL
14 else if z.key < y.key:
15 y.left = z
16 z.succ = y
17 if pred ≠ NIL:
18 pred.succ = z
19 else:
20 y.right = z
21 z.succ = y.succ
22 y.succ = z
The helpful TRANSPLANT procuedre needs to be modified since the existing version relives on accessing the parent attribute.
TRANSPLANT(T, u, v)
1 p = PARENT(T, u)
2 if p == NIL:
3 T.root = v
4 else if u == p.left
5 p.left = v
6 else:
7 p.right = v
In order to build our DELETE procedure, we need a modified version of TREE-PREDECESSOR (See Excercise 12.2-3).
TREE-PREDECESSOR(T, x)
1 if x.left ≠ NIL:
2 return TREE-MAXIMUM(x.left)
3 y = T.root
4 pred = NIL
5 while y ≠ NIL:
6 if y.key == x.key:
7 break
8 if y.key < x.key:
9 pred = y
10 y = y.right
11 else:
12 y = y.left
13 return pred
We now have all the necessary pieces to construct a version of the DELETE procedure that respects the constaints of this problem.
DELETE(T, z)
1 pred = TREE-PREDECESSOR(T, z)
2 pred.succ = z.succ
3 if z.left == NIL:
4 TRANSPLANT(T, z, z.right)
5 else if z.right == NIL:
6 TRANSPLANT(T, z, z.left)
7 else:
8 y = TREE-MINIMUM(z.right)
9 if PARENT(T, y) ≠ z:
10 TRANSPLANT(T, y, y.right)
11 y.right = z.right
12 TRANSPLANT(T, z, y)
13 y.left = z.left
These changes do not increase the procedure’s runtimes by more than a constant factor and therefore they are still all \(O(h)\).