Java Reference
In-Depth Information
Note:
Properties of a red-black tree
1.
The root is black.
2.
Every red node has a black parent.
3.
Any children of a red node are black; that is, a red node cannot have red children.
4.
Every path from the root to a leaf contains the same number of black nodes.
Question 21
Show that the red-black tree in Figure 27-29 satisfies the four properties just given.
Question 22
What red-black tree is equivalent to the 2-4 tree in Figure 27-25c?
Question 23
Show that the red-black tree that answers Question 22 satisfies the four
properties given previously.
Note:
Creating a red-black tree
In practice, you do not convert 2-4 trees into red-black trees. You create a red-black tree by
adding entries to an initially empty tree according to the steps described in the following
section. These steps consider both the balance of the tree and the color of its nodes.
Adding a leaf.
What color should we assign to a new node that we add to the tree? An addition to a
binary search tree always occurs at a leaf, so the same is true for a red-black tree. If we use black
for a new leaf, we will increase the number of black nodes on the paths to that leaf. This increase
violates the fourth property of a red-black tree. Thus, any new node must be red. However, do not
assume that all the leaves in a red-black tree are red. Adding or removing entries can change the
color of various nodes, including that of leaves added earlier.
Note:
The color of nodes added to a red-black tree
Adding an entry to a red-black tree results in a new red leaf. The color of this leaf can change
later when other entries are added or removed.
Consider some simple cases of adding to a red-black tree. A one-node red-black tree has one
black node, its root. Figure 27-30 shows two possibilities when we add a new entry
e
to this tree. In
each case, the new red node maintains the properties of a red-black tree, so it is legal.
FIGURE 27-30
The result of adding a new entry
e
to a one-node red-black tree
x
x
OR
e
e
