Foreword

Recently, it took one week to look at the red-black tree algorithm on and off. This algorithm is still difficult because many scenarios are involved. At the same time, the principles of HashMap and TreeMap that we will explain next involve the red-black tree algorithm.  The reference link has too many text descriptions. There are many articles about red and black trees, some of them are more and more aggressive, and some of them are very good. The key is not to talk about people (this is not a curse, it refers to the article is still a little abstract). Understanding allows you to fully understand its principles while reading this article and to memorize scenes quickly and completely.

Red-black tree principle

Red-black trees are a kind of self-balancing binary search tree (BST). Compared with AVL trees, red-black trees are more balanced, but they may cause more rotation during insertion and deletion. Therefore, if our application involves many frequent insert and delete operations, the red-black tree should be preferred. However, if the frequency of insert and delete operations is low and the frequency of search operations is high, the AVL tree should take precedence over the red-black tree. We need to keep in mind the following rules followed by each node of the red-black tree

(1) Each node is either black or red. (2) The root node is black. (3) Each leaf node is black. [Note: The leaf node here refers to an empty leaf node. In the principle of the algorithm, the space is represented by Nil, but in object-oriented languages, the space is represented by NULL.] (4) If a node is red, its children must It is black (note: this means there cannot be two consecutive red nodes). (5) All paths from a node to its descendants contain the same number of black nodes.

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_0.jpg

After understanding the above rules, you will enter the red and black tree insert and delete operations. The insert operation is fine. The most complicated is the delete operation. Do n’t panic. Let ’s take it step by step. Both the insert and delete operations may cause the tree. Imbalance again will break the rules of the above red-black tree. When inserting or deleting, we use the methods of [change color] and [rotate] to make the tree balance again. If Z is an insertion node, here we make the following naming convention: father node, grandfather node, uncle node. OK, let’s look at the insert operation first.

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_1.png

Red-black tree insertion

When it comes to insertion, we immediately have doubts. According to the red-black tree rule, each node is either red or black, so is the node we inserted red or black? If it is black, it is very likely that it will break the rule 5. At this time, we will spend a lot of effort to make the tree balance again, but if it is red, it is also very likely to break the rules two and four, but it is black than the inserted node. Easier to repair. So that’s why the insert node is red. So in the first step, we perform standard BST insertion and the node color is red. The insertion operation is divided into the following four scenarios.

(1) Z is the root node

(2) Z’s father is a red node and uncle is a red node

(3) Z’s father is a red node and uncle is a black node (straight line)

(4) Z’s father is a red node and uncle is a black node (triangle)

Z is the root node

When Z is the root node, because the default insertion node is red, but according to the red-black tree rule, the two root nodes are black, so the color is changed and the red is directly changed to black, as follows:

Z’s father is a red node and uncle is a red node

The same processing operation is performed without distinguishing whether Z is on the left or right side of its parent node, or on the left or right side of Z’s grandparent node.

(1) Set the “parent node” to black. (2) Set “Uncle Node” to black. (3) Set “Grandfather Node” to “Red”. (4) Set “Grandfather Node” to “Current Node” (red node); that is, continue to operate on “Current Node” afterwards.

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_2.png

or

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_3.png

 

Z’s father is a red node, and uncle is a black node (straight line)

According to the above premise, some children’s shoes may be divided into two cases where Z is on the left and right of its father node. Here I use two kinds of Z, Z’s father node, and Z’s grandfather node on the same straight line. The symmetry case is the same when explaining the triangle as follows. The two symmetry cases when Z, Z’s father node, and Z’s grandfather node constitute the triangle, so would it be better to understand and draw a piece in my mind? . There are two cases due to symmetry:

(1) When Z’s father node is to the left of Z’s grandfather node: [1] Set the “Father node” to black [2] Set the “Grandfather node” to red [3] Turn right with “Father node”

(2) When Z’s father node is to the right of Z’s grandfather node: [1] Set “Father node” to black [2] Set “Grandfather node” to red [3] Left-handed with “Grandfather node”

 

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_4.png

or

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_5.png

Z’s father is a red node and his uncle is a black node (triangle)

