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:

Basic Description and Examples of Red Black Trees

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 has a black root. The left and right trees are the only trees with red nodes, and in both trees all red nodes have black children. While the left tree is not perfectly balance, it does obey the 4th rule; for example, the path from the root to the right null child of node 107 passes through two (and only two) black nodes. The same is true for every other root-null path. Eac passes through only two black nodes. Therefore the left tree is a valid red-black tree. Clearly 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

B-Trees Defined

2-3-4 trees are just instances of a more general data structure known as B-Trees

The degree d of a B-tree is the minimum number of children (degree) for non-leaf nodes

  • Non-root nodes must have at least d-1 keys and d children

  • All nodes must have at most 2d-1 keys and 2d children

2-3-4 Trees have degree d = 2

Relationship Between 2-3-4 trees and Red Black Trees

Recall 2-3-4 trees are complete trees: all leaf nodes on the same level, and this remains true after insertion and deletion. 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. Their insertion and deletion algorithms also only involve local transformations. A red-black tree is a binary search tree. It has only 2-nodes, no 3- or 4-nodes.

A red-black tree can be built from a 2-3-4 tree directly by converting each 3- and 4- nodes to multiple 2-nodes. The result is a “balanced” Binary Search Tree. “Balanced” means that the height of an RB-Tree is at MOST twice the height of a 2-3-4 tree. Recall, the height of 2-3-4 tree had an upper bound of log2(n). Thus height or an RB-Tree is bounded by 2*log2(n) which is still O(log2(n)).

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