A red-black tree is a binary tree representation of a 2-3-4 tree. The child pointer of a node is either red or black. If the child pointer was present in the original 2-3-4 tree, it is a black pointer; otherwise, it is a red pointer.

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

Red Black Trees (under develpment)

Contents Under Development...

The algorithms shown in Implementing a 2 3 4 Tree in C++17 ensure a tree structure that is always balanced, but a 2-3-4 tree wastes storage because its 3-node and 4-nodes are not always full. A red black tree is a way of representing a 2 3 4 tree as a nearly‘balanced binary search tree.

“Every 2-, 3-, and 4-node in a 2 3 4 tree can be converted to at least 1 black node and 1 or 2 red children of the black node. Red nodes are always ones that would join with their parent to become a 3- or 4-node in a 2-3-4 tree” from http://ee.usc.edu/~redekopp/cs104/slides/L19b_BalancedBST_BTreeRB.pdf slide 45.

These links have good explanations of red black trees and how to transform the nodes of a 2-3-4 tree into red black tree:

National Chung University pdf shows how to transform a 2 3 4 tree into a red black tree starting at slide 67 and following. It makes more sense than the USC slides.

  • These Red black lecture notes look really good. They introduce the concept of external nodes, and it seems like the more thorough and tutorial-oriented of the lectures. It has succinct proofs about 2 3 4 tree and red black tree equivalence.
  • These Scribd slides, especially the last half, really explain Red Black trees as types of 2 3 4 trees, and how how the operations
  • These Standford slides decribe the isometry between 2 3 4 trees and ree black trees of insertion and dletion correpsond to the tow types of trees.

These discuess insertiong cases:

NIU also has a very succinct illustration and explanation of how 2-, 3- and 4-nodes correspond to red and black nodes and how describes the varies insertion senarios.

As does this stackover flow explanation.

Thoughts so far

A red-black tree is a binary tree representation of a 2-3-4 tree. The 2- and 4-nodes have only one equiavlent representation in a red black tree, but a 3-node can be represented two possilbe ways. <Describe node coloring in reb black trees> The nodes of a 2-, 3- and 4-nodes ares transformed into red-black tree nodes as follows:

A 2-node

a 4-node

a 3-node

Ulitmately explain why the invarient of the red black tree always holds true under the mappings described above.

A red black tree corresponds to a unique 2-3-4 tree; however, that 2-3-4 tree can be represented by different red black trees, but for all “tallest leaf” - “shortest” leaf <= 2 (I need the correct term for tallest and shortest leaf).

Todo

Take one of the trees outputted by my 2 3 4 tree test code and convert it into a red black tree.

Other sources: