12.3 Insertion and deletion

12.3-1

Give a recursive version of the $\text{TREE-INSERT}$ procedure.

1
2
3
4
RECURSIVE-TREE-INSERT(T, z)
    if T.root == NIL
        T.root = z
    else INSERT(NIL, T.root, z)
1
2
3
4
5
6
7
8
9
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$:

    1
    2
    3
    4
    5
      A        C        C
     / \      / \        \
    B   D    B   D        D
       /
      C
    
  • Delete $B$ first, then delete $A$:

    1
    2
    3
    4
    5
      A        A        D
     / \        \      /
    B   D        D    C
       /        /
      C        C
    

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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$.

1
2
3
4
5
6
7
8
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}$.

1
2
3
4
5
6
7
8
TREE-PREDECESSOR(T, x)
    if x.left != NIL
        return TREE-MAXIMUM(x.left)
    y = PARENT(T, x)
    while y != NIL and x == y.left
        x = y
        y = PARENT(T, y)
    return y
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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)$.

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.