14.2 How to augment a data structure
14.21
Show, by adding pointers to the nodes, how to support each of the dynamicset queries $\text{MINIMUM}$, $\text{MAXIMUM}$, $\text{SUCCESSOR}$, and $\text{PREDECESSOR}$ in $O(1)$worstcase time on an augmented orderstatistic tree. The asymptotic performance of other operations on orderstatistic 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.22
Can we maintain the blackheights of nodes in a redblack 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 blackheights as attributes in the nodes of a redblack tree without affecting the asymptotic performance of the redblack tree operations. We appeal to Theorem 14.1, because the blackheight of a node can be computed from the information at the node and its two children. Actually, the blackheight can be computed from just one child's information: the blackheight of a node is the blackheight 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 redblack trees.
Within the $\text{RBINSERTFIXUP}$ and $\text{RBDELETEFIXUP}$ procedures are color changes, each of which potentially cause $O(\lg n)$ blackheight changes. Let us show that the color changes of the fixup procedures cause only local blackheight changes and thus are constanttime operations. Assume that the blackheight of each node $x$ is kept in the attribute $x.bh$.
For $\text{RBINSERTFIXUP}$, 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 blackheight $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 blackheight changed is node $C$. To fix that, add $z.p.p.bh = z.p.p.bh + 1$ after line 7 in $\text{RBINSERTFIXUP}$.
 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 blackheight $k$, we see that even with color changes and rotations, the blackheights of nodes $A$, $B$, and $C$ remain the same $(k + 1)$.
Thus, $\text{RBINSERTFIXUP}$ maintains its original $O(\lg n)$ time.
For $\text{RBDELETEFIXUP}$, 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{RBDELETEFIXUP}$.
 This is a constanttime 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 blackheights 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 blackheights don't change.
 Add these two constanttime assignments in $\text{RBDELETEFIXUP}$ 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{RBDELETEFIXUP}$ maintains its original $O(\lg n)$ time.
Therefore, we conclude that blackheights of nodes can be maintained as attributes in redblack trees without affecting the asymptotic performance of redblack tree operations.
For the second part of the question, no, we cannot maintain node depths without affecting the asymptotic performance of redblack 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.23 $\star$
Let $\otimes$ be an associative binary operator, and let $a$ be an attribute maintained in each node of a redblack 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 orderstatistic trees.
$x.f = x.left.f \otimes x.a \otimes x.right.f$.
14.24 $\star$
We wish to augment redblack trees with an operation $\text{RBENUMERATE}(x, a, b)$ that outputs all the keys $k$ such that $a \le k \le b$ in a redblack tree rooted at $x$. Describe how to implement $\text{RBENUMERATE}$ 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 redblack tree.)
 $\Theta(\lg n)$: Find the smallest key that larger than or equal to $a$.
 $\Theta(m)$: Based on Exercise 14.21, find the $m$ successor.