.. include:: .. include:: 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: * `Red Black Tree Visualization `_ 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: .. 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% 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 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)). 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 `_: * `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: * `CLRS Solution good Illustrations `_. * `Instructor's Manual `_ * `Solutions to "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein CLRS Solutions `_ 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 Red Black Tree Implementations ------------------------------ * `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