(1) When Z’s father node is to the left of Z’s grandfather node: [1] Left-hand “Father Node” [2] Set “Father Node” as the current node (ie node A below) [3] evolved as above Case 1 straight, continue operation

(2) When Z’s father node is to the right of Z’s grandfather node: [1] Turn “Father node” right-hand [2] Set “Father node” as the current node (ie, node A below) [3] evolves into Continue to the second case as above

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_6.png

or

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_7.png

Data structure definition

First we need to define node elements. Each node has left child, right child, father node, node color and stored elements, so we define the node as follows:

 

 

class RedBlackNode <T extends Comparable <T >> {

    // black node 
    public  static  final  int BLACK = 0 ; 
     // red node 
    public  static  final  int RED = 1 ;
     // element 
    public T key;
     // parent node 
    RedBlackNode <T> parent;
     // left child 
    RedBlackNode <T> left ;
     // right child 
    RedBlackNode <T> right;

    // Node color 
    public  int color;

    RedBlackNode () {
        color = BLACK;
        parent = null ;
        left = null ;
        right = null ;
    }

    RedBlackNode (T key) {
        this ();
         this .key = key;
    }
}

 

 

Next is the definition of the red-black tree. The left-handed and right-handed methods are not given. What can be done with two strokes on paper, we simply define as follows

 

 

public  class RedBlackTree <T extends Comparable <T >> {

    private RedBlackNode <T> root = null ;


    private  void rotateLeft (RedBlackNode <T> x) {

    }
    
    private  void rotateRight (RedBlackNode <T> x) {

    }
}

 

 

Insert pseudo code

When performing the insert operation, we need to specify the exact location of the inserted node, that is, we need to find the parent node, left child, and right child of the inserted node and the default inserted node is red, and finally repair it by changing color or rotation, as follows:

 

 

 private  void insert (RedBlackNode <T> z) {

        RedBlackNode <T> y = null ;
        RedBlackNode <T> x = root;

        // If the root node is not empty, the parent node of the inserted node 
        while (! IsNull (x)) {
            y = x;

            // If the element value is less than the current element value, continue to find from the left child 
            if (z.key.compareTo (x.key) <0 ) {

                x = x.left;
            }

           // If the element value is less than the current element value, continue to find from the right child 
            else {

                x = x.right;
            }
        }
        
        // take y as the 
        parent node of z z.parent = y;

        // If the parent node is empty, the inserted node is the root node 
        if (isNull (y))
            root = z;
         else  if (z.key.compareTo (y.key) <0 )
            y.left = z;
         else 
            y.right = z;

        z.left = null ;
        z.right = null ;
        z.color = RedBlackNode.RED;

        insertFixup (z);

}

 

 

The next step is to implement the above-mentioned insertion repair method. The above analysis of several cases of the insertion operation is based on the premise that the parent node of the inserted node is red, so here we repair the parent node of the inserted node if it is red. At the same time, Both insertion and deletion have their symmetric cases, that is to say, we can divide the inserted and deleted nodes into two large cases on the left or right of their parent nodes. There is no doubt that these two operations will It must be symmetrical, and the most obvious and easy to understand insertion repair method is as follows (notes have been added, which can be viewed again with the help of the above analysis)

 

 

