Thursday, September 28, 2006

Red Black Trees

Topics

• B-Trees with 3 data items and 4 pointers -- usually called 4-2 trees.
• Implementation of essentially the same data structure as 4-2 trees, except using a different paradigm -- Red Black Trees using binary tree nodes.
• Red Black Trees are also very similar to AVL Trees -- They use a Binary Search Tree configuration with some added constructs to keep it reasonably balanced.
• Implementation is very close to a Binary Search Tree with the addition of "color" to each node and the associated link back to its parent.
• Implementation uses the same rotation patterns as AVL Trees.
• The colors "red" and "black" were just arbitrarily picked by the data structure's creator.
• The rules of a Red Black Tree:
•     The root is always black.
•     Nodes are always added as a red leaf according standard binary tree rules.   
•     The number of black nodes links from the root to any leaf is the same for every path to a node with one or two NULL children.
•     A red node always has a black parent.  There can never be two consecutive red nodes in any path to a leaf.
• Additional features:
•     There can be two consecutive black links in a path to a leaf.
•     Nodes can be changed to either red or black, but they start off red.
•     A black node could have two black children, two red children, or one of each.
•     Rebalancing a Red Black Tree to restore it to the rules above requires at most one set of rotations.
•     Rebalancing also can also require a number of additional "recolorings", which consists of flipping a bit or a boolean inside the nodes. 

Readings

Chapter 7, Section 7.1.7.  Although the title says "4-2 Trees" it contains both 4-2 trees and Red Black Trees, which are fundamentally the same, although the code for each would be differently implemented.  Note that the book's pseudocode algorithm is iterative and not recursive, and is very confusing to try to implement.  They gloss over a number of important details.  My C# implementation uses recursion and rotation.  My code's algorithm comes from another book and is very similar to an AVL tree.