[ Algorithm ] Red-Black BST

Source From Here 
Left-leaning red-black BSTs (Guibas-Sedgewick 1979 and Sedgewick 2007) 
1. Represent 2–3 tree as a BST. 
2. Use "internal" left-leaning links as "glue" for 3–nodes 

An equivalent definition 
A BST such that: 

* No node has two red links connected to it.
* Every path from root to null link has the same number of black links.
* Red links lean left.

1-1 correspondence with 2-3 trees 
Key property. 1–1 correspondence between 2–3 and LLRB. 

Search implementation for red-black BSTs 
Observation. Search is the same as for elementary BST (ignore color). 

Red-black BST representation 
Each node is pointed to by precisely one link (from its parent) which can be encoded with color of BLACK or RED: 

Elementary red-black BST operations 
Left rotation. Orient a (temporarily) right-leaning red link to lean left. 

Right rotation. Orient a left-leaning red link to (temporarily) lean right. 

Color flip. Recolor to split a (temporary) 4-node. 

Invariants. Maintains symmetric order and perfect black balance. 

Insertion in a LLRB tree: overview 
Basic strategy. Maintain 1-1 correspondence with 2-3 trees by applying elementary red-black BST operations. 

Warmup 1. Insert into a tree with exactly 1 node. 

Case 1. Insert into a 2-node at the bottom. 

* Do standard BST insert; color new link red.
* If new red link is a right link, rotate left.

Warmup 2. Insert into a tree with exactly 2 nodes. 

Case 2. Insert into a 3-node at the bottom. 

* Do standard BST insert; color new link red.
* Rotate to balance the 4-node (if needed).
* Flip colors to pass red link up one level.
* Rotate to make lean left (if needed).
* Repeat case 1 or case 2 up the tree (if needed).

Java implementation 
Same code for all cases. 

* Right child red, left child black: rotate left.
* Left child, left-left grandchild red: rotate right.
* Both children red: flip colors.

The complete sample code in Groovy: 
- RedBlackBST.groovy 

view plaincopy to clipboardprint?

1. package ds  
2.   
3. class RedBlackBSTextends Comparable,V> {  
4.     private static boolean      RED=true  
5.     private static boolean      BLACK=false  
6.     private Node         root=null  
7.       
8.     private class Node{  
9.         K           key  
10.         V           value  
11.         Node     left=null  
12.         Node     right=null  
13.         Boolean     color=false  
14.           
15.         @Override  
16.         public String toString()  
17.         {  
18.             return String.format("(%s,%s,%s)|%s|%s", key, value, color, left, right)  
19.         }  
20.           
21.         public void b(){color=false}  
22.         public void r(){color=true}  
23.     }  
24.       
25.     private boolean isRed(Node n){  
26.         if(n==null) return false  
27.         else return n.color  
28.     }  
29.     public void put(K key, V value)  
30.     {  
31.         root=put(root, key, value)        
32.         root.color=false  
33.     }  
34.       
35.     public Node put(Node h, K key, V value)  
36.     {  
37.         if(h == null) return new Node(key:key, value:value,color:true)  
38.         int cmp = key.compareTo(h.key)  
39.         if(cmp < 0)          h.left =  put(h.left,  key, value)  
40.         else if(cmp > 0) h.right = put(h.right, key, value)  
41.         else                h.value = value  
42.           
43.         if(isRed(h.right) && !isRed(h.left))        h = rotateLeft(h)  
44.         if(isRed(h.left)  && isRed(h.left.left))    h = rotateRight(h)  
45.         if(isRed(h.left)  && isRed(h.right))        flipColors(h)  
46.           
47.         return h  
48.     }  
49.     public V get(K k)  
50.     {         
51.         Node node = root       
52.         while(node!=null)  
53.         {  
54.             int c = k.compareTo(node.key)  
55.             if(c==0) return node.value  
56.             else if(c<0) node = node.left  
57.             else node = node.right  
58.         }  
59.         return null  
60.     }  
61.     private Node rotateLeft(Node h)  
62.     {         
63.         assert(isRed(h.right))  
64.         Node x = h.right  
65.         h.right = x.left  
66.         x.left = h  
67.         x.color = h.color  
68.         h.r()  
69.         return x  
70.     }  
71.     private Node rotateRight(Node h)  
72.     {         
73.         assert(isRed(h.left))  
74.         Node x = h.left  
75.         h.left = x.right  
76.         x.right = h  
77.         x.color = h.color  
78.         h.r()  
79.         return x  
80.     }  
81.     private Node flipColors(Node h)  
82.     {         
83.         assert(!isRed(h))  
84.         assert(isRed(h.left))  
85.         assert(isRed(h.right))  
86.         h.r()  
87.         h.left.b()    
88.         h.right.b()  
89.     }  
90. }  

Testing Code: 

view plaincopy to clipboardprint?

1. package lab  
2.   
3. import ds.RedBlackBST  
4.   
5. class W5_E1 {  
6.     static void main(args)  
7.     {  
8.         RedBlackBST rbBST = new RedBlackBST()  
9.         def data = [] as Set  
10.         Random rdm = new Random()  
11.         100.times{  
12.             def k = rdm.nextInt(100)  
13.             data.add(k)           
14.             rbBST.put(k, k)           
15.         }  
16.           
17.         printf("BST Size=%d...\n", data.size())  
18.         data.each{ key->           
19.             assert(key==rbBST.get(key))           
20.         }  
21.         printf("Pass!")  
22.     }  
23. }  

ST implementations: summary