Exploring the many types of Red/Black Trees
On my blog I frequently discuss various topics related to red/black trees. Because there are many variants of r/b trees I wanted to unify a simple recursive bottom up framework for implementing them. I have also begun exploring varioud top down variants as well.
RedBlackNode.hpp - The node definition for red/black trees
ValidateRedBlack.hpp - algorithms to verify a given tree is a valid red/black BST, with algorithms for 2-3, 2-3-4, and 2-3-4-5 red/black trees.
Bottom up algorithms:
RedBlack.hpp - This has the RedBlackTree class, from which all variants are derived, it contains the methods for rotations
and color flips, insertion, and a virtual fixUp method meant to implement the balancing rules of the particular
variant.
RedBlack234.hpp - "Traditional" bottom up 2-3-4 Tree based Red/Black Tree
RedBlack23.hpp - Parity Seeking 2-3 Tree based Red/Black Tree
LLRedBlack23.hpp - "Left Leaning" 2-3 Tree based Red/Black Tree
Top down algorithms:
TDRedBlack234.hpp - Top down 2-3-4 red/black tree's as described in sedgewick & guibas's orginal 1978 paper
TDRedBlack2345.hpp - Another top down variant from the above mentioned paper, uses only single rotations and implements 2-3-4-5 trees.
These tree's are used along with my TreeDraw library to create images such as the following for my blog:
which appear in articles describing the algorithms in this repo, such as:
http://www.maxgcoding.com/bottom-up-2-3-red-black-trees-let-your-red-nodes-lean-how-they-want/
http://www.maxgcoding.com/bottom-up-red-black-trees/
http://www.maxgcoding.com/validating-red-black-trees/
http://www.maxgcoding.com/top-down-2-3-4-5-trees-the-red-black-tree-time-forgot/