The concept of red black tree

Special binary search tree , There are storage bits on each node to indicate that the color of the node is red (Red) Or black (Black). The time complexity is O(lgn), Efficient .

characteristic :

(1) Each node is either black , Or red .

(2) The root node is black .

(3) Every leaf node (NIL) It's black .( Only empty (NIL or null) The node of )

(4) If a node is red , Then its child nodes must be black .( Black nodes can be continuous , Red nodes are not continuous )

(5) All paths from a node to its children contain the same number of black nodes .

 

Theorem : A tree contains n The height of a node's red black tree is at most 2log(n+1).

prove : Mathematical induction proves its converse proposition “ The height is h The red black trees in China have at least 2^(h/2 )-1 Nodes ”

Black node height bh(x) >= h/2, So prove it “ The height is h The red black trees in China have at least 2^bh(x)-1 A black node ”

The rotation of the red black tree

left-handed

In the left “ Left ”, signify “ The node being rotated will become a left node ”.

LEFT-ROTATE(T, x) 
y ← right[x]            // Premise : It is assumed that x The right child of y. Let's start the formal operation
right[x] ← left[y]      // take “y The left child ” Set to “x The right child ”, namely take β Set to x The right child
p[left[y]] ← x          // take “x” Set to “y The father of the left child ”, namely take β My father is set as x
p[y] ← p[x]             // take “x Father ” Set to “y Father ”
if p[x] = nil[T]      
then root[T] ← y                 // situation 1: If “x Father ” It's an empty node , Will y Set as root
else if x = left[p[x]] 
           then left[p[x]] ← y    // situation 2: If x It's the left child of its parent node , Will y Set to “x The left child of the parent node of ”
           else right[p[x]] ← y   // situation 3:(x It's the right child of its parent ) take y Set to “x The right child of the parent node of ”
left[y] ← x             // take “x” Set to “y The left child ”
p[x] ← y                // take “x Parent node ” Set to “y”

 

Right hand

On the right “ Right ”, signify “ The node being rotated will become a right node ”.

 

RIGHT-ROTATE(T, y) 
x ← left[y]             // Premise : It is assumed that y The left child of x. Let's start the formal operation
left[y] ← right[x]      // take “x The right child ” Set to “y The left child ”, namely take β Set to y The left child
p[right[x]] ← y         // take “y” Set to “x The father of the right child ”, namely take β My father is set as y
p[x] ← p[y]             // take “y Father ” Set to “x Father ”
if p[y] = nil[T]      
then root[T] ← x                 // situation 1: If “y Father ” It's an empty node , Will x Set as root
else if y = right[p[y]] 
           then right[p[y]] ← x   // situation 2: If y It's the right child of its parent , Will x Set to “y The left child of the parent node of ”
           else left[p[y]] ← x    // situation 3:(y It's the left child of its parent node ) take x Set to “y The left child of the parent node of ”
right[x] ← y            // take “y” Set to “x The right child ”
p[y] ← x                // take “y Parent node ” Set to “x”

 

Basic operation of red and black tree

add to

step1: The binary search tree inserts nodes , The key values are ordered .

step2: The inserted node means " Red ". This doesn't violate the characteristics 5, The fewer cases that need to be dealt with .

step3: Rotate or recolor , Adjust to red black tree .

Realization

RB-INSERT(T, z) 
y ← nil[T]                        // The new node “y”, take y Set to null node .
x ← root[T]                       // set up “ Red and black trees T” The root node of is “x”
while x ≠ nil[T]                  // Find the node to insert “z” In the binary tree T Position in “y”
     do y ← x                     
        if key[z] < key[x] 
           then x ← left[x] 
           else x ← right[x] 
p[z] ← y                          // Set up “z Father ” by “y”
if y = nil[T]                    
    then root[T] ← z               // situation 1: if y It's an empty node , Will z Set as root
    else if key[z] < key[y]       
            then left[y] ← z       // situation 2: if “z The values contained ” < “y The values contained ”, Will z Set to “y The left child ”
            else right[y] ← z      // situation 3:(“z The values contained ” >= “y The values contained ”) take z Set to “y The right child ”
left[z] ← nil[T]                  // z The left child of is set to blank
right[z] ← nil[T]                 // z Set the right child to blank . thus , It has been completed and will “ node z Insert into a binary tree ” It's in .
color[z] ← RED                    // take z Color it as “ Red ”
RB-INSERT-FIXUP(T, z)             // adopt RB-INSERT-FIXUP Color modification and rotation of red black tree nodes , Let the tree T It's still a red black tree

 