private  void insertFixup (RedBlackNode <T> z) {

        RedBlackNode <T> y = null ;
        
        while (z.parent.color == RedBlackNode.RED) {

            // If Z's
             parent node is to the left of Z grandparent node if (z.parent == z.parent.parent.left) {

                // Define Z's parent sibling node 
                y = z.parent.parent.right;

                // If y is red 
                if (y.color == RedBlackNode.RED) {
                
                    // z's father becomes black 
                    z.parent.color = RedBlackNode.BLACK;
                    
                    // y becomes 
                    blacky.color = RedBlackNode.BLACK;
                    
                    // z's grandfather becomes red 
                    z.parent.parent.color = RedBlackNode.RED;
                    
                    // take z's grandfather as z 
                    z = z.parent.parent;
                }
                // If y is black and z is the right child 
                else  if (z == z.parent.right) {

                    // take z's father as z 
                    z = z.parent;
                    
                    // Left 
                    rotateLeft (z) with the parent node of z;
                }

                // else if y is black and z is the left child 
                else {
                    
                    // z's father becomes black 
                    z.parent.color = RedBlackNode.BLACK;
                    
                    // z's grandfather becomes red 
                    z.parent.parent.color = RedBlackNode.RED;
                    
                    //                     rotate rightRight (z.parent.parent) with z's grandfather 
;
                }
            }

            // If Z's father node is on the right of Z grandparent node 
            else {

                // Define Z's parent sibling node 
                y = z.parent.parent.left;

                // If y is red 
                if (y.color == RedBlackNode.RED) {
                    
                    // z's father becomes black 
                    z.parent.color = RedBlackNode.BLACK;
                    
                    // y becomes 
                    blacky.color = RedBlackNode.BLACK;
                    
                    // z's grandfather becomes red 
                    z.parent.parent.color = RedBlackNode.RED;
                    
                    // Left rotate with z's parent node 
                    z = z.parent.parent;
                }

                // If y is black and z is the left child 
                else  if (z == z.parent.left) {
                    
                    // take z's father as z 
                    z = z.parent;
                    
                    //                     Rotate rightRight (z) with z's 
parent node ;
                }
                // else if y is black and z is the right child 
                else {
                   
                    // z's father becomes black 
                    z.parent.color = RedBlackNode.BLACK;
                    
                    // z's grandfather becomes red 
                    z.parent.parent.color = RedBlackNode.RED;
                    
                    // Left 
                    rotateLeft (z.parent.parent) with z's grandfather ;
                }
            }
        }
        
        // After the operation is completed, the root node becomes black 
        again. Root.color = RedBlackNode.BLACK;

}

 

 

Red-black tree removed

In the above insertion operation, we mainly check the color of the uncle to consider different situations, that is to say, the two violations are mainly two consecutive reds after insertion. In the delete operation, we check the color of the same level, that is, check the color of the sibling nodes to consider different situations. The main violation of the delete attribute is the change of the black height in the subtree, because deleting the black node may cause the root to leaf path. The height of black is reduced, in other words, the red and black tree rule five is broken. So how should we delete it? Perform a standard BST delete. When we perform a standard delete operation in BST, we always always delete a leaf node or a node with only one child (for internal nodes, we copy the successor node, and then recursively call to delete the successor node, successor node It is always a leaf node or a node with one child), so we only need to deal with the case where a node is a leaf or have a child , because deletion is a quite complicated process. In order to understand the deletion, we introduce the concept of double black, When a black node is deleted and replaced by a black child node, the child node is marked as double black, and the height of the black will not change at this time, so our main task for deleting is to convert the double black to a single black . It sounds as if I still feel aggression, not panic. Next, I will still use a detailed illustration to explain to you what a magical existence of double black is. Deletion operations are generally divided into the following three cases:

(1) The deleted node has no children, which is the leaf node. (Delete directly)  (2) The deleted node has only one son. (Delete the node directly and replace its position with the only child node of the node)  (3) The deleted node has two children.

The first and second cases above do not need me to say more. For the third case, the double black concept we introduced above is described in the reference link. For example, if the node v (black) is deleted, the successor node u Occupy the v node. Because the deleted node u is black, the number of black nodes passing this node is reduced by one. In order to solve this problem, we will introduce an additional black node to the occupied v node, although this solves the red-black tree rule five. Problem, but we know that the red-black tree rule one is that each node is either red or black, so it breaks rule one, and then we solve it by changing color or rotation. We will introduce an additional black node on the u node, so the double black is not a bit confusing. What does this mean? Let ’s take a look at the following figure to understand it at a glance. What about the double blacks that appear? Please look down.

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_8.png

When the current node Z is double black and is not the root node

[1] Left-left case (A node is the left node of its parent node, C is the left node of A)

(1) Turn the left child of the Z sibling node, node A, to black. (2) Use the parent node of Z, which is node B, to make a right-hand rotation. At this point, the double black on the Z node is given a black node to let D overlap, and eventually the double black evolves into a single black)

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_9.png

[2] Right-right case (A node is the right node of its parent node, C is the right node of A)

(1) Turn the right child of the Z sibling node, node A, to black. (2) Left-hand the parent node of Z, node B. (Note: We will see that node D will be connected to node B when left-handed. The double black on the Z node is given a black node to let D overlap, and eventually the double black becomes a single black)

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_10.png

