Sunday, November 27, 2011

Red and Black Tree

Posted by Unknown at 9:29 AM


CS231 AlgorithmsHandout # 21
Prof. Lyn TurbakNovember 2, 2001
Wellesley College 
Red-Black Trees 
Reading: CLRS Chapter 13; 14.1 { 14.2; CLR Chapter 14; 15.1 { 15.2. 
DeØnition
A red-black tree (RBT) is a binary search tree that satisØes the following red-black properties:
1.Every node has a color that is either red or black.
2.Every leaf is black.
3.If a node is red, both children are black.
4.Every path from a given node down to any descendant leaf contains the same number of black nodes. The number of black nodes on such a path (not including the initial node but including leaves) is called theblack-height (bh) of the node.
5.The root of the tree is black (not a CLR property, but should be).
Example
   D3               
                    
                     
 B2       K3        
                    
                     
A1C1    I2   N 2     
                     
                    
      G2 J1 M1 P2   
            
                    
                     
    E1 H    L  O1 R1 
      1  1   
                     
                        
      F              Q1S1
       1          
                        
                        
                         
Balance Property of Red-Black Trees
Consider a subtree with n nodes (non-leaves) rooted at any node x within a red-black tree. Then the following relationships hold:
3 height(x)=2 3 bh(x) 3 height(x)
3 2bh(x) ° 1 3 n < 2height(x)
3 lg(n) < height(x) 3 2 lg(n + 1)
The last relationship is the sense in which a red-black tree is balanced.
1
Red-Black Tree Insertion
To insert value V into red-black tree T:
Step 1: Use usual BST insertion algorithm, coloring new node red. RBT properties (1), (2), and (4) do not change. RBT property (3) will not hold if there is a red-red violation.
Step 2: Remove any red-red violation via the following rotation rules.1 It may be necessary to apply the rules multiple times. What is the maximal number of times the rules can be applied in the worst case?
  Z 
     
  d
 X
  
   
   
aY  
  
   
bc
   Z 
     
   d
  Y
   
   c
   
 X 
   
  b 
a  
   X  
  Y   
   a Z
     
 X Z  
    Yd
abcd 
  
   b c
 X 
a Y
  
 bZ
  
c d
Step 3: If Step 1 or Step 2 leaves the root of the tree red, reassert RBT property (5) by blackening the root. Why is this necessary? (Hint: look at the rules in Step 2.)
1These are simpler, but less e±cient than, those in CLR. They are due to Chris Okasaki, Purely Functional Data Structures, Cambridge University Press, 1998.
2
Red-Black Tree Insertion Example
Insert the letters A L G O R I T H M in order into a red-black tree.
insertAblacken
!A root!
 
G
AL
 G  
    
     
A  O 
     
     
 L R
     
     
     
A
insert
!
O
insert
!
I
    A      
            
 A        G  
        
            
insert   insert L    blacken
      rotate  
!L  !G  !   root!
 L    A L
    
       
            
      G      
            
              
              
     G  
        
 G      
         
         
     A L  
       
         
A L      
 insert  rotate
   !R   !
     O
    
   
        
          
   O      
           
         R 
         
          
           
 G    G   
          
            
A  O  A  O  
           insert
    insert    
     !T     !H
  L R L R
      
          
             
 I     I   T 
          
            
            
            
3
Red-Black Tree Insertion Example (continued)    
          
 G        
            
         G     
           
              
 A  O         
             
                
        A   O    
             
                
 L R          
    rotate   rotate
    !    !
      I   R
       
        
            
  I   T           
             
         H L  T 
               
            
              
 H               
               
                    
                  
             
  I     I    
               
                 
 G   O   G   O   
       blacken        insert
           
       root!        !M
A H L RA H L R
        
                 
                  
       T        T 
            
                
                
  I  
       
         
 G   O 
       
         
A H L  R 
         
         
     M  T
      
         
         
4
More E±cient Red-Red Violation Elimination, Part 1
The rotation rules presented earlier for eliminating red-red violations are simple but can require a number of rotations proportional to the height of the tree. CLR present more complex but e±cient rules. Here, we present
their rules in a diÆerent style, using the notationa to stand for a red-black tree named a rooted at a red node
andbto stand for a red-black tree named b rooted at a black node.
 
Case 1 of CLR's RB-Insert handles the case where the sibling of the top red node N of red-red violation is red. In this case, the blackness of N 's parent can be distributed among N and its sibling, as illustrated by the following rules:
  Y  Y
 Xc Xc
    
a ba b
  Z  Z
X c Xc
    
ab a b
X  X 
aYaY 
   
bc bc
X  X 
aZa Z
   
bc bc
Note that no rotations are required, but the red-red violation may move up the tree.
5
More E±cient Red-Red Violation Elimination, Part 2
Case 2 and Case 3 of CLR's RB-Insert handle the situation where the sibling of the top red node N of red-red violation is black. In this case, a single rotation2 eliminates the red-red violation, as illustrated by the following rules:
   Z
  Yd
   
 X c
   
a b 
 Z  X  
   Y   
Xd  a Z
     
  X Z  
aY   Yd
     
 abcd  
bc  b c
 X 
aY 
  
 bZ
  
 cd
This more e±cient approach of eliminating red-red violations needs at most £(lg(n)) rule applications and one rotation.
2CLR presents the rules in such a way that two rotations may be required, but this can be optimized to one.
6
Red-Black Tree Deletion
To delete value V from red-black tree T:
Step 1: Use usual BST deletion algorithm, replacing a deleted node by its predecessor (or successor) in the case where neither child is a leaf. Let N be the node with a child leaf that is deleted. If N is black, property (4) (uniformity of black-height) is violated. Reassert it by making the \other" child of N doubly-black
Step 2: Propagate double-blackness up the tree using the following rules.3 The blackness token  turns a black node doubly-black and turns a red node black. Using these rules, the black height invariant can be reasserted with £(lg(n)) rule applications and at most 2 rotations.
3 A. The sibling of the doubly-black node is black and one nephew is red (CLR's RB-Delete Cases 3 and 4). This rule eliminates the blackness token with one rotation.
X  Y  X 
aZX ZaY 
      
 dbcd bZ
 Ya    
      
       
bc    cd
      
3 B. The sibling and both nephews of the doubly-black node are black (CLR's RB-Delete Case 2). This rule propagates the blackness token upward without rotation.
X X 
aYaY
  
bcbc
3 C. The sibling of the doubly-black node is red (CLR's RB-Delete Case 1). This enables Case A or B.
   X        Y 
               
             
 aY     X c
      
          
             
  bca   b
Step 3: If the doubly black token progagates to root, remove it.      
       
3Only the cases where the doubly-black node is a left child are shown; the cases where the doubly-black node is a right child are symmetric.
7
Red-Black Tree Deletion Example       
Delete the letters A L G O R I T H M in order from the red black tree constructed before.  
           
    I    I   
              
                   
  G   O   G   O   
                CaseB
       delete    
         !A      !
 A H L  R H L R
          
                 
                     
      M   T     M  T 
               
                    
                    
 I     I   
             
               
G   O   G   O  
              unblacken
      CaseB    
       !       root!
 H L  R H L  R
          
                
                  
    M  T     M  T 
            
                
                
 I     I   
             
              
G   O   G  O  
             blacken
      delete   
       !L      red!
 H L  R H M R
         
               
                 
    M  T       T 
           
              
              
8
Red-Black Tree Deletion Example (continued)    
            
   I       I   
               
             
 G  O   H O  
       delete    blacken
       
      !G     red!
  H M  R  M R
          
        
             
                 
        T      T 
             
               
               
  I      I   
              
           
H O   H    
     delete    replace
       
     !O     by!pred
  M  R  M R
        
        
            
               
       T      T 
            
              
              
 I        
              
          I     I  
             
                
H  M            
               
                  
       CaseAH  R deleteH    
         
    !     !R     
     R          
               
              
            
               
       M T  M T
              
      T          
                     
                 
                 
               
9
Red-Black Tree Deletion Example (continued)    
             
  I    I   I 
               
                  
replaceH  M CaseBH  M blackenH  M 
by!pred     !     red!     
            
    T    T    T
           
            
              
        delete   
     !I   
     H 
        
        
H M   M 
    replace  
    by!pred   
     
     T   T
       
         
         
 M  
    
   deleteM
  
  ! 
H  
  
  H 
    
     
     
     
  M    M 
CaseA delete   CaseB
   
!   !T !
H TH
     
     
        
         
deleteunblacken
!Mroot!
10
Augmenting Red-Black Trees
Can often improve running time of additional operations on a data structure by caching extra information in the header node or data nodes of a data structure. Must insure that this information can be updated e±ciently for other operations.
Examples:
1.Store in a header node the length of a linked or doubly-linked list.
2.Store in a header node the maximum value of a linked list representation of a bag. Can also store a pointer to the list node containing the maximum value. Does it matter whether the list is sorted vs. unsorted? Linked vs. doubly-linked?
3.Store the size of every red-black subtree in the root of that subtree.
size[leaf] = 0
size[node] = 1 + size[left[node]] + size[right[node]]
Can use size Øeld to:
3 Determine size of tree in £(1) worst-case time.
3 Perform Select(T, k) (i.e. Ønd the kth order statistic) in £(lg(n)) worst-case time.
3 Determine the rank of a given key x in £(lg(n)) worst-case time.
Insert and Delete can update the size Øeld e±ciently (i.e., without changing the asymptotic running time of Insert and Delete):
Insert: In downward phase searching for insertion point, increment sizes by one. In upward "Øx-up" phase, update sizes at each rotation.
Delete: After deleting node y, decrement sizes on path to root[T] by one. In upward "Øx-up" phase, update sizes at each rotation.
In general, can e±cienly augment every node x of a red-black tree with the a Øeld that stores the result of any function f that depends only on key[x], f(left[x]), and f(right[x]).
3 for Insert, Øeld only needs to be updated on path from insertion point to root.
3 for Delete, only needs to be updated on path from deletion point to root.
3 easy to update at every rotation.
11

 

0 comments:

Post a Comment

Subscribe to: Post Comments (Atom)