Chapter 6

Section 6.1

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.

3. Yes and yes:

Section 6.2

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.

Section 6.4.2

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

Section 6.4.3

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.

Section 6.5.1

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];
  }

See also 655 and 656.

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 
  {
    struct rb_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.