Red Black Trees (under develpment)¶
Contents Under Development…
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:
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:
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:
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:
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.
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.
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.
Rank these also most helpful for, say, illustration of xyz, pseudo code, etc.
Overiew of all types of trees shows BST, 2-3 tree, and red black trees. Concept of rotations.
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.
CLRS: Introduction to Algorithms 3rd Edition B-Trees chapter 12, Red-Black Trees chapter 13. Instructor’s Solution Manual:
Red Black Tree Lecture Notes:
Red Black Tree Implementations¶
C# Implementation from Journal of Object Technology
C++ Implementation from a blog on sample source code.
Red Black Tree (RB-Tree) Using C++ from coders-hub.com.
Basic red-black tree in C++ using a fixed key and value type Cristian Silva, III, repository ongithub.com