17-4 The cost of restructuring red-black trees

There are four basic operations on red-black trees that perform structural modifications: node insertions, node deletions, rotations, and color changes. We have seen that $\text{RB-INSERT}$ and $\text{RB-DELETE}$ use only $O(1)$ rotations, node insertions, and node deletions to maintain the red-black properties, but they may make many more color changes.

a. Describe a legal red-black tree with $n$ nodes such that calling $\text{RB-INSERT}$ to add the $(n + 1)$st node causes $\Omega(\lg n)$ color changes. Then describe a legal red-black tree with $n$ nodes for which calling $\text{RB-DELETE}$ on a particular node causes $\Omega(\lg n)$ color changes.

Although the worst-case number of color changes per operation can be logarithmic, we shall prove that any sequence of $m$ $\text{RB-INSERT}$ and $\text{RB-DELETE}$ operations on an initially empty red-black tree causes $O(m)$ structural modifications in the worst case. Note that we count each color change as a structural modification.

b. Some of the cases handled by the main loop of the code of both $\text{RB-INSERT-FIXUP}$ and $\text{RB-DELETE-FIXUP}$ are terminating: once encountered, they cause the loop to terminate after a constant number of additional operations. For each of the cases of $\text{RB-INSERT-FIXUP}$ and $\text{RB-DELETE-FIXUP}$, specify which are terminating and which are not. ($\textit{Hint:}$ Look at Figures 13.5, 13.6, and 13.7.)

We shall first analyze the structural modifications when only insertions are performed. Let $T$ be a red-black tree, and define $\Phi(T)$ to be the number of red nodes in $T$. Assume that $1$ unit of potential can pay for the structural modifications performed by any of the three cases of $\text{RB-INSERT-FIXUP}$.

c. Let $T'$ be the result of applying Case 1 of $\text{RB-INSERT-FIXUP}$ to $T$. Argue that $\Phi(T') = \Phi(T) - 1$.

d. When we insert a node into a red-black tree using $\text{RB-INSERT}$, we can break the operation into three parts. List the structural modifications and potential changes resulting from lines 1–16 of $\text{RB-INSERT}$, from nonterminating cases of $\text{RB-INSERT-FIXUP}$, and from terminating cases of $\text{RB-INSERT-FIXUP}$.

e. Using part (d), argue that the amortized number of structural modifications performed by any call of $\text{RB-INSERT}$ is $O(1)$.

We now wish to prove that there are $O(m)$ structural modifications when there are both insertions and deletions. Let us define, for each node $x$,

$$ w(x) = \begin{cases} 0 & \text{ if } x \text{ is red}, \\ 1 & \text{ if } x \text{ is black and has no red children}, \\ 0 & \text{ if } x \text{ is black and has one red children}, \\ 2 & \text{ if } x \text{ is black and has two red children}. \end{cases} $$

Now we redefine the potential of a red-black tree $T$ as

$$\Phi(T) = \sum_{x \in T} w(x),$$

and let $T'$ be the tree that results from applying any nonterminating case of $\text{RB-INSERT-FIXUP}$ or $\text{RB-DELETE-FIXUP}$ to $T$.

