Red Black TreesColored Edges Definition
Binary search tree.
Child pointers are colored red or black.
Pointer to an external node is black.
No root to external node path has two consecutive red pointers.
Every root to external node path has the same number of black pointers.
Binary Tree Representation Of 2-3-4 Trees
2- and 3-nodes waste space.
Overhead of moving pairs and pointers when changing among 2-, 3-, and 4-node use.
Represented as a binary tree for improved space and time performance. 2-3-4 node structure LC P1 LMC P2 RC RMC P3 Problems with 2-3-4 trees.
Representation Of 4-node
x y z a b c d a b c d z y x
Representation Of 3-node
x y a b c a b c y x a b y x c or
Representation Of 2-node
a x b x a b
Example
10 7 8 1 5 30 40 20 25 35 45 60 3
Properties Of Binary Tree Representation
Nodes and edges are colored.
The root is black.
Nonroot black node has a black edge from its parent.
Red node has a red edge from its parent.
Can deduce edge color from node color and vice versa.
Need to keep either edge or node colors, not both.
Red Black Trees
Colored Nodes Definition
Binary search tree.
Each node is colored red or black.
Root and all external nodes are black.
No root-to-external-node path has two consecutive red nodes.
All root-to-external-node paths have the same number of black nodes
Red Black Trees
Colored Edges Definition
Binary search tree.
Child pointers are colored red or black.
Pointer to an external node is black.
No root to external node path has two consecutive red pointers.
Every root to external node path has the same number of black pointers.
2-3-4 & Red-Black Equivalence
10 7 8 1 5 30 40 20 25 35 45 60 3
Red Black Tree
The height of a red black tree that has n (internal) nodes is between log2(n+1) and 2log2(n+1).
C++ STL implementation
java.util.TreeMap => red black tree
Top-Down Insert
Mimic 2-3-4 top-down algorithm.
Split 4-nodes on the way down.
Root Is A 4-node
x y z a b c d x y z a b c d a b c d z y x a b c d z y x
4-node Left Child Of 2-node
w x y a b c d z e w z y a b c d x e z w y x a b c d e z w y x a b c d e
4-node Left Child Of 3-node
v w x a b c d f z y e v x a b c d w y z f e y v x w a b c d z e f y v x w a b c d z e f
4-node Left Child Of 3-node
v w x a b c d f z y e v x a b c d w y z f e y v x w a b z e f c d y v x w a b c d z e f
4-node Middle Child Of 3-node
v w y x b c z a f d e x w v y a d b c z e f w x y b c d e f z v a w a b c f y d e v x z
4-node Middle Child Of 3-node
d z w y x b c v a f e x w v y a d b c z e f w x y b c d e f z v a w a b c f y d e v x z
4-node Right Child Of 3-node
One orientation of 3-node requires color flip.
Other orientation requires RR rotation.
Top-Down Delete
Mimic 2-3-4 top-down delete.
Color flip followed by possible rotation.
Red-Black Analysis
Less memory required than by 2-3-4 representation.
Less time required by 4-node splits when red-black representation is used.
O(log n) rotations per insert/delete.
Comments