12.3 Insertion and deletion
12.3-1
Give a recursive version of the $\text{TREE-INSERT}$ procedure.
INSERT(p, x, z)
if x == NIL
z.p = p
if z.key < p.key
p.left = z
else p.right = z
else if z.key < x.key
INSERT(x, x.left, z)
else INSERT(x, x.right, z)
12.3-2
Suppose that we construct a binary search tree by repeatedly inserting distinct values into the tree. Argue that the number of nodes examined in searching for a value in the tree is one plus the number of nodes examined when the value was first inserted into the tree.
Number of nodes examined while searching also includes the node which is searched for, which isn't the case when we inserted it.
12.3-3
We can sort a given set of $n$ numbers by first building a binary search tree containing these numbers (using $\text{TREE-INSERT}$ repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worst-case and best-case running times for this sorting algorithm?
- The worst-case is that the tree formed has height $n$ because we were inserting them in already sorted order. This will result in a runtime of $\Theta(n^2)$.
- The best-case is that the tree formed is approximately balanced. This will mean that the height doesn't exceed $O(\lg n)$. Note that it can't have a smaller height, because a complete binary tree of height $h$ only has $\Theta(2^h)$ elements. This will result in a rutime of $O(n\lg n)$. We showed $\Omega(n\lg n)$ in exercise 12.1-5.
12.3-4
Is the operation of deletion "commutative" in the sense that deleting $x$ and then $y$ from a binary search tree leaves the same tree as deleting $y$ and then $x$? Argue why it is or give a counterexample.
No, giving the following courterexample.
-
Delete $A$ first, then delete $B$:
-
Delete $B$ first, then delete $A$:
12.3-5
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 $\text{SEARCH}$, $\text{INSERT}$, and $\text{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$. ($\textit{Hint:}$ You may wish to implement a subroutine that returns the parent of a node.)
We don't need to change $\text{SEARCH}$.
We have to implement $\text{PARENT}$, which facilitates us a lot.
PARENT(T, x)
if x == T.root
return NIL
y = TREE-MAXIMUM(x).succ
if y == NIL
y = T.root
else
if y.left == x
return y
y = y.left
while y.right != x
y = y.right
return y
INSERT(T, z)
y = NIL
x = T.root
pred = NIL
while x != NIL
y = x
if z.key < x.key
x = x.left
else
pred = x
x = x.right
if y == NIL
T.root = z
z.succ = NIL
else if z.key < y.key
y.left = z
z.succ = y
if pred != NIL
pred.succ = z
else
y.right = z
z.succ = y.succ
y.succ = z
We modify $\text{TRANSPLANT}$ a bit since we no longer have to keep the pointer of $p$.
TRANSPLANT(T, u, v)
p = PARENT(T, u)
if p == NIL
T.root = v
else if u == p.left
p.left = v
else
p.right = v
Also, we have to implement $\text{TREE-PREDECESSOR}$, which helps us easily find the predecessor in line 2 of $\text{DELETE}$.
TREE-PREDECESSOR(T, x)
if x.left != NIL
return TREE-MAXIMUM(x.left)
y = T.root
pred = NIL
while y != NIL
if y.key == x.key
break
if y.key < x.key
pred = y
y = y.right
else
y = y.left
return pred
DELETE(T, z)
pred = TREE-PREDECESSOR(T, z)
pred.succ = z.succ
if z.left == NIL
TRANSPLANT(T, z, z.right)
else if z.right == NIL
TRANSPLANT(T, z, z.left)
else
y = TREE-MIMIMUM(z.right)
if PARENT(T, y) != z
TRANSPLANT(T, y, y.right)
y.right = z.right
TRANSPLANT(T, z, y)
y.left = z.left
Therefore, all these five algorithms are still $O(h)$ despite the increase in the hidden constant factor.
12.3-6
When node $z$ in $\text{TREE-DELETE}$ has two children, we could choose node $y$ as its predecessor rather than its successor. What other changes to $\text{TREE-DELETE}$ would be necessary if we did so? Some have argued that a fair strategy, giving equal priority to predecessor and successor, yields better empirical performance. How might $\text{TREE-DELETE}$ be changed to implement such a fair strategy?
Update line 5 so that $y$ is set equal to $\text{TREE-MAXIMUM}(z.left)$ and lines 6-12 so that every $y.left$ and $z.left$ is replaced with $y.right$ and $z.right$ and vice versa.
To implement the fair strategy, we could randomly decide each time $\text{TREE-DELETE}$ is called whether or not to use the predecessor or successor.