Red Black Trees (under develpment)

Contents Under Development…

Todo

Read these sources to discover the clearest and look for those that mention how 2-3 and 2-3-4 tree relate to red-balck trees. Perhaps update existing tree related .rst files with something particularly relevant.

A red-black tree is a binary tree representation of a 2-3-4 tree.

A 2-, 3- and 4-nodes is transformed into its red-black representation as follows:

Visualization link:

The Standford CS166 Tree slides below are excellent. They explain:

Binary trees are introduced, then a basic overview of red-black trees, followed by multiway-trees, whose isometry to red-black trees is shown starting around slide #196.

Red-black tree have these properties:

  • Every node has a flag indicating whether its either red or black.

  • The root is always black

  • No red node has a red child.

  • Every root-null path in the tree passes through the same number of black nodes.

Below are three valid red-black trees:

Exaple of red-balck tree

Each tree above has a black root as required. The left and right trees are the only trees with red nodes, and in both tree the red nodes have black children. While the left tree is not perfectly balance, it does obey the 4th rule. Take, for example, the path from the root to the right null child of node 107 passes through two (and only two) black nodes. Every other root-null path also passes through two and only two black nodes. Thus, left tree is a valid red-black tree. Finally, it is clear that in the middle and right trees every root-null path passes through the same number of black node.

Below is an examples of an invalid red-black trees:

Exaple of red-black tree

The path from the root to the left null child of node 7 passes through two black nodes, whereas the path to all other null children passes through three black nodes. This violates the fourth invariant above. Changing the color of two nodes as below will satisfy the fourth invariant:

Example of red-balck tree

Recall 2-3-4 trees are complete trees: all leaf nodes on the same level, and this is true after insertions and deletions. Their height is bounded by log2(n). Red-black trees actually represent the structure of 2-3-4 trees in a different way. They save memory compared to 2-3-4 trees. They also have insertion and deletion algorithms that involve only local transformations.

Resources

USC 2-3-4 tree and red black tree correspondence shows on slides 32-75 relationship of 2-3-4 trees to Red-Black trees. It contains extensive illustrations how the tree changes, how rotations occur.

Starting at slide #220, the equivalent 2-3-4 tree insert algorithm is for shown for an insertion into a red black tree.

Standford CS166:

The National Chengheng University Transforming a 2 3 4 tree into a Red Black Tree slides introduce 2 3 trees, 2 3 4 trees, and the show how 2 3 4 trees algorithms are equivalent to red black insert algorithms.

Open Data structures article on how 2-3-4 algorithms map to red black trees.

Stackoverflow Illustration of Relationship of 2 3 4 to Red Black Trees.

Todo

Rank these also most helpful for, say, illustration of xyz, pseudo code, etc.

Digipen.edu’s:

North Illinois University Insertion relationship between 2-, 3- and 4-trees and Red and Black trees.

In the CLRS book there is no discussion of the relationship of 2-3-4 trees to red-black trees. After introducing the structure of and rules for red-black trees, a lemma is immediately proved about the maximum possible height of rb trees. After this, the rotation, insertion and deletion algorthims are discussed in detail. The rb-tree introduced uses a common sentinel node as the left and right child of all leaf nodes.

Red Black Tree Lecture Notes:

Red Black Tree Implementations