[3] Left-right case (A node is the left node of its parent node, C is the right node of A)

(1) Turn the Z sibling node, node A, into red (2) Turn the Z sibling node, node A’s right child, into black (3) Left-handed with Z’s sibling node A (4) Evolve as above left-left Keep going

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_11.png

[4] Right-left case (A node is the right node of its parent node, C is the left node of A)

(1) Turn the Z sibling node, A node, into red (2) Turn the Z sibling node, A node’s left child, into black (3) Perform a right-hand rotation with Z’s sibling node A (4) Evolve as above , Continue

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_12.png

When the current node Z sibling is a black node and the child is a black node

[1] The parent node is red (discolored)

(1) Change the parent node of node Z, that is, node B to red (2) Change the sibling node of node Z, that is, node A to red (3) Just change the color: red + double black = single black

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_13.png

[2] The case where the parent node is black (the parent node is double black, continue to recur)

(1) The sibling node of the Z node, that is, the A node becomes red (2) The parent node of the Z, that is, the B node is assigned to the Z node, and the recursive operation is continued

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_14.png

When the current node Z sibling is red

[1] The sibling of Z node, that is, A node is to the left of the parent node of Z node

(1) The sibling node of the Z node, that is, the A node becomes black (2) The parent node of the Z node, that is the B node, is black (3) The right rotation of the parent node of the Z node, that is the B node (4) evolves into the above Parent node is red, continue operation

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_15.png

[2] The sibling of node Z, that is, node A is to the right of the parent node of node Z

(1) The sibling node of the Z node, that is, the A node becomes black (2) The parent node of the Z node, that is the B node, is black (3) The left node of the Z node, that is, the B node is left-handed (4) evolves into the above father Node is red, continue operation

Java_entry_series_[13]_Principles_of_the_red-black_tree_algorithm_16.png

Remove pseudocode

For the delete operation, we first need to find the node that needs to be deleted. As we analyzed, if only one of the children of the deleted node can be deleted directly, if there are two children, in addition to finding the subsequent standard delete operation, Delete and repair operations are required, as follows:

 

 

 public  void remove (RedBlackNode <T> v) {

        RedBlackNode <T> z = search (v.key);

        RedBlackNode <T> x = null ;
        RedBlackNode <T> y = null ;

        // If one of z's children is null, you must delete z 
        if (isNull (z.left) || isNull (z.right))
            y = z;
            
            // Otherwise we need to delete z's successor 
        else y = findSuccessor (z);
        
        // Let x be the left or right child of y (y can only have one child) 
        if (! IsNull (y.left))
            x = y.left;
         else 
            x = y.right;

        // Set the father of y to be the father of x 
        x.parent = y.parent;

        // If the 
        parent node of y is null, it means that x is the root node if (isNull (y.parent))
            root = x;

            // If y is the left child, set x to be the left sibling of 
        else  if (! IsNull (y.parent.left) && y.parent.left == y)
            y.parent.left = x;

            // If y is the right child, set x to be the right brother of 
        else  if (! IsNull (y.parent.right) && y.parent.right == y)
            y.parent.right = x;          // If y is black, violation of red-black tree rules needs to be fixed 
        if (y.color == RedBlackNode.BLACK)
            removeFixup (x);
}

 

 

 

 