RB-INSERT-FIXUP(T, z)
while color[p[z]] = RED                                                  // if “ Current node (z) The parent node of is red ”, Then proceed to the following processing .
    do if p[z] = left[p[p[z]]]                                           // if “z Parent node ” yes “z The grandfather node of the left child ”, Then proceed to the following processing .
          then y ← right[p[p[z]]]                                        // take y Set to “z The uncle node of (z The grandfather node of the right child )”
               if color[y] = RED                                         // Case 1 Conditions : Uncle is red
                  then color[p[z]] ← BLACK                    ▹ Case 1   //  (01) take “ Parent node ” Set to black .
                       color[y] ← BLACK                       ▹ Case 1   //  (02) take “ Uncle node ” Set to black .
                       color[p[p[z]]] ← RED                   ▹ Case 1   //  (03) take “ Grandfather node ” Set to “ Red ”.
                       z ← p[p[z]]                            ▹ Case 1   //  (04) take “ Grandfather node ” Set to “ Current node ”( Red nodes )
                  else if z = right[p[z]]                                // Case 2 Conditions : Uncle is black , And the current node is the right child
                          then z ← p[z]                       ▹ Case 2   //  (01) take “ Parent node ” As “ New current node ”.
                               LEFT-ROTATE(T, z)              ▹ Case 2   //  (02) With “ New current node ” Rotate left for the fulcrum .
                          color[p[z]] ← BLACK                 ▹ Case 3   // Case 3 Conditions : Uncle is black , And the current node is the left child .(01) take “ Parent node ” Set to “ black ”.
                          color[p[p[z]]] ← RED                ▹ Case 3   //  (02) take “ Grandfather node ” Set to “ Red ”.
                          RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3   //  (03) With “ Grandfather node ” Right rotation for the fulcrum .
       else (same as then clause with "right" and "left" exchanged)      // if “z Parent node ” yes “z The grandfather node of the right child ”, Put the above operation into “right” and “left” Swap places , And then execute one after the other .
color[root[T]] ← BLACK

 

Depending on the parent of the inserted node , Can be " When node z Colored as a red node , And insert the binary tree " There are three situations to deal with .
① Description : The inserted node is the root node .
processing method : Paint this node black directly .
② Description : The parent of the inserted node is black .
processing method : Nothing needs to be done . After the node is inserted , It's still the red and black tree .
③ Description : The parent of the inserted node is red .
processing method : that , The situation is similar to that of the red black tree “ characteristic (5)” Conflict . In this case , The inserted node must have a non empty grandparent node ; Go further , The inserted node must also have an uncle node ( Even if the uncle node is empty , We also see it as being , An empty node itself is a black node ). After understanding this , We rely on " Uncle node ", Divide this situation into 3 In this case (Case).

Case 1 Uncle is red

(01) take “ Parent node ” Set to black .

(02) take “ Uncle node ” Set to black .

(03) take “ Grandfather node ” Set to “ Red ”.

(04) take “ Grandfather node ” Set to “ Current node ”( Red nodes ); namely , Then go on to “ Current node ” To operate .

 

Case 2 Uncle is black , And the current node is the right child

(01) take “ Parent node ” As “ New current node ”.

(02) With “ New current node ” Rotate left for the fulcrum .

Case 3 Uncle is black , And the current node is the left child

(01) take “ Parent node ” Set to “ black ”.

(02) take “ Grandfather node ” Set to “ Red ”.

(03) With “ Grandfather node ” Right rotation for the fulcrum .

Case 3 After processing , And then we put nodes "120" As the current node , It becomes Case 2 The situation of .

 

Three situations (Case) The core idea of dealing with problems is : Move the red node to the root node ; then , Set the root node to black .

Delete

step1: Two pronged search tree delete node .

3 In this case :

① The deleted node is a leaf node , Delete the node directly .

② The deleted node has only one child , Delete the node directly , And replace its position with the only child of the node .

③ The deleted node has two children , First, find out its subsequent nodes , And then put “ The content of its successor node ” Copy to “ The content of this node , Then consider deleting “ Its successor node ”. " The successor node of this node " Or no son , Or just one son . If there is no son , Then press " situation ① " To deal with ; If there's only one son , Then press " situation ② " To deal with .