f. Show that $\Phi(T') \le \Phi(T) - 1$ for all nonterminating cases of $\text{RB-INSERT-FIXUP}$. Argue that the amortized number of structural modifications performed by any call of $\text{RB-INSERT-FIXUP}$ is $O(1)$.

g. Show that $\Phi(T') \le \Phi(T) - 1$ for all nonterminating cases of $\text{RB-DELETE-FIXUP}$. Argue that the amortized number of structural modifications performed by any call of $\text{RB-DELETE-FIXUP}$ is $O(1)$.

h. Complete the proof that in the worst case, any sequence of $m$ $\text{RB-INSERT}$ and $\text{RB-DELETE}$ operations performs $O(m)$ structural modifications.

a. For $\text{RB-INSERT}$, consider a complete red-black tree in which the colors alternate between levels. That is, the root is black, the children of the root are red, the grandchildren of the root are black, the great-grandchildren of the root are red, and so on. When a node is inserted as a red child of one of the red leaves, then case 1 of $\text{RB-INSERT-FIXUP}$ occurs $(\lg(n + 1)) / 2$ times, so that there are $\Omega(\lg n)$ color changes to fix the colors of nodes on the path from the inserted node to the root.

For $\text{RB-DELETE}$, consider a complete red-black tree in which all nodes are black. If a leaf is deleted, then the double blackness will be pushed all the way up to the root, with a color change at each level (case 2 of $\text{RB-DELETE-FIXUP}$), for a total of $\Omega(\lg n)$ color changes.

b. All cases except for case 1 of $\text{RB-INSERT-FIXUP}$ and case 2 of $\text{RB-DELETE-FIXUP}$ are terminating.

c. Case 1 of $\text{RB-INSERT-FIXUP}$ reduces the number of red nodes by $1$. As Figure 13.5 shows, node $z$'s parent and uncle change from red to black, and $z$'s grandparent changes from black to red. Hence, $\Phi(T') = \Phi(T) - 1$.

d. Lines 1–16 of $\text{RB-INSERT}$ cause one node insertion and a unit increase in potential. The nonterminating case of $\text{RB-INSERT-FIXUP}$ (Case 1) makes three color changes and decreases the potential by $1$. The terminating cases of $\text{RB-INSERT-FIXUP}$ (cases 2 and 3) cause one rotation each and do not affect the potential. (Although case 3 makes color changes, the potential does not change. As Figure 13.6 shows, node $z$'s parent changes from red to black, and $z$'s grandparent changes from black to red.)

e. The number of structural modifications and amount of potential change resulting from lines 1–16 of $\text{RB-INSERT}$ and from the terminating cases of $\text{RB-INSERT-FIXUP}$ are $O(1)$, and so the amortized number of structural modifications of these parts is $O(1)$. The nonterminating case of $\text{RB-INSERT-FIXUP}$ may repeat $O(\lg n)$ times, but its amortized number of structural modifications is $0$, since by our assumption the unit decrease in the potential pays for the structural modifications needed. Therefore, the amortized number of structural modifications performed by $\text{RB-INSERT}$ is $O(1)$.

f. From Figure 13.5, we see that case 1 of $\text{RB-INSERT-FIXUP}$ makes the following changes to the tree:

  • Changes a black node with two red children (node $C$) to a red node, resulting in a potential change of $-2$.
  • Changes a red node (node $A$ in part (a) and node $B$ in part (b)) to a black node with one red child, resulting in no potential change.
  • Changes a red node (node $D$) to a black node with no red children, resulting in a potential change of $1$.

The total change in potential is $-1$, which pays for the structural modifications performed, and thus the amortized number of structural modifications in case 1 (the nonterminating case) is $0$. The terminating cases of $\text{RB-INSERT-FIXUP}$ cause $O(1)$ structural changes. Because $w(v)$ is based solely on node colors and the number of color changes caused by terminating cases is $O(1)$, the change in potential in terminating cases is $O(1)$. Hence, the amortized number of structural modifications in the terminating cases is $O(1)$. The overall amortized number of structural modifications in $\text{RB-INSERT}$, therefore, is $O(1)$.

g. Figure 13.7 shows that case 2 of $\text{RB-DELETE-FIXUP}$ makes the following changes to the tree:

  • Changes a black node with no red children (node $D$) to a red node, resulting in a potential change of $-1$.
  • If $B$ is red, then it loses a black child, with no effect on potential.
  • If $B$ is black, then it goes from having no red children to having one red child, resulting in a potential change of $-1$.

The total change in potential is either $-1$ or $-2$, depending on the color of $B$. In either case, one unit of potential pays for the structural modifications performed, and thus the amortized number of structural modifications in case 2 (the nonterminating case) is at most $0$. The terminating cases of $\text{RB-DELETE}$ cause $O(1)$ structural changes. Because $w(v)$ is based solely on node colors and the number of color changes caused by terminating cases is $O(1)$, the change in potential in terminating cases is $O(1)$. Hence, the amortized number of structural changes in the terminating cases is $O(1)$. The overall amortized number of structural modifications in $\text{RB-DELETE-FIXUP}$, therefore, is $O(1)$.

h. Since the amortized number structural modification in each operation is $O(1)$, the actual number of structural modifications for any sequence of $m$ $\text{RB-INSERT}$ and $\text{RB-DELETE}$ operations on an initially empty red-black tree is $O(m)$ in the worst case.