13. Red-Black Trees 1

Definition
A red-black tree (RBT) is a binary search tree with one extra bit of storage per node: its colour can be either RED or BLACK.
Each node in a RBT contains at least the following fields:

1. color
2. key
3. left child pointer left()
4. right child pointer right()
5. parent pointer p()

Properties of red-black trees

1. Every node is colored only with either RED or BLACK.
2. The root node must be BLACK.
3. Every leaf (NIL) must be BLACK.
4. If a node is RED, then both its children are BLACK. This implies the red node must be an internal node.
5. Each path from a node x to any one of its descendant leaf nodes contains the same number of BLACK nodes. Note that the color of node x will be not counted.

6. The black height bh(x) of a node x in a RBT is the number of BLACK nodes on the path from node x down to a leaf, not counting x itself but counting the leaf.
   Lemma: A red-black tree with n internal nodes has height h at most 2 log(n + 1).
   The height of the red-black tree h is at most twice the black height of the root 2 · bh(root ), i.e., h ≤ 2 · bh(root ).
   The subtree rooted at any node x contains at least 2^bh(x) − 1 internal nodes.

Operations on a red-black tree

A red-black tree can support the operations SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR in time O(log n), where n is the number of internal nodes in the RBT.

INSERT and DELETE operations on a red-black tree might destroy its defining properties.
For this, we may have to change:

1. the color of some nodes in the RBT.
2. or the pointer structure of nodes in the RBT.

To maintain a balanced tree T, we change the pointer structure by using Rotations:
(1) The left Rotation;
(2) The right rotation.

Notice that the operation of either the left rotation or the right rotation only takes O(1) time by changing the pointers of several nodes, the binary search tree property of the resulting tree is still held.

示例

Insertion in a red-black tree

We use the TREE_INSERT procedure for binary search trees to insert a node x into a red-black tree T as if it were a binary search tree, and then colour the new inserted node RED.

2 violated situation:

1. The root might be RED (the original tree is empty, or the root is colored with red after a sequence of coloring changes on the tree).
2. A RED node might have a RED parent.

Solution

1. If the second violation occurs, we do some operations that either fix it or move it to a higher level, where a level near to the tree root is higher.
2. If it has not been fixed before we get to the tree root, the first violation occurs. We can fix the first violation by just setting the colour of the tree root to BLACK.

Suppose we have a RED node z which has a RED parent. There are 3 cases.

1. If case 1 occurs, the prescribed operations either fix the error or move it towards the root.
2. If cases 2 or 3 occur, the prescribed operations fix the tree always.
3. If the root is RED, making it BLACK fixes the tree.

示例

The time complexity is O(logn) as its largest height is 2log(n+1).
视频教学