step2: Rotate and recolor the red black tree .

RB-DELETE(T, z)
if left[z] = nil[T] or right[z] = nil[T]        
   then y ← z                                  // if “z The left child ” or “z The right child ” It's empty , Will “z” Assign a value to “y”;
   else y ← TREE-SUCCESSOR(z)                  // otherwise , take “z Successor node ” Assign a value to “y”.
if left[y] ≠ nil[T]
   then x ← left[y]                            // if “y The left child ” Not empty , Will “y The left child ” Assign a value to “x”;
   else x ← right[y]                           // otherwise ,“y The right child ” Assign a value to “x”.
p[x] ← p[y]                                    // take “y Parent node ” Set to “x Parent node ”
if p[y] = nil[T]                              
   then root[T] ← x                            // situation 1: if “y Parent node ” It's empty , Is set “x” by “ The root node ”.
   else if y = left[p[y]]                   
           then left[p[y]] ← x                 // situation 2: if “y It's the left child of its parent node ”, Is set “x” by “y The left child of the parent node of ”
           else right[p[y]] ← x                // situation 3: if “y It's the right child of its parent ”, Is set “x” by “y The right child of the parent node of ”
if y ≠ z                                   
   then key[z] ← key[y]                        // if “y Value ” Assign a value to “z”. Be careful : This is just a copy z The value of y, Without a copy z The color of the !!!
        copy y's satellite data into z        
if color[y] = BLACK                           
   then RB-DELETE-FIXUP(T, x)                  // if “y Black node ”, Call
return y

 

 

RB-DELETE-FIXUP(T, x)
while x ≠ root[T] and color[x] = BLACK 
    do if x = left[p[x]]     
          then w ← right[p[x]]                                             // if “x” yes “ The left child of its parent node ”, Is set “w” by “x My uncle ”( namely x For the right child of its parent node )                                         
               if color[w] = RED                                           // Case 1: x yes “ black + black ” node ,x The sibling node of is red .( here x And x The child nodes of the brother nodes are all black nodes ).
                  then color[w] ← BLACK                        ▹  Case 1   //   (01) take x The brother node of is set to “ black ”.
                       color[p[x]] ← RED                       ▹  Case 1   //   (02) take x The parent of is set to “ Red ”.
                       LEFT-ROTATE(T, p[x])                    ▹  Case 1   //   (03) Yes x The parent node of .
                       w ← right[p[x]]                         ▹  Case 1   //   (04) After the left-hand , To reset x Brother node of .
               if color[left[w]] = BLACK and color[right[w]] = BLACK       // Case 2: x yes “ black + black ” node ,x My brother node is black ,x The two children of the brother node are black .
                  then color[w] ← RED                          ▹  Case 2   //   (01) take x The brother node of is set to “ Red ”.
                       x ←  p[x]                               ▹  Case 2   //   (02) Set up “x Parent node ” by “ new x node ”.
                  else if color[right[w]] = BLACK                          // Case 3: x yes “ black + black ” node ,x My brother node is black ;x The brother node of the left child is red , The right child is black .
                          then color[left[w]] ← BLACK          ▹  Case 3   //   (01) take x The left child of the sibling node is set to “ black ”.
                               color[w] ← RED                  ▹  Case 3   //   (02) take x The brother node is set to “ Red ”.
                               RIGHT-ROTATE(T, w)              ▹  Case 3   //   (03) Yes x Right hand rotation of the brother node of .
                               w ← right[p[x]]                 ▹  Case 3   //   (04) Right after the , To reset x Brother node of .
                        color[w] ← color[p[x]]                 ▹  Case 4   // Case 4: x yes “ black + black ” node ,x My brother node is black ;x The right child of the brother node is red .(01) take x Parent node color Assign a value to x Brother node of .
                        color[p[x]] ← BLACK                    ▹  Case 4   //   (02) take x The parent node is set to “ black ”.
                        color[right[w]] ← BLACK                ▹  Case 4   //   (03) take x The right child of the sibling node is set to “ black ”.
                        LEFT-ROTATE(T, p[x])                   ▹  Case 4   //   (04) Yes x The parent node of .
                        x ← root[T]                            ▹  Case 4   //   (05) Set up “x” by “ The root node ”.
       else (same as then clause with "right" and "left" exchanged)        // if “x” yes “ The right child of its parent node ”, Put the above operation into “right” and “left” Swap places , And then execute one after the other .