private  void removeFixup (RedBlackNode <T> x) {

        RedBlackNode <T> w;

        // when the deletion node is not the root node and black 
        the while (X! = && x.color the root == RedBlackNode.BLACK) {

            // If x is to the left of its 
            parent node if (x == x.parent.left) {

                // define x's siblings 
                w = x.parent.right;

                // when w is red 
                if (w.color == RedBlackNode.RED) {
                
                    // w becomes black 
                    w.color = RedBlackNode.BLACK;
                    
                    // x's father becomes red 
                    x.parent.color = RedBlackNode.RED;
                    
                    // Left 
                    rotateLeft (x.parent)                     with x's father ;
                                         w = x.parent.right;
                }

                // w when both children are black 
                if (w.left.color == RedBlackNode.BLACK && 
                        w.right.color == RedBlackNode.BLACK) {
                        
                    // w becomes black     
                    w.color = RedBlackNode.RED;
                    
                    // x's father is x 
                    x = x.parent;
                }
                else {
                     // w's right child is black 
                    if (w.right.color == RedBlackNode.BLACK) {
                    
                        // The left child of w becomes black 
                        w.left.color = RedBlackNode.BLACK;
                        
                        // w becomes red 
                        w.color = RedBlackNode.RED;
                        
                        //                         rotate rightRight (w) with w 
;
                        
                        // Re-assign the right child of x's father to w 
                        w = x.parent.right;
                    }
                    
                    // w is black, when the right sunspot is red
                    
                    // w becomes the color of x father 
                    w.color = x.parent.color;
                    
                    // The father of x becomes black 
                    x.parent.color = RedBlackNode.BLACK;
                    
                    // The right child of w becomes black 
                    w.right.color = RedBlackNode.BLACK;
                    
                    // Left 
                    rotateLeft (x.parent)                     with x's father ;
                                         x = root;
                }
            }
           // If x is to the right of its parent node 
            else {

                // define x's siblings 
                w = x.parent.left;

                 // when w is red 
                if (w.color == RedBlackNode.RED) {
                
                    // w becomes black 
                    w.color = RedBlackNode.BLACK;
                    
                    // x's father becomes red 
                    x.parent.color = RedBlackNode.RED;
                    
                    //                     Rotate rightRight (x.parent) with x's father 
;
                    
                    // Re-assign the left child of x's father to w 
                    w = x.parent.left;
                }

                // w when both children are black 
                if (w.right.color == RedBlackNode.BLACK && 
                        w.left.color == RedBlackNode.BLACK) {
                    
                    // w becomes black                         
                    w.color = RedBlackNode.RED;
                    
                    // x's father is x 
                    x = x.parent;
                }
                else {
                     // w's right child is black 
                    if (w.left.color == RedBlackNode.BLACK) {
                    
                        // The left child of w becomes black 
                        w.right.color = RedBlackNode.BLACK;
                        
                        // w becomes red 
                        w.color = RedBlackNode.RED;
                        
                        //                         rotate leftLeft (w) with w 
;
                        
                        w = x.parent.left;
                    }

                    // w is black, when the left sunspot is red
                    
                    // w becomes the color of x father 
                    w.color = x.parent.color;
                    
                    // The father of x becomes black 
                    x.parent.color = RedBlackNode.BLACK;
                    
                    // The left child of w becomes black 
                    w.left.color = RedBlackNode.BLACK;
                    
                    //                     Rotate rightRight (x.parent) with x's father 
;
                    
                    x = root;
                }
            }
        }
        
       // After the operation is completed, the x node becomes black 
        again x.color = RedBlackNode.BLACK;
}

 

 

Summary

In this section, we have analyzed the red-black tree principle in detail, and given most of the pseudo-code. In order to make the children’s shoes of the article immediately understand, no further optimization has been done. The paper may come to an end, and I know that this matter must be done. I can imagine the effects of other people on the Internet and their own analysis again. I can imagine that this article has been on and off for a few months. The way to understand, the children’s shoes seen in this article, combined with the description of a lot of red and black trees on the Internet, are estimated to be understandable. With the understanding of this section, we will analyze other low-level implementations next. It will be easy. If there are any improper or wrong descriptions in the article, they can be raised in the comments. Thank you for reading and we will meet again in the next section.

 

Java entry series [1] string creation method

Java entry series [2] string features

Java entry series [3] stringbuilder string buffer

Java entry series [4] packaging class

Java entry series [5] inheritance abstract classes interfaceson

Java entry series [6] Principles of dynamic array

Java entry series [7] collection arraylist

Java entry series [8] principles of doubley linked list alogrithm

Java entry series [9] linkedlist source code analysis

Java entry series [10] Hash algorithm principle

Java entry series [11] Hashtable source code analysis

Java entry series [12] Hashcode and equals

Java entry series [13] Principles of the read-black tree algorithmn method

Java entry series [14] Hashmap source code ananlysis

Orignal link:https://www.cnblogs.com/CreateMyself/p/11610133.html