.. include:: <isonum.txt> .. include:: <isopub.txt>
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:
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:
.. figure:: ../images/rb-valid-examples.png :alt: 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:
.. figure:: ../images/red-black-invalid.jpg :alt: Exaple of red-black tree :scale: 90%
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:
.. figure:: ../images/rb-corrected-1.jpg :alt: Example of red-balck tree :scale: 90%
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
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 log\ :sub:2\ (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 log\ :sub:2\ (n). Thus height or an RB-Tree is bounded by 2*log\ :sub:2\ (n) which is still O(log\ :sub:2\ (n)).
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.
- Balanced Trees, Part I: B-Trees (slides 1-51), Red Black trees (slides 52-77), Multi-way trees (slides 78-271).
- Balanced Trees, Part 2 Red Black tree performance (slides 1-86).
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:
- Overiew of all types of trees shows BST, 2-3 tree, and red black trees. Concept of rotations.
- Mapping 2-3-4 Trees into Red-Black Trees .
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:
- Illustration and synoptic discussion of red black tree insertion and deletion discusses insertion and deletion.
- Tulane red black trees contains detailed pseudo code of all insertion cases
- Bartosz Milewski’s red-black tree article in C++ using std::shared_ptr_
- Bartosz Milewski’s red-black tree source code
- 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