Chapter 6 |

**1.**
It must be a complete binary tree (see complete binary tree) of exactly
*pow* (2, *n*) - 1 nodes.

If a red-black tree contains only red nodes, on the other hand, it cannot have more than one node, because of rule 1.

**2.**
If a red-black tree's root is red, then we can transform it into an
equivalent red-black tree with a black root simply by recoloring the
root. This cannot violate rule 1, because it does not introduce a red
node. It cannot violate rule 2 because it only affects the number of
black nodes along paths that pass through the root, and it affects all
of those paths equally, by increasing the number of black nodes along
them by one.

If, on the other hand, a red-black tree has a black root, we cannot in general recolor it to red, because this causes a violation of rule 1 if the root has a red child.

**1.**
C has a number of different namespaces. One of these is the namespace
that contains **struct**, **union**, and **enum** tags. Names of structure
members are in a namespace separate from this tag namespace, so it is
okay to give an **enum** and a structure member the same name. On the
other hand, it would be an error to give, e.g., a **struct** and an **enum**
the same name.

**1.**
Inserting a red node can sometimes be done without breaking any rules.
Inserting a black node will always break rule 2.

**1.**
We can't have *k* == 1, because then the new node would be the root,
and the root doesn't have a parent that could be red. We don't need
to rebalance *k* == 2, because the new node is a direct child of the
root, and the root is always black.

**2.**
Yes, it would, but if *d* has a red node as its root, case 1 will be
selected instead.

**1.**
If *p* has no left child, that is, it is a leaf, then obviously we
cannot swap colors. Now consider only the case where *p* does have a
non-null left child *x*. Clearly, *x* must be red, because otherwise
rule 2 would be violated at *p*. This means that *p* must be black to
avoid a rule 1 violation. So the deletion will eliminate a black
node, causing a rule 2 violation. This is exactly the sort of problem
that the rebalancing step is designed to deal with, so we can
rebalance starting from node *x*.

**2.**
There are two cases in this algorithm, which uses a new **struct** **avl_node** * variable named *x*. Regardless of which one is chosen,
*x* has the same meaning afterward: it is the node that replaced one
of the children of the node at top of stack, and may be `NULL` if the
node removed was a leaf.

Case 1: If one of *p*'s child pointers is `NULL`, then *p* can be
replaced by the other child, or by `NULL` if both children are `NULL`:

654. <Step 2: Delete item from RB tree, alternate version 654> =if(p->rb_link[0] ==NULL||p->rb_link[1] ==NULL)

{x=p->rb_link[0];if(x==NULL)x=p->rb_link[1]; }

Case 2: If both of *p*'s child pointers are non-null, then we find *p*'s
successor and replace *p*'s data by the successor's data, then delete
the successor instead:

655. <Step 2: Delete item from RB tree, alternate version 654> +=else

{structrb_node*y;pa[k] =p;da[k++] = 1;y=p->rb_link[1];while(y->rb_link[0] !=NULL)

{pa[k] =y;da[k++] = 0;y=y->rb_link[0]; }x=y->rb_link[1];p->rb_data=y->rb_data;p=y; }

In either case, we need to update the node above the deleted node to
point to *x*.

656. <Step 2: Delete item from RB tree, alternate version 654> +=pa[k- 1]->rb_link[da[k- 1]] =x;

**See also:**
[Cormen 1990], section 14.4.