color[x] ← BLACK

 

We are going to " Delete the nodes in the red black tree " There are roughly two steps , In the first step " Look up the red black tree as a binary tree , Delete node " after , Possible violation " characteristic (2)、(4)、(5)" Three characteristics . The second step is to solve the above three problems , And then keep all the characteristics of the red black tree .
For the convenience of analysis , We assume that "x Contains an extra black "(x The original color still exists ), So it won't violate " characteristic (5)". Why? ?
adopt RB-DELETE Algorithm , We know : Delete node y after ,x Occupied the original node y The location of . Now that it's deleted y(y It's black ), It means one less black node ; that , Add a black color to the position . such , When we assume that "x Contains an extra black ", It just makes up for " Delete y The missing black node ", It would not violate " characteristic (5)". therefore , hypothesis "x Contains an extra black "(x The original color still exists ), So it won't violate " characteristic (5)".
Now? ,x Not only does it contain its original color properties ,x There's also an extra black . namely x The color attribute of is " red + black " or " black + black ", It violates " characteristic (1)".

Now? , The problem we face , By solving " It's against the characteristics (2)、(4)、(5) Three characteristics " Transformed into " Resolve violation features (1)、(2)、(4) Three characteristics ".RB-DELETE-FIXUP What we need to do is to restore the characteristics of the red black tree through the algorithm (1)、(2)、(4).RB-DELETE-FIXUP The idea is : take x The extra black it contains keeps moving up the tree ( Move to the root ), Until the gesture below :
a) x Point to one " red + black " node . here , take x Set as a " black " The node can be .
b) x Point to the root . here , take x Set as a " black " The node can be .
c) Not the first two postures .

Put the posture above , Can be summed up as 3 In this case .
① Description :x yes “ red + black ” node .
processing method : Put... Directly x Set to black , end . At this time, all the properties of the red black tree are restored .
② Description :x yes “ black + black ” node , And x It's a root .
processing method : Don't do anything? , end . At this time, all the properties of the red black tree are restored .
③ Description :x yes “ black + black ” node , And x It's not a root .
processing method : This situation can be divided into 4 Seed situation . this 4 The seeds are shown in the table below :

 

(Case 1)x yes " black + black " node ,x The sibling node of is red

(01) take x Brother node of D Set to “ black ”.

(02) take x Parent node B Set to “ Red ”.

(03) Yes x Parent node B To carry on the left-hand .

(04) After the left-hand , To reset x Brother node of .

(Case 2) x yes " black + black " node ,x My brother node is black ,x The two children of the brother node are black

(01) take x The brother node of is set to “ Red ”.

(02) Set up “x Parent node ” by “ new x node ”.

(Case 3)x yes “ black + black ” node ,x My brother node is black ;x The brother node of the left child is red , The right child is black

(01) take x The left child of the sibling node is set to “ black ”.

(02) take x The brother node is set to “ Red ”.

(03) Yes x Right hand rotation of the brother node of .

(04) Right after the , To reset x Brother node of .

(Case 4)x yes “ black + black ” node ,x My brother node is black ;x The right child of the brother node is red ,x The brother node of the left child of any color

(01) take x Parent node color Assign a value to x Brother node of .

(02) take x The parent node is set to “ black ”.

(03) take x The right child of the sibling node is set to “ black ”.

(04) Yes x The parent node of .

(05) Set up “x” by “ The root node ”.

