程式扎記: [ Algorithm ] Red-Black BST

標籤

2015年10月2日 星期五

[ 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 
  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==nullreturn 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 == nullreturn 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==0return 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: 
  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 

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!