Skip to content

14.2 How to augment a data structure

14.2-1

Show, by adding pointers to the nodes, how to support each of the dynamic-set queries $\text{MINIMUM}$, $\text{MAXIMUM}$, $\text{SUCCESSOR}$, and $\text{PREDECESSOR}$ in $O(1)$worstcase time on an augmented order-statistic tree. The asymptotic performance of other operations on order-statistic trees should not be affected.

  • MINIMUM: A pointer points to the minimum node, if the node is being deleted, move the pointer to its successor.
  • MAXIMUM: Similar to $\text{MINIMUM}$.
  • SUCCESSOR: Every node records its successor, the insertion and deletion is similar to that in linked list.
  • PREDECESSOR: Similar to $\text{MAXIMUM}$.

14.2-2

Can we maintain the black-heights of nodes in a red-black tree as attributes in the nodes of the tree without affecting the asymptotic performance of any of the redblack tree operations? Show how, or argue why not. How about maintaining the depths of nodes?

Yes, we can maintain black-heights as attributes in the nodes of a red-black tree without affecting the asymptotic performance of the red-black tree operations. We appeal to Theorem 14.1, because the black-height of a node can be computed from the information at the node and its two children. Actually, the black-height can be computed from just one child's information: the black-height of a node is the black-height of a red child, or the black height of a black child plus one. The second child does not need to be checked because of property 5 of red-black trees.

Within the $\text{RB-INSERT-FIXUP}$ and $\text{RB-DELETE-FIXUP}$ procedures are color changes, each of which potentially cause $O(\lg n)$ black-height changes. Let us show that the color changes of the fixup procedures cause only local black-height changes and thus are constant-time operations. Assume that the black-height of each node $x$ is kept in the attribute $x.bh$.

For $\text{RB-INSERT-FIXUP}$, there are 3 cases to examine.

Case 1: $z$'s uncle is red.

  • Before color changes, suppose that all subtrees $\alpha$, $\beta$, $\gamma$, $\delta$, $\epsilon$ have the same black-height $k$ with a black root, so that nodes $A$, $B$, $C$, and $D$ have blackheights of $k + 1$.
  • After color changes, the only node whose black-height changed is node $C$. To fix that, add $z.p.p.bh = z.p.p.bh + 1$ after line 7 in $\text{RB-INSERT-FIXUP}$.
  • Since the number of black nodes between $z.p.p$ and $z$ remains the same, nodes above $z.p.p$ are not affected by the color change.

Case 2: $z$'s uncle $y$ is black, and $z$ is a right child.
Case 3: $z$'s uncle $y$ is black, and $z$ is a left child.

  • With subtrees $\alpha$, $\beta$, $\gamma$, $\delta$, $\epsilon$ of black-height $k$, we see that even with color changes and rotations, the black-heights of nodes $A$, $B$, and $C$ remain the same $(k + 1)$.

Thus, $\text{RB-INSERT-FIXUP}$ maintains its original $O(\lg n)$ time.
For $\text{RB-DELETE-FIXUP}$, there are 4 cases to examine.

Case 1: $x$'s sibling $w$ is red.

  • Even though case 1 changes colors of nodes and does a rotation, blackheights are not changed.
  • Case 1 changes the structure of the tree, but waits for cases 2, 3, and 4 to deal with the "extra black" on $x$.

Case 2: $x$'s sibling $w$ is black, and both of $w$'s children are black.

  • $w$ is colored red, and $x$'s "extra" black is moved up to $x.p$.
  • Now we can add $x.p.bh = x.bh$ after line 10 in $\text{RB-DELETE-FIXUP}$.
  • This is a constant-time update. Then, keep looping to deal with the extra black on $x.p$.

Case 3: $x$'s sibling w is black, $w$'s left child is red, and $w$'s right child is black.

  • Regardless of the color changes and rotation of this case, the black-heights don't change.
  • Case 3 just sets up the structure of the tree, so it can fall correctly into case 4.

Case 4: $x$'s sibling $w$ is black, and $w$'s right child is red.

  • Nodes $A$, $C$, and $E$ keep the same subtrees, so their black-heights don't change.
  • Add these two constant-time assignments in $\text{RB-DELETE-FIXUP}$ after line 20:
  • $$ \begin{aligned} x.p.bh & = x.bh + 1 \\ x.p.p.bh & = x.p.bh + 1 \end{aligned} $$

  • The extra black is taken care of. Loop terminates.

Thus, $\text{RB-DELETE-FIXUP}$ maintains its original $O(\lg n)$ time.

Therefore, we conclude that black-heights of nodes can be maintained as attributes in red-black trees without affecting the asymptotic performance of red-black tree operations.

For the second part of the question, no, we cannot maintain node depths without affecting the asymptotic performance of red-black tree operations. The depth of a node depends on the depth of its parent. When the depth of a node changes, the depths of all nodes below it in the tree must be updated. Updating the root node causes $n - 1$ other nodes to be updated, which would mean that operations on the tree that change node depths might not run in $O(n\lg n)$ time.

14.2-3 $\star$

Let $\otimes$ be an associative binary operator, and let $a$ be an attribute maintained in each node of a red-black tree. Suppose that we want to include in each node $x$ an additional attribute $f$ such that $x.f = x_1.a \otimes x_2.a \otimes \cdots \otimes x_m.a$, where $x_1, x_2, \ldots ,x_m$ is the inorder listing of nodes in the subtree rooted at $x$. Show how to update the $f$ attributes in $O(1)$ time after a rotation. Modify your argument slightly to apply it to the $size$ attributes in order-statistic trees.

$x.f = x.left.f \otimes x.a \otimes x.right.f$.

14.2-4 $\star$

We wish to augment red-black trees with an operation $\text{RB-ENUMERATE}(x, a, b)$ that outputs all the keys $k$ such that $a \le k \le b$ in a red-black tree rooted at $x$. Describe how to implement $\text{RB-ENUMERATE}$ in $\Theta(m+\lg n)$ time, where $m$ is the number of keys that are output and $n$ is the number of internal nodes in the tree. ($\textit{Hint:}$ You do not need to add new attributes to the red-black tree.)

  • $\Theta(\lg n)$: Find the smallest key that larger than or equal to $a$.
  • $\Theta(m)$: Based on Exercise 14.2-1, find the $m$ successor.