Trees - Red and black trees (R-B Tree) More articles about

  1. 2-3 Trees / Red and black trees (red-black tree)

    2-3 tree 2-3 Tree node : null node ,null The distance from the node to the root node is the same , therefore 2-3 Numbers are balance trees 2 Cross node , There are two branches , There is an element in the node , The left tree element is smaller , The element node of the right tree is larger 3 Cross node , There are three sub trees ...

  2. AVL Trees , Red and black trees

    AVL Trees https://baike.baidu.com/item/AVL%E6%A0%91/10986648 In computer science ,AVL Tree is the first self balanced binary search tree . stay AVL The height of two subtrees of any node in the tree ...

  3. Written test algorithm problem (51): brief introduction - Red and black trees (RedBlack Tree)

    Red and black trees (Red-Black Tree) Red black tree is a kind of BST, But adding a memory bit to each node indicates the color of the node (R perhaps B): From any one of them root To leaf The display of node coloring mode on the path of , The red black tree ensures that all paths are ...

  4. Talking about AVL Trees , Red and black trees ,B Trees ,B+ Tree principle and application ( turn )

    come from :https://blog.csdn.net/whoamiyang/article/details/51926985 background : I'm looking at < High performance Mysql>, When you see creating high-performance indexes , Book ...

  5. B Trees 、B- Trees 、B+ Trees 、B* Trees Red and black trees

    Reprinted from :http://blog.csdn.net/quitepig/article/details/8041308 B Trees The binary search tree : 1. All non leaf nodes have at most two sons (Left and Right): ...

  6. Talking about AVL Trees , Red and black trees ,B Trees ,B+ Tree principle and application

    background : I'm looking at < High performance Mysql>, When you see creating high-performance indexes , The book says mysql Storage engine for InnoDB The index type used is B+Tree, that , Do you have such a question , For data indexing , Why should we make ...

  7. C# Linked list Binary tree Balanced binary trees Red and black trees B-Tree B+Tree The index to achieve

    Linked list => Binary tree => Balanced binary trees => Red and black trees =>B-Tree=>B+Tree 1. Linked list Linked list structure is composed of many nodes , Each node has two parts : Data section : Save the actual data of the node . The earth ...

  8. data structure ( One ) Binary tree &amp; avl Trees &amp; Red and black trees &amp; B- Trees &amp; B+ Trees &amp; B* Trees &amp; R Trees

    Reference documents : avl Trees :http://lib.csdn.net/article/datastructure/9204 avl Trees :http://blog.csdn.net/javazejian/artic ...

  9. B Trees B+ Trees Red and black trees

    B-Tree(B Trees ) Before the specific explanation , A little bit , Again :B- Trees , That is to say B Trees . because B The original English name of the tree is B-tree, And many people in China like to put B-tree translation B- Trees , Actually , This is a very bad literal translation , It's easy to misunderstand . ...

Random recommendation

  1. ps Tutorial links

    course 1:http://www.68ps.com/jc/ps_tp.asp course 2:http://www.3lian.com/edu/photoshop/

  2. Title Case a Sentence

    Solutions Convert string to lowercase Split a string into an array of strings Loop array capitalizes every word Convert all elements of the array to a string The first method function titleCase(str) { str=str ...

  3. iPad Development

    get view: self.categoryItem.customView Set control to start : stay POP ver The size in self.preferredContentSize = The firm trilogy 1. By setting ...

  4. Xshell And securecrt Between different

    Now the more popular terminal simulator software is xshell and securecrt 了 , Now let's objectively analyze the two kinds of software , In order to better choose . One . Functional comparison 1.1Xshell function Support layout switching Adjustable execution sequence Provide multi label function Yes ...

  5. opengl Basic learning project ( 3、 ... and ) Several styles of polygon drawing

    Digression The reason why smart people don't succeed , It's because of their lack of tenacity . —— Isaac · Newton (1643 year 1 month 4 Japan —1727 year 3 month 31 Japan ) The British Maybe it can be understood as   When you want to go a step further , insist , Hard work and intelligence are indispensable .  Keep your back straight and straight ...

  6. Amazon Kindle Device is hiring in Beijing Shanghai and Shenzhen!

    This is Angela from recruitment team of Amazon Kindle Device Software & Applications, we are exp ...

  7. MongoDB 2.6.x Installation and deployment of

    1. download mongodb 2.6.x Version of zip package , stay D Disk create directory MongoDB, Unzip to D:\MongoDB Catalog . Create database directory D:\MongoDB\data, Next, open the command line window , Switch to D:\M ...

  8. UVA - 11882 Biggest Number(dfs+bfs+ Strong pruning )

    The main idea of the topic : Give a grid matrix , There are numbers in the matrix 0~9, Choose any grid as the starting point , Connect the numbers you have passed to form a number , Find the biggest number , You can only walk once per grid . Topic analysis :DFS. Pruning plan : In the current situation , Find out all that's still available ...

  9. Java My summer job

    Java Summer homework One .< malice > Reading notes < malice > It is one of the inferential novels written by Japanese writer keigo dono . After reading it, I can't help but be shocked by Mr. Dongye's peculiar writing technique and the ugliness of human nature displayed in the book . I think this book compares with < ...

  10. java jackson Ignore nonexistent property fields and According to the attribute name json

    @JsonAutoDetect(fieldVisibility = Visibility.ANY, getterVisibility = Visibility.NONE, isGetterVisibi ...