Red and black tree addition and deletion operations

Posted Jun 16, 202020 min read

Red and black tree addition and deletion operations

The worst time complexity of red-black tree search is also O(logN). For its high performance, I feel that it is worthwhile to spend so many brain cells and time to study(I watched it many times). This article and the insertion diagram are also made by myself based on my own understanding. I hope that everyone can improve efficiency when learning red and black trees, and do not take detours.

Foreword

Recall and sort out the knowledge points of the binary tree In this article we said that "the binary tree is a simple binary search, but its performance depends on On the level of the binary tree".

  • The best case is O(logn), which exists in the case of a complete binary tree, and its access performance is similar to a half search;
  • The worst case is O(n). For example, all nodes of the inserted element have no left subtree(right subtree). In this case, all nodes of the binary tree need to be traversed once.
    [ Binary Sorting Tree ]( https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91zzzzzzzzzzzzzz -oss-process=image/format,png#pic_center)

The red-black tree is essentially a binary search tree, adding a field to identify the color in the node class, and has certain rules. At the same time, with this bright spot, the performance of the red-black tree reaches the ideal equilibrium state(the worst time responsibility for insertion, deletion, and search is O(logn)).

In Java1.8, HashMap uses linked lists and red-black trees, Interpretation of HashMap one year late . The TreeSet and TreeMap in the Java collection, the set and map in the C++ STL, and the management of the Linux virtual memory are all implemented through the red-black tree.

Introduction

Red-black tree(English:Red-black tree) is a self-balancing binary search tree, is a data structure used in computer science, the typical use is to achieve associative arrays. It was invented by Rudolf Bell in 1972, he called it "symmetric binary B-tree", and its modern name was obtained in a paper written by Leo J. Guibas and Robert Sedgewick in 1978. It is complicated, but its operation has a good worst-case runtime, and is efficient in practice:it can do lookups, insertions, and deletions in O(logn) time, where n is the element of the tree Number, excerpt from:Wikipedia-Red Black Tree .

public class RBTree<T extends Comparable<T>> {
    public RBNode<T> mRoot = null; //root node
    public static boolean RED = true;
    public static boolean BLACK = false;
    class RBNode <T extends Comparable<T>> {
        //colour
        boolean color;
        //Keyword(key value)
        T key;
        //Left child node
        RBNode<T> left;
        //Right child node
        RBNode<T> right;
        //Parent node
        RBNode<T> parent;

        public RBNode(T key, boolean color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {
            this.key = key;
            this.color = color;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }

        public T getKey() {
            return key;
        }

        @Override
        public String toString() {
            return "" + key +(this.color == RED? "RED":"BLACK");
        }
    }
}

Red black tree characteristics

    1. Each node is either red or black;
    1. The root node is always black;
    1. All leaf nodes are black(leaf nodes of red and black trees are empty nodes(NIL or NULL));
    1. If the node is red, its child nodes must be black(otherwise not necessarily);
    1. Each path from the root node to the leaf node or empty child node must contain the same number of black nodes(that is, the same black height).

requires attention:

The leaf node in feature 3 is a node that is only empty(NIL or null).
Feature 5, to ensure that no path will be twice as long as the other paths. Therefore, the red-black tree is a binary tree that is relatively close to equilibrium.

Red and black tree correction

Discoloration, left-hand rotation, and right-hand rotation are the expansion operations of the red-black tree on the binary tree, and they are also based on these three operations to comply with the five characteristics of the red-black tree. So students who are familiar with the operation of binary trees can easily understand how to ensure the balance after adding and deleting red and black trees as long as they master the three operations of red and black trees. Those who are not familiar with binary trees can also take a look at Knowledge point memory and sorting"]( http://dandanlove.com/2017/10/20/about-binary-tree/ ) this article.

Discoloration

Discoloration only refers to the discoloration of red and black tree nodes. Because the red-black tree node must be [red]or [black]two colors, so the color change is only to change the current node color to meet the characteristics(2, 3, 4, 5).

Left hand

Usually, the left-hand operation is used to rotate a red link inclined to the right to a left link. The schematic diagram is as follows:
[ Insert picture description here ]( https://img-blog.csdnimg.cn /20191224152901205.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9kYW5kYW5sb3ZlLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FF_#,size_16,color_FF

Left-handed animation(easier to understand and remember):
[ Insert picture description here ]( https://img-blog.csdnimg.cn /20191224152932810.gif#pic_center)

/*************Left-hand operation on the red and black tree node x ******************/
/*
 * Left-handed schematic:left-handed rotation of node x
 * p p
 *//
 * x y
 */\/\
 * lx y -----> x ry
 */\/\
 * ly ry lx ly
 * Left-handed did three things:
 * 1. Assign the left child node of y to the right child node of x, and assign x to the parent node of the left child node of y(when the left child node of y is not empty)
 * 2. Assign x's parent node p(not empty) to y's parent node, and update p's child node to y(left or right)
 * 3. Set the left child node of y to x and the parent node of x to y
 */
public void leftRotate(RBNode<T> x) {
    if(x == null) return;
    //1. Assign the left child node of y to the right child node of x, and assign x to the parent node of the left child node of y(when the left child node of y is not empty)
    RBNode<T> y = x.right;
    x.right = y.left;
    if(y.left != null) {
        y.left.parent = x;
    }
    //2. Assign x's parent node p(not empty) to y's parent node, and update p's child node to y(left or right)
    y.parent = x.parent;
    if(x.parent == null) {
        //mRoot is the root node of RBTree
        this.mRoot = y;
    } else {
        if(x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
    }
    //3. Set the left child node of y to x and the parent node of x to y
    y.left = x;
    x.parent = y;
}

Right hand

Right-handed and left-handed are just the opposite.
[ Insert picture description here ]( https://img-blog.csdnimg.cn /20191224153005170.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9kYW5kYW5sb3ZlLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FF_#,size_16,color_FF

Right-hand operation animation(easier to understand and remember):
[ Insert picture description here ]( https://img-blog.csdnimg.cn /20191224153029893.gif#pic_center)

/************* Right-hand operation on the red and black tree node y ******************/
/*
 * Right-hand diagram:right-hand node y
 * p p
 *//
 * y x
 */\/\
 * x ry -----> lx y
 */\/\
 * lx rx rx ry
 * Right-handed did three things:
 * 1. Assign the right child node of x to the left child node of y, and assign y to the parent node of the right child node of x(when the right child node is not empty)
 * 2. Assign y's parent node p(not empty) to x's parent node, and update p's child node to x(left or right)
 * 3. Set the right child node of x to y and the parent node of y to x
 */
public void rightRotate(RBNode<T> y) {
    if(y == null) return;
    //1. Assign the right child node of x to the left child node of y, and assign y to the parent node of the right child node of x(when the right child node of x is not empty)
    RBNode<T> x = y.left;
    y.left = x.right;
    if(x.right != null) {
        x.right.parent = y;
    }
    //2. Assign the parent node p of y(when not empty) to the parent node of x, and update the child node of p to x(left or right)
    x.parent = y.parent;
    if(y.parent == null) {
        this.mRoot = x;
    } else {
        if(y == y.parent.left) {
            y.parent.left = x;
        } else {
            y.parent.right = x;
        }
    }
    //3. Set the right child node of x to y and the parent node of y to x
    x.right = y;
    y.parent = x;
}

Red and black tree node addition

The red-black tree is expanded on the basis of a binary tree, and its added nodes are also added like a binary tree, and then adjusted. Two Binary Tree Knowledge Points Recall and Sorting #Create Binary Tree This section describes the addition of binary tree nodes. So here we focus on the adjustment after the addition of the binary tree.

  • The fifth characteristic of the red-black tree stipulates that the path from any node to each leaf node of its subtree contains the same number of black nodes. That is to say, when we insert a black node into the red-black tree, this feature will be violated.
  • At the same time, the fourth feature stipulates that the left and right children of the red node must be black nodes. When we insert a red node under a red node, this feature will be violated.

Therefore, we need to adjust the structure after inserting the black node to ensure that the red-black tree always meets these five characteristics.

The adjustment idea of the node after inserting the red-black tree

One of the most commonly used problem solving techniques in mathematics is to resolve multiple unknowns into one unknown.

We are worried about violating Article 5 when inserting a black node, and violating Article 4 when inserting a red node, so we will change the inserted node to red, and then judge whether the father of the inserted node is red. If so, modify and adjust(Discoloration, left-handed, right-handed). At the same time, during the adjustment process, we need to observe the "5 characteristics".

Because the operations of the left and right subtrees are symmetrical, we will talk about the case where the parent node of the node to be added is the left child of the grandfather node, and the addition of the right subtree is the opposite.

    1. If the [parent node]of the [red node]we added is black, then the tree does not need to be adjusted.
    1. If the [parent node]of the [red node]we added is red, then the tree needs to be adjusted.
  • 1), the parent node is red, the uncle node(parent node's sibling node) is red.

  • 2). The parent node is red, the uncle node is black, and the added node is the left child of the parent node.

  • 3). The parent node is red, the uncle node is black, and the added node is the right child of the parent node.

The parent node is black, and the grandfather node must be black, because the parent node of the red node cannot be red(feature 4:the two child nodes of each red node must be black).

Adjustment-Case(1):The parent node is red, and the uncle node(parent node's sibling node) is red.

The following figure is the modification process of the red-black tree in this case(the upper side is the target node is the left child, the lower side is the target node is the right child):

[ Insert picture description here ]( https://img-blog.csdnimg.cn /20191224153143480.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9kYW5kYW5sb3ZlLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FF_#,size_16,color_FF

In order for newly added nodes to also meet feature 4:

  • Dye all the parent and uncle nodes in black(node T satisfies feature 4), but in this way, the branches of father and uncle nodes have one more black;
  • Dye the grandfather node red, so that the two branches of the grandfather node meet all the characteristics, but we need to check whether the grandfather node meets the characteristics of the red-black tree;
  • Insert the grandfather node into the node and continue to modify towards the root of the tree;

This way we keep looping up until the parent node turns black or reaches the root of the tree.

Adjustment-Case(2):The parent node is red, the uncle node is black, and the added node is the left child of the parent node.

The following figure is the modification process of the red-black tree in this situation:
[ Insert picture description here ]( https://img-blog.csdnimg.cn /20191224153215672.png#pic_center)

We insert two consecutive red nodes on the left child branch of the grandfather node and insert one between the grandfather node and his right child(to ensure that there are no two consecutive red dots on the left and the red dot inserted on the right meets all the characteristics).

  • First dye the parent node black;
  • Dye the grandfather node to red;
  • Right-click the parent node;

We just adjusted through the above 3 steps to make the nodes of the whole red-black tree satisfy 5 characteristics.

Adjustment-Case(3):The parent node is red, the uncle node is black, and the added node is the right child of the parent node.

The following figure is the modification process of the red-black tree in this situation:
[ Insert picture description here ]( https://img-blog.csdnimg.cn /20191224153238966.png#pic_center)

Our parent node performs a left-hand operation, so that it becomes the state of adjustment-case(2), and then continue to adjust according to its adjustment operation.

Through the adjustment of the red-black tree in the above three situations, we can solve all the problems of the red-black tree inserted into the red node.

Red and black tree insertion code implementation:

/*********************** Insert a node into the red-black tree******************* ***/
public void insert(T key) {
    RBNode<T> node = new RBNode<>(key, BLACK, null, null, null);
    insert(node);
}

/**
 * 1. Insert the node into the red-black tree, the process is the same as the binary search tree
 * 2. Coloring the inserted node as "red"; coloring the inserted node as red will not violate "Characteristic 5"!
 * Fewer violations of a feature mean that the fewer cases we need to deal with.
 * 3. Through a series of operations such as rotation or coloring, make it a red-black tree again.
 * @param node inserted node
 */
public void insert(RBNode<T> node) {
    //The parent node of node
    RBNode<T> current = null;
    RBNode<T> x = mRoot;

    while(x != null) {
        current = x;
        int cmp = node.key.compareTo(x.key);
        if(cmp <0) {
            x = x.left;
        } else {
            x = x.right;
        }
    }
    //Find the location and use current as the parent node of node
    node.parent = current;
    //2. Next, determine whether node is inserted in the left or right child node
    if(current != null) {
        int cmp = node.key.compareTo(current.key);
        if(cmp <0) {
            current.left = node;
        } else {
            current.right = node;
        }
        node.color = RED;
        insertFixUp(node);
    } else {
        this.mRoot = node;
    }
}

/**
 * Modify the red and black tree after inserting the whole node
 * @param node
 */
public void insertFixUp(RBNode<T> node) {
    //Define parent node and grandfather node
    RBNode<T> parent, gparent;
    //The condition that needs to be trimmed:the parent node exists, and the color of the parent node is red
    while(((parent = node.parent) != null) && isRed(parent)) {
        //Grandfather node
        gparent = parent.parent;
        //If the parent node is the left child node of the grandfather node
        if(parent == gparent.left) {
            //Get uncle a little bit
            RBNode<T> uncle = gparent.right;
            //case1:Uncle node is red
            if(uncle != null && isRed(uncle)) {
                //Paint father and uncle nodes black
                parent.color = BLACK;
                uncle.color = BLACK;
                //Turn the grandfather node graph red
                gparent.color = RED;
                //Place the location on the grandfather node
                node = gparent;
                //Continue to judge upward
                continue;
            }

            //case2:The uncle node is black, and the current node is the right child node
            if(node   == parent.right) {
                //Left left from the father
                leftRotate(parent);
                //Replace the parent node with yourself to prepare for right-left
                RBNode<T> tmp = parent;
                parent = node;
                node = tmp;
            }
            //case3:the uncle node is black, and the current node is the left child node
            parent.color = BLACK;
            gparent.color = RED;
            rightRotate(gparent);
        } else {
            //If the father node is the right child node of the grandfather node, it is completely opposite to the above, essentially the same
            RBNode<T> uncle = gparent.left;
            //case1:Uncle node is also red
            if(uncle != null & isRed(uncle)) {
                parent.color = BLACK;
                uncle.color = BLACK;
                gparent.color = RED;
                node = gparent;
                continue;
            }

            //case2:The uncle node is black, and the current node is the left child node
            if(node   == parent.left) {
                rightRotate(parent);
                RBNode<T> tmp = parent;
                parent = node;
                node = tmp;
            }
            //case3:The uncle node is black, and the current node is the right child node
            parent.color = BLACK;
            gparent.color = RED;
            leftRotate(gparent);
        }
    }
    //Set the root node to black
    this.mRoot.color = BLACK;
}

Red and black tree node deletion

The above section discusses the addition of new nodes to the red-black tree, and the following section describes the deletion of the red-black tree. Red-black tree deletion is the most important part of red-black tree operation(why is it most important? Because it is the most difficult to understand).

Similarly, the deletion of the red-black tree is adjusted based on the deletion operation of the binary tree, so that it meets all the characteristics of the red-black tree.
Two Binary Tree Knowledge Points Recollection and Sorting #Two Binary Tree Node Delete This part describes the addition of the binary tree node, so here we focus on the binary tree Adjustment after adding.

The idea of deleting binary tree nodes

  • If the node to be deleted happens to be a leaf node, delete it directly.

  • If the node to be deleted also has child nodes, you need to establish the relationship between the parent node and the child nodes:

  • If there are only left or right children, just move this child up to the position to be deleted;

  • If there are two children, you need to select a suitable child node as the new root node, which is called the inherited node.(The new node is required to be larger than all the left subtrees and smaller than the right subtree. We can choose the largest node in the left subtree or the smallest node in the right subtree.)

Red Black Tree Delete Master Plan

We need to consider adjusting the deleted tree based on the idea of deleting the binary tree. I remember the article said that one of the most commonly used problem solving techniques in mathematics is to resolve multiple unknowns into an unknown number. `This sentence? The deletion of the binary tree is divided into two large cases or three small cases. We first merge these cases into one case, and then make adjustments, is it easier?

The merger of the three groups of red and black trees deleted

The steps to be deleted above are summarized as follows:

    1. If the left and right children of the deleted node are not null at the same time, then only the subtree inherits the position of the deleted node;
    1. If the deleted node is a leaf node, we directly adjust it;
  • If the left and right children of the deleted node are not null, you need to replace the deleted node with the successor node and the value and color, so as not to cause damage to the red-black tree balance, only need to adjust the successor node after deletion, In this way, we return to the state of dealing with cases 1 and 2;

    • Subsequent node is the rightmost child leaf node of the left subtree
    • Subsequent node is the leftmost leaf node of the right subtree;

If the color of the node to be deleted is red, then the structure of the red-black tree is not destroyed, so there is no need to adjust it. If we judge that the color of the deleted node is black, then adjust it;

Code and analysis:

/*********************** Delete the nodes in the red and black tree******************* ***/
public void remove(T key) {
    RBNode<T> node;
    if((node   = search(mRoot, key)) != null) {
        remove(node);
    }
}

/**
 * 1. The deleted node has no son, that is, the deleted leaf node. Then, delete the node directly.
 * 2. The deleted node has only one son. Then delete the node directly, and replace its original position with the only child node of the node.
 * 3. The deleted node has two sons. Then first find its successor node(the smallest of the right children, the child has no children or only one right child).
 * Then copy "the content of its successor node" to "the content of that node"; after that, delete "its successor node".
 * Here, the successor node is equivalent to a stand-in. After copying the content of the successor node to the "deleted node", delete the successor node.
 * ------ In this way, the problem becomes how to delete the successor node?
 * In the case where the "deleted node" has two non-empty child nodes, its successor nodes cannot be non-empty.
 * Note:The successor node is the node that is deleted;
 * That is:it means "either no son or only one son".
 * If there is no son, return to(1).
 * If there is only one son, return to(2).
 *
 * @param node The node to be deleted
 */
public void remove(RBNode<T> node) {
    RBNode<T> child, parent;
    boolean color;
    //1, the left and right children of the deleted node are not empty
    if((node.left != null) &&(node.right != null)) {
        //First find the successor node of the deleted node, use it to replace the position of the deleted node
        RBNode<T> replace = node;
        //1). Get the successor node [the smallest of the right children]
        replace = replace.right;
        while(replace.left != null) {
            replace = replace.left;
        }
        //2). Handle the relationship between [child nodes of successor nodes]and [child nodes of deleted nodes]
        if(node.parent != null) {
            //The node to be deleted is not the root node
            if(node   == node.parent.left) {
                node.parent.left = replace;
            } else {
                node.parent.right = replace;
            }
        } else {
            mRoot = replace;
        }

        //3). Handle the relationship between [child nodes of successor nodes]and [child nodes of deleted nodes]
        //The successor node must not have a left child node
        child = replace.right;
        parent = replace.parent;
        //Save the color of subsequent nodes
        color = replace.color;
        //Subsequent nodes are deleted nodes
        if(parent == node) {
            parent =replace;
        } else {
            if(child != null) {
                child.parent = parent;
            }
            parent.left = child;
            replace.right = node.right;
            node.right.parent = replace;
        }
        replace.parent = node.parent;
        replace.color = node.color;
        replace.left = node.left;
        node.left.parent = replace;
        //4. If the color of the removed successor node is black, re-correct the red-black tree
        if(color == BLACK) {
            removeFixUp(child, parent);
        }
        node = null;
    } else {
        //The deleted node is a leaf node, or has only one child.
        if(node.left != null) {
            child = node.left;
        } else {
            child = node.right;
        }
        parent = node.parent;
        //Save the color of "Replace Node"
        color = node.color;
        if(child != null) {
            child.parent = parent;
        }
        //"node node" is not the root node
        if(parent != null) {
            if(parent.left == node) {
                parent.left = child;
            } else {
                parent.right = child;
            }
        } else {
            mRoot = child;
        }
        if(color == BLACK) {
            removeFixUp(child, parent);
        }
        node = null;
    }
}

After completing the delete operation, we will proceed with our adjustment operation. After reading the above code, we know that the parameters that need to be passed when adjusting are successor node and deleted parent node.

Red and black tree deletion node adjustment

After the deletion, the successor node will become the child of the deletion node, then in the process of the connection, we will define the successor node as the target node.

Below we discuss the color of the node:because the color of the current node must be black, we only discuss based on the color of the sibling node.

    1. The current node is black, and the sibling node is red(then the child nodes of the parent node and the sibling node must be black);
    1. The current node is black, and the sibling node is black,

      • 1) The two child nodes of the brother node are black;
      • 2) The left child node of the sibling node is red, and the right child node is black;
      • 3) The right child node of the sibling node is red, and any color of the left child node;

Adjustment situation(1):The current node is black, and the sibling node is red

The following figure is the modification process of the red-black tree in this situation:
[ Insert picture description here ]( https://img-blog.csdnimg.cn /20191224153433246.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9kYW5kYW5sb3ZlLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FF,#70

  • Paint the parent node red, paint the sibling node black, and then rotate the parent node of the current node to the left. This will translate into a state in case 2.

Adjustment(2):The current node is black, and the sibling nodes are black

2.1. The left child node of the brother node is red, and the right child node is black;

The following figure is the modification process of the red-black tree in this situation:
[ Insert picture description here ]( https://img-blog.csdnimg.cn /20191224153500801.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9kYW5kYW5sb3ZlLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FF,#70

  • Paint the sibling node in red, point the current node to its parent node, and point its parent node to the grandfather node of the current node, continue to recursively judge and adjust to the root of the tree;

2.2, the two child nodes of the brother node are black;

The following figure is the modification process of the red-black tree in this situation:
[ Insert picture description here ]( https://img-blog.csdnimg.cn /20191224153536670.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9kYW5kYW5sb3ZlLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FF,#70

  • Paint the brother node of the current node in red, paint the left child node of the brother node in black, and then use the brother node as a pivot to perform a right-hand operation.

2.3. The right child node of the sibling node is red, and any color of the left child node;

The following figure is the modification process of the red-black tree in this situation:
[ Insert picture description here ]( https://img-blog.csdnimg.cn /20191224153615785.png#pic_center)

  • Paint the sibling node to the color of the parent node, then paint the parent node to black, paint the right child node of the brother node to black, and then use the parent node of the current node as a fulcrum to do a left-hand operation.

Red and black tree deletion adjustment case summary & code implementation

If it happened from case:1, it may be one of case:2, 3, 4:if it is case:2, then it is impossible for case:3 and 4 to appear again; if it is case:3 will inevitably lead to the appearance of case:4; if case:2 and 3 are not, then it must be case:4.

/**
 * Red and black tree deletion correction function
 *
 * After deleting the insertion node from the red-black tree(the red-black tree is out of balance), call this function again;
 * The purpose is to reshape it into a red-black tree.
 * If the current node to be deleted is red, it will not cause any damage to the characteristics of the current tree after it is deleted.
 * If the deleted node is black, it needs to be further adjusted to ensure that the subsequent tree structure meets the requirements.
 * Here we only correct the case where the deleted node is black:
 *
 * Adjust thinking:
 * In order to ensure that the number of black nodes on the left and right sides of the parent node of the deleted node is the same, it is important to pay attention to whether the node on the side of the parent node that is not deleted is black.
 * If the other side of the parent node after deletion is more black than the deleted side, we must find a way to balance it.
 * 1. Make one of the nodes on the other side of the parent node(that is, the sibling tree of the deleted node) red, and one less black.
 * 2. Or turn over the nodes on the other side(dye black) to one
 *
 * 1) The current node is black, and the sibling node is red(then the child nodes of the parent node and the sibling node must be black);
 * 2) The current node is black, and the sibling node is black, and the two child nodes of the sibling node are black;
 * 3) The current node is black, and the sibling node is black, and the left child node of the sibling node is red, and the right child node is black;
 * 4) The current node is black, and the sibling node is black, and the right child node of the sibling node is red, and the left child node is any color.
 *
 * In the above four cases, 2, 3, and 4 are all subsets(current node is black, and sibling nodes are black).
 *
 * Parameter Description:
 * @param node The node replaced after deletion(post-order node)
 * @param parent The parent node of the subsequent node
 */
private void removeFixUp(RBNode<T> node, RBNode<T> parent) {
    RBNode<T> other;
    RBNode<T> root = mRoot;
    while((node   == null || node.color == BLACK) && node != root) {
        if(parent.left == node) {
            other = parent.right;
            if(other.color == RED) {
                //case 1:The brother w of x is red [corresponding to state 1, convert it to 2, 3, 4]
                other.color = BLACK;
                parent.color = RED;
                leftRotate(parent);
                other = parent.right;
            }

            if((other.left == null || other.left.color == BLACK)
                    &&(other.right == null || other.right.color == BLACK)) {
                //case 2:x's brother w is black, and the two children of w are black [corresponding to state 2, use the root of the network tree of adjustment thought 1 to do recursion]
                other.color = RED;
                node = parent;
                parent = node.parent;
            } else {
                if(other.right == null || other.right.color == BLACK) {
                    //case 3:x's brother w is black, and the left child of w is red, and the right child is black [corresponding to state 3, adjusted to state 4]
                    other.left.color = BLACK;
                    other.color = RED;
                    rightRotate(other);
                    other = parent.right;
                }
                //case 4:x's brother w is black; and the right child of w is red, and the left child is any color [corresponding to state 4, use adjustment thought 2 to make adjustments]
                other.color = parent.color;
                parent.color = BLACK;
                other.right.color = BLACK;
                leftRotate(parent);
                node = root;
                break;
            }
        } else {
            other = parent.left;
            if(other.color == RED) {
                //case 1:x's brother w is red
                other.color = BLACK;
                parent.color = RED;
                rightRotate(parent);
                other = parent.left;
            }

            if((other.left == null || other.left.color == BLACK)
                    &&(other.right == null || other.right.color == BLACK)) {
                //case 2:Brother x is black, and both children of w are black
                other.color = RED;
                node = parent;
                parent = node.parent;
            } else {
                if(other.left == null || other.left.color == BLACK) {
                    //case 3:x's brother w is black, and the left child of w is red, and the right child is black.
                    other.right.color = BLACK;
                    other.color = RED;
                    leftRotate(other);
                    other = parent.left;
                }
                //case 4:x's brother w is black; and the right child of w is red, and the left child is any color.
                other.color = parent.color;
                parent.color = BLACK;
                other.left.color = BLACK;
                rightRotate(parent);
                node = root;
                break;
            }
        }
    }
    if(node   != null) {
        node.color = BLACK;
    }
}

to sum up

The worst time complexity of red-black tree search is also O(logN). For its high performance, I feel that it is worthwhile to spend so many brain cells and time to study(I watched it many times). This article and the insertion diagram are also made by myself based on my own understanding. I hope that everyone can improve efficiency when learning red and black trees, and do not take detours.

Reference article

There are many articles about Red Black Tree. After reading a few carefully, I feel that these three articles are good. The first part of the red-black tree is inserted, the second part of the red-black tree is left-handed and right-handed(the animation is very good) and the red-black tree is deleted. The last part of the code is very good and provides a test case. The main content of the article is the summary of the following three articles.

Revisit the data structure:an in-depth understanding of red and black trees
[Data Structure and Algorithm 05]Red-Black Tree(After reading the package to understand ~)
Realization of Java in Red Black Tree(5)

Related Posts