Red and black trees are actually very simple

1. Background

In the development process, it is inevitable to maintain a set of data, and be able to add, delete, modify and check quickly. If the amount of data is large and needs to be persistent, choose the database. However, if the amount of data is relatively small, does not need persistence, and requires high response time, it is most appropriate to store it directly in local memory.

2. Linked list

Storing data in local memory is not random. You need to choose the appropriate data structure according to different scenarios. Let's first look at the following group of data, 54, 24, 74, 12, 42, 62, 83, 9, 17, 33, 49, 58, 65, 79, 90, 5, 20, 29, 37, 46, 69, 86 and 95. We need to select a data structure to store them and support rapid addition, deletion, modification and query operations.

When it comes to data structures, most people's first reaction is the simplest linear structures, such as arrays, linked lists, stacks or queues. If there is a scenario in which subscripts can be used to randomly access data, there is no doubt that the array is the most appropriate. After all, the data is accessed directly through the memory address (pointer), which is a performance lever. However, in the actual development, it is impossible for most scenarios to provide subscript access data, so let's use a two-way linked list to see:

The implementation of the two-way linked list is relatively simple. Here you can directly use the code:

public class DoublyLinked<V> implements Iterable<E> {
    
    /*The head and tail nodes of the linked list do not store data, but only serve as markers*/
    private final Node first, last;
    /*Linked list length*/
    private int size;
    
    public DoublyLinked() {
        this.first = new Node(null, null, new Node());
        (this.last = first.next).prev = first;
    }
    
    /*Nodes in linked list*/
    class Node {
        V value;
        Node prev, next;    
        public Node() {}
        public Node(V value, Node prev, Node next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }
    
    /*Get linked list length*/
    public int size() { return size; }
    
    /*Get chain header node*/
    public V peekFirst() {
        Node node = first.next;
        return last == node ? null : node.value;
    }
    
    /*Get the tail node of the linked list*/
    public V peekLast() {
        Node node = last.prev;
        return first == node ? null : node.value;
    }
    
    /*Insert a node into the head of the linked list*/
    public void addFirst(V value) {
        Node first = this.first;
        first.next = first.next.prev = new Node(value, first, first.next);
        ++size;
    }
    
    /*Insert a node to the end of the linked list*/
    public void addLast(V value) {
        Node last = this.last;
        last.prev = last.prev.next = new Node(value, last.prev, last);
        ++size;
    }
    
    /*Delete chain header node*/
    public V removeFirst() {
        Node first = this.first, node = first.next;
        if (last != node) {
            (first.next = node.next).prev = first;
            node.prev = node.next = null;
            --size;
        }
        return node.value;
    }
    
    /*Delete the tail node of the linked list*/
    public V removeLast() {
        Node last = this.last, node = last.prev;
        if (first != node) {
            (last.prev = node.prev).next = last;
            node.prev = node.next = null;
            --size;
        }
        return node.value;
    }
    
    /*Find nodes in the linked list*/
    public boolean contains(V value) {
        for (Node node = first.next, last = this.last; last != node; node = node.next) {
            if (Objects.equals(value, node.value)) {
                return true;
            }
        }
        return false;
    }

    /*Replace nodes in the linked list*/
    public boolean replace(V source, V target) {
        for (Node node = first.next, last = this.last; last != node; node = node.next) {
            if (Objects.equals(source, node.value)) {
                node.value = target;
                return true;
            }
        }
        return false;
    }
    
    /*Replace nodes in the linked list*/
    public void replaceAll(V source, V target) {
        for (Node node = first.next, last = this.last; last != node; node = node.next) {
            if (Objects.equals(source, node.value)) {
                node.value = target;
            }
        }
    }

    /*Delete nodes in the linked list*/
    public boolean remove(V value) {
        for (Node prev = first, node = prev.next, last = this.last;
             last != node; node = (prev = node).next) {
            if (Objects.equals(value, node.value)) {
                (prev.next = node.next).prev = prev;
                node.prev = node.next = null;
                --size;
                return true;
            }
        }
        return false;
    }

    /*Delete nodes in the linked list*/
    public void removeAll(V value) {
        for (Node prev = first, node = prev.next, last = this.last;
             last != node; node = (prev = node).next) {
            if (Objects.equals(value, node.value)) {
                (prev.next = node.next).prev = prev;
                node.prev = node.next = null;
                node = prev;
                --size;
            }
        }
    }

    /*Create iterator*/
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private Node current = DoublyLinked.this.first;
            
            @Override
            public boolean hasNext() {
                return DoublyLinked.this.last != current.next;
            }
            
            @Override
            public E next() {
                return (current = current.next).value;
            }
        };
    }
    
}

The data in the above linked list is disordered and repeatable. The time complexity of the methods related to the operation of the head and tail nodes is O(1), but at the same time, the scope of application of these operations is also very narrow. In most scenarios, you only know the specific values and then operate the linked list. At this time, you are more likely to use methods such as contains, replace and remove that need to traverse the nodes in the linked list. If you maintain a linked list with ordered values or de duplication of values, the method of inserting nodes also needs to traverse the linked list. If each traversal of the lookup node is the worst case, that is, each lookup node is at the end of the linked list, the time complexity is O(n), where n is the length of the linked list. There is no problem in the scenario of small amount of data, but if the amount of data is large, the linked list is long, and the scenario of high concurrency and high throughput is encountered, the performance may not be enough.

3. Binary search (sort) tree

The disadvantages of linked list operation are obvious, which requires frequent traversal of nodes, but the work of traversal can not be saved. Then you can find a way to shorten the path to be traversed. At this time, the binary search (sorting) tree meets this requirement. Let's take a look at the characteristics of binary search tree. Firstly, it must be a binary tree. Secondly, the keyword value of any node in the tree must be greater than that of its left child node and less than that of its right child node.

3.1. Search

Look at Figure 2. This is a binary search number. We know a keyword value of "37". We need to find this node in the tree. First, compare with the keyword value of the root node, "37" is smaller than "54", so continue to compare with the keyword value "24" of the left child node of the root node, which is obviously larger than 24, so continue to compare with the keyword value "42" of the right child node, and so on. When comparing to the fifth node, find the keyword value "37".

In this way, it is not necessary to traverse all nodes in the tree to find the data. It only needs to traverse down a child node of each node, which greatly shortens the search path. Ideally, the time complexity becomes O(log n), and its time growth curve is a logarithmic function.

Then, based on such logic, it is also very simple to find the maximum and minimum values. I won't say more here.

3.2. Insertion

The above explains how to find nodes. Let's continue to see how to insert a node into the tree. Note that the empty tree is also a binary search tree.

The inserted node also needs to traverse along a certain path from the root node. If a node with the keyword value equal to the value to be inserted is encountered in the process of traversal, modify it directly, otherwise continue to traverse. Until the last node is found, then wrap the value to be inserted into a node and insert it under the node.

As shown in Figure 2, you need to insert a node with a keyword value of "52" into the tree. First compare 52 with the keyword value of "54" of the root node. 52 is less than 54, and then compared with the left child node keyword value "24". 52 is larger than 24, and then continue to compare with 42. 52 is larger than 42, and then continue to compare with 49. 52 is larger than 49. It was necessary to continue to compare with the right child node of the node with the keyword value of "49", but the node with the keyword value of "49" does not have a right child node, so here we directly wrap the value of 52 as a node and insert it as the right child node with the keyword value of "49".

According to the above logic, if you need to insert nodes with keyword values of "44" and "17" respectively, what kind of logic should it be? You can test it yourself.

3.3. Delete

Deleting a node is troublesome. There are two situations. One is that the deleted node has two child nodes. The other is that the deleted node has at most one child node. For example, in Figure 2, you need to delete three nodes with keyword values of "65", "29" and "24", among which the deletion of "24" is more troublesome.

Let's first look at deleting the "65" node. We need to find the node with the key value of "65" first. There is no need to explain how to find the corresponding node in the tree according to a value. Since the node "65" has a right child node and "65" is the right child node of its parent node "62", after removing the node "65", you need to take the right child node "69" as the right child node of its parent node "62", so the deletion is completed. It is even easier to delete the node with the keyword value of "29". The node "29" is a bachelor without child nodes. After removing it, there is no need to do other operations. Let's look at the operation of deleting the node with the keyword value of "24". Since 24 has two child nodes, if the two child nodes are removed and establish a new parent-child relationship with their parent nodes, there is no way to continue to maintain the structure of binary search tree. At this time, you need to replace the deleted node with a previous node or a subsequent node, which will be deleted as a new deleted node.

A node with a keyword value of "24" has a predecessor node of "20" and a successor node of "29". Let's take a look at the relationship between these three nodes? In terms of value size, 20 is the maximum value smaller than 24 among all keyword values in the tree, and 29 is the minimum value larger than 24. From the structure of the tree, on the water balance axis, the two nodes with keyword values of "20" and "29" are closest to "24", which means that the previous node of "24" cannot have a right child node and the subsequent node cannot have a left child node. Then let's change our thinking. If the node "24" is removed, can one of the two nodes "20" or "29" be used to fill the position of "24". Finally, deleting "24" is converted to deleting "20" or "29" nodes. Is the problem solved. As for how to find the previous and subsequent nodes, we won't talk about it here. You can think about it yourself.

3.4 code example

public class BSTree<K extends Comparable<K>, V> {
    
    private Node root;
    private int size;
    
    /*Get the number of nodes in the tree*/
    public int size() { return size; }
    
    /*Get root node*/
    public Entry<K, V> getRoot() { return null == root ? null : new Entry<>(root.key, root.value); }
    
    /*Judge whether the tree with the given node as the root node is a binary search tree*/
    public boolean isBSTree(Node node) {
        // If the current node is empty, recursive verification starts from the root node
        node = null == node ? root : node;
        if (null == node) { // An empty tree is also a binary lookup tree
            return true;
        }
        // Get the parent node, left child node and right child node of the current node
        Node parent = node.parent, nodeLeft = node.left, nodeRight = node.right;
        if (null != parent && parent.left != node && parent.right != node) {
            // The parent node is not empty, but the left and right child node references of the parent node do not point to the current node, so it is not a binary tree
            return false;
        }
        if (null != nodeLeft) { // The left child node of the current node is not empty
            if (nodeLeft.parent != node || nodeLeft.compareTo(node) >= 0) {
                // The parent node reference of the left child node does not point to the current node, which is not satisfied. It is a binary tree.
                // Or if the key value of the left child node is greater than or equal to the key value of the current node, it is a binary search tree (the key value of the current node is greater than that of the left child node and less than that of the right child node)
                return false;
            }
            if (!isBSTree(nodeLeft)) { // Recurse the left sub node to judge whether the sub tree meets the characteristics of red black tree
                return false;
            }
        }
        if (null != nodeRight) { // The right child node of the current node is not empty
            if (nodeRight.parent != node || nodeRight.compareTo(node) <= 0) {
                return false;
            }
            if (!isBSTree(nodeRight)) {
                return false;
            }
        }
        return true;
    }
    
    /*Find value by key*/
    public V find(K key) {
        if (null == key) {
            throw new NullPointerException();
        }
        Node node = findNode(key, root);
        return null == node ? null : node.value;
    }
    
    /*Find the node with the smallest Key value*/
    public Entry<K, V> findMin() {
        Node node = root;
        while (null != node && null != node.left) {
            node = node.left;
        }
        return null == node ? null : new Entry<>(node.key, node.value);
    }
    
    /*Find the node with the largest Key value*/
    public Entry<K, V> findMax() {
        Node node = root;
        while (null != node && null != node.right) {
            node = node.right;
        }
        return null == node ? null : new Entry<>(node.key, node.value);
    }
    
    /*Insert a node*/
    public V put(K key, V value) {
        if (null == key) {
            throw new NullPointerException();
        }
        Node current = root, parent = null;
        // Gets the parent node of the location where the node is to be inserted
        int compare = 0;
        while (null != current && 0 != (compare = key.compareTo(current.key))) {
            current = compare > 0 ? (parent = current).right : (parent = current).left;
        }
        if (null != current) { // The key to insert already exists
            V ov = current.value;
            current.value = value;
            return ov;
        }
        if (null == parent) { // The tree to insert is empty
            this.root = new Node(key, value, null);
        } else { // Insert new node
            if (compare < 0) {
                parent.left = new Node(key, value, parent);
            } else {
                parent.right = new Node(key, value, parent);
            }
        }
        ++size;
        return null;
    }
    
    /*Delete node*/
    public V remove(K key) {
        if (null == key) {
            throw new NullPointerException();
        }
        Node remove, replace;
        if (null == (remove = findNode(key, root))) { // The node to be deleted cannot be found in the tree
            return null;
        }
        V value = remove.value;
        if (null != remove.left && null != (replace = remove.right)) {
            // If the left and right child nodes of the deleted node are not empty, the deleted node and the successor node will be replaced (you can also use the predecessor node to replace the deleted node)
            while (null != replace.left) {
                replace = replace.left;
            }
            remove.key = replace.key;
            remove.value = replace.value;
            remove = replace;
        }
        // At this time, there is only one child node at most
        Node parent = remove.parent, child = null == (child = remove.left) ? remove.right : child; // Get parent and child nodes
        if (null != parent && null != child) { // The parent node is not empty and has a child node that is not empty
            (parent.left == remove ? parent.left = child : (parent.right = child)).parent = parent;
            remove.parent = remove.left = null;
        } else if (null != parent) { // The parent node is not empty, and the child nodes are all empty
            remove.parent = parent.right == remove ? parent.right = null : (parent.left = null);
        } else if (null != child) { // The parent node is empty, but the child node is not empty
            root = child;
            remove.left = remove.right = child.parent = null;
        } else { // Both parent and child nodes are empty
            root = null;
        }
        --size;
        return value;
    }
    
    /*The binary tree is traversed in medium order to ensure the traversal of data from small to large*/
    public void forEach(Consumer<Entry<K, V>> action) {
        Deque<Node> deque = new LinkedList<>();
        for (Node node = root; node != null || !deque.isEmpty(); ) {
            for (; node != null; node = node.left) {
                deque.push(node);
            }
            Node pop = deque.pop();
            action.accept(new Entry<>(pop.key, pop.value));
            node = pop.right;
        }
    }
    
    /*Universal lookup node*/
    private Node findNode(K key, Node current) {
        Node found = null;
        for (int compare; null != current && null == found; ) {
            if ((compare = key.compareTo(current.key)) > 0) {
                current = current.right;
            } else if (compare < 0) {
                current = current.left;
            } else {
                found = current;
            }
        }
        return found;
    }
    
    class Node implements Comparable<Node> {
        K key;
        V value;
        Node parent, left, right;
        public Node(K key, V value, Node parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
        @Override
        public int compareTo(Node node) { return key.compareTo(node.key); }
        
    }
    
    public static class Entry<K, V> {
        private final K key;
        private final V value;
        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
        public K getKey() { return key; }
        public V getValue() { return value; }
        @Override
        public String toString() { return "Entry{key=" + key + ", value=" + value + '}'; }
    }
    
}

Through the above analysis, we understand the principle of binary search tree. The length of its search traversal node path depends on the height / depth of the tree. The height difference between the left and right subtrees of the node in the binary tree is the balance factor of the node. The balance factor of all nodes in the balanced binary tree will only be - 1, 0 and 1. The smaller the balance factor, the more balanced the tree will be, and the better the performance of searching and traversing nodes will be. Imagine if the data in Figure 2 has been sorted in advance, and then inserted into the binary search tree in turn, what will be the result? If the data is arranged in ascending order, the value inserted into the tree will become larger and larger. As a result, the data will only be inserted into the right subtree. Finally, the tree will degenerate into a linked list, and the balance factor is the number of nodes in the tree. Deleting nodes may also cause unpredictable growth of the balance factor.

4. Red black tree

When inserting or deleting nodes in a binary lookup tree, the balance factor may become large, or even directly degenerate into a linked list. The most typical problem is that when inserting ordered data, the problem will be very serious, but in the actual production process, we can't avoid that the inserted data is orderly, but this will destroy the balance of the tree, so we have to find a way to adjust the balance of the tree after inserting or deleting nodes. The binary tree that can meet this characteristic is called self leveling horizontal binary tree. At present, there are many mature self leveling horizontal binary search trees in the industry.

At present, there are about 6 self leveling and horizontal binary search trees commonly used, including heap tree, size balanced tree (SBT), spread tree, AVL tree (balanced binary search tree), red black tree, Scapegoat tree, etc. Some of them carry out self leveling through node rotation, some through local node reorganization and other operations. Today we are going to introduce, of course, one of the brightest balance trees, the red and black tree.

Let's take a look at the characteristics of red black tree. First, it must be a binary search tree. Then, in order to maintain balance, it mainly has the following five characteristics:

  1. The color of each node is red or black;

  2. The root node color is black;

  3. The color of each leaf node (Nil) is black (the leaf node here refers to the empty node that does not exist);

  4. The child nodes of red nodes must be black (two consecutive red nodes are not allowed in all paths);

  5. The number of black nodes on all paths from any node to its leaf node is equal;

Unlike AVL tree, red black tree does not explicitly declare the range of its balance factor, but its five characteristics implicitly ensure that the height difference between the left and right subtrees of any node in the tree will never exceed twice, so red black tree is an approximately balanced binary search tree. At this point, the red black tree is only an approximate balance. Compared with the AVL tree, which is an absolute balance (the absolute value of the height difference between the left and right subtrees of any node is not greater than 1), why does it have more advantages? The answer lies in the operation of self balancing. Based on the above five characteristics, the red black tree can handle as few nodes as possible during self balancing, and its time complexity is relatively more stable. Therefore, there are relatively many applications of red black tree in various fields, such as HashMap in jdk (jdk1.8 and above), TreeMap, map and set in STL, epoll in Linux system, etc.

The above explains the linked list and binary search tree. In fact, they are just used to attract jade. Now we are going to really enter the theme and analyze the red and black tree in detail.

4.1 node rotation

The red black tree is self leveling by rotating the nodes left and right or changing the node color. Modifying the node color is easy to understand. In the code, it is nothing more than a field with different values. Here we will focus on rotation. Node rotation is divided into left rotation and back rotation:

  • Left rotation: with the rotation node as the fulcrum, the right child node of the rotation node becomes the parent node of the rotation node, the left child node of the right child node becomes the right child node of the rotation node, and the left child node of the rotation node remains unchanged. As shown in Figure 4:

  • Right rotation: with the rotation node as the fulcrum, the left child node of the rotation node becomes the parent node of the rotation node, the right child node of the left child node becomes the left child node of the rotation node, and the right child node of the rotation node remains unchanged. As shown in Figure 5:

You can see the changes before and after the tree is rotated. It can be found that it can still maintain the structure of a binary search tree, and can adjust the structure of some nodes and the height of left and right subtrees. Therefore, by rotating nodes and changing the color of nodes, an unbalanced red black tree (a tree that does not meet the five characteristics of red black tree) can be adjusted into a standard red black tree. Let's start to analyze how to make the red black tree that destroys the balance self leveling after inserting and deleting nodes.

Node Description:

4.2. Insertion operation

The previous explanation of the characteristics of red black tree has said that red black tree is also a binary search tree, but it needs to do self leveling operation (node rotation or color change) after inserting nodes. Therefore, it can be seen that when inserting a node, the operation of the red black tree is the same as that of the binary query, that is, first find the location where the node should be inserted (the location of the parent node). If it is found that the value already exists in the search traversal process, modify it, and insert it if it does not exist. Node insertion may destroy the balance of the tree (not in line with the five characteristics of red black tree). Let's analyze the self leveling operation below.

First of all, you should remember that before you are ready to insert a node, the red black tree must meet the above five characteristics, but the tree may not meet the five characteristics due to the insertion of a node into the tree.

Generally, the initial node is set as the red node by default. For the convenience of later description, we uniformly call the inserted node as the "current node". After inserting a node into a standard red black tree, the following four scenes that need to be self leveled will be generated:

  • Scenario 1: the parent node of the current node is empty

Balance operation as, directly set the current node color to black, and then end the balance operation.

  • Scenario 2: the parent node of the current node is a black node

Since the front node is the initial node and the parent node is a black node, its left and right child nodes are leaf nodes, and its brother nodes can be either red nodes or leaf nodes. As shown below:

Note: the underlined node is the current node

Because inserting a red sub node under the black node will not destroy the balance of the red black tree, the current scene does not need to rotate or change the node color.

Note: in the following [scenario 4], another situation will be derived when the current node is not an inserted node. The left and right child nodes of the current node are black nodes, and the brother nodes can be either red nodes or black nodes. However, no matter what the sibling node is, these two cases can be adapted to [scenario 2].

  • Scenario 3: the parent node of the current node is a red node, and its uncle node is not a red node

Because the parent node of the current node is a red node, its grandfather node is a black node. Since the current node is an insert node and the uncle node is not a red node, its left and right child nodes are and uncle nodes can only be leaf nodes. As shown below:

Note: the underlined node is the current node

Let's take the first tree in the above figure as an example to balance. First, set the color of the parent node of the current node to black and the color of the grandfather node to red, then rotate right with the grandfather node as the fulcrum, and then end the balancing operation. As shown below:

Let's look at the balancing operation of the second tree in the figure. First, the parent node of the current node is used as the fulcrum for left rotation, and then the left child node of the current node is set as the current node. As shown below:

Is it the same structure as the first tree? Don't say anything else?

Note: in the following [scenario 4], another situation will be derived when the current node is not an inserted node. The left and right child nodes and sibling nodes of the current node are black nodes. However, these two situations can be adapted to [scenario 3].

  • Scenario 4: the parent node of the current node is a red node, and its uncle node is also a red node

Because the parent node and uncle node of the current node are red nodes, its grandfather node is black. Because the current node is an insert node and the uncle node is a red node, its left and right child nodes, brother nodes and left and right child nodes of the uncle node are leaf nodes. As shown below:

Note: the underlined node is the current node

Let's take the first tree in the above figure as an example to balance. First, set the color of the parent node and uncle node of the current node to black, then set the color of the grandfather node to red, and then set the grandfather node as the current node. As shown below:

Note: in the following derivation scenario, another situation will be derived when the current node is not an inserted node. The left and right child nodes, brother nodes and uncle nodes of the current node are black nodes. However, both cases can be adapted to [scenario 4].

Don't think this is over. We have to continue to look at the type of the parent node of the current node. From this, the following 4 cases can be derived:

  • The grandfather node of the current node is empty and can be adapted to [scenario 1]
  • The parent node of the current node is a black node, which can be adapted to [Scene 2]. As shown below:

Note: the underlined node is the current node.

  • The parent node of the current node is a red node, and the uncle node is a black node, which can be adapted to [Scene 3]. As shown below:

Note: the underlined node is the current node.

  • The parent node and uncle node of the current node are red nodes, and the left and right child nodes of the brother node and uncle node are black nodes, which can be adapted to [Scene 4]. As shown below:

Note: the underlined node is the current node.

Insert summary: the balancing process is a cycle. If the tree cannot be balanced after processing on the current node and its parent node, you need to set the grandfather node as the current node and enter the next cycle. Let's see that the parent node of the current node in [scenario 1] is the root node and the parent node of the current node in [scenario 2] is the black node. There is no need to rotate or change the node color. The tree is in a balanced state. In [Scene 3] and [Scene 4], after repeatedly rotating and changing color to balance the tree, we find that the parent node of the current node is either a root node or a black node. So we conclude that when the parent node is the root node or the parent node is the black node, the tree has been balanced. So you can see why the initial nodes inserted are red by default.

Maybe you just look at the scene analysis above and still don't quite understand it. But it doesn't matter. Having said so much, the ultimate goal is to achieve it at the code level. The ultimate goal is to combine the above scenario analysis and then read the following code examples.

4.3. Delete

Compared with the above insertion operation, the red black tree deletion operation will be relatively more complex. In fact, there will be a little more scenes requiring self leveling operation. Like insertion, the node deletion operation of red black tree is the same as that of binary search tree. First, find the node to be deleted. If it cannot be found, it will end. If it is found, it depends on the child nodes. If there are two child nodes of non leaf nodes, use the previous / subsequent node to replace the deleted node. If there is only one child node of non leaf node (note that if any node in the red black tree has only one child node of non leaf node, the child node must have only two leaf nodes), use the child node as the previous / subsequent node to replace the deleted node, and then there are only two leaf nodes in the final deleted node.

At this time, it should be noted that we cannot directly delete the node to be deleted, because the deleted node needs to participate in the balancing operation before the red black tree is deleted, and the node can be deleted only after balancing. It should be noted here that the purpose of self leveling before deletion is to make the deleted nodes become redundant nodes in the tree, that is, the red black tree can maintain balance after removing the deleted nodes. On the contrary, if the tree is not removed, it will be unbalanced.

For the convenience of later description, here we uniformly call the deleted node "current node". Before deleting a node, we have four scenarios that need to be balanced:

  • Scenario 1: the parent node of the current node is an empty node

End the balancing operation directly, and then delete the node to be deleted.

  • Scenario 2: currently red node

Because the current node is a red node, the parent node of the current node is a black node. Since the current node is a deleted node, its left and right child nodes are leaf nodes, and its brother nodes can be either red nodes or leaf nodes. As shown below:

Note: the underlined node is the current node.

Let's take the first tree in the above figure as an example to balance. Here, the current node is a red node. You can directly set the color of the current node to black, then end the balancing operation, and finally delete the nodes that need three places. As shown below:

Some people may think that the current node here is a deleted node. Since the tree is balanced, it's OK to delete the deleted node directly. Is it redundant to set the color of the current node black? This step is not redundant, but very important. You can continue to look back.

Note: in the following [scenario 5], another situation will be derived when the current node is not a deleted node. The left and right child nodes of the current node are black nodes, and its brother nodes can be either red nodes or black nodes. However, these two situations can be adapted to [scenario 2].

  • Scene 3: the current node and its sibling node are black nodes, and its sibling node has at least one red child node

Since the current node and its sibling nodes are black nodes, the parent node of the current node can be either red or black nodes. Since the front node is a deleted node and its brother node has at least one red node, its left and right child nodes are leaf nodes, and its brother nodes either have one red child node and one leaf node, or two red child nodes. As shown below:

Note: the underlined node is the current node.

Let's take the first tree in the above figure as an example to balance. First, change the color of the sibling node to the color of the parent node, then set the color of the parent node and the right child node of the sibling node to black, and then rotate left with the parent node as the fulcrum. As shown below:

We found that the tree is balanced. After the operation, we can end the balance, and then delete the nodes that need to be deleted.

Let's look at the balancing operation of the second tree in the figure. First, set the color of the brother node to red, and set the color of the left child node of the brother node to black, and then rotate right with the brother node as the fulcrum. As shown below:

Is it the same structure as the first tree? Don't say anything else?

Note: in the following [scenario 5], another situation will be derived when the current node is not a deleted node. The left and right child nodes of the current node are not leaf nodes. Its brother nodes either have a red node, a black node, or two red nodes. However, these two situations can be adapted to [scenario 3].

  • Scenario 4: the current node is a black node and its sibling node is a red node

Since the sibling node of the current node is a red node, its parent node is a black node. Since the current node is a deleted node and a black node, its left and right child nodes are leaf nodes, and the left and right child nodes of its brother nodes are black nodes. As shown below:

Note: the underlined node is the current node.

Let's take the first tree in the above figure as an example to balance. First, set the color of the brother node to black and the color of the parent node to red, and then rotate left with the parent node as the fulcrum. As shown below:

As you can see from the figure above, the tree is not balanced after this processing, and the nodes that need to be deleted cannot be deleted. However, the current scene processing is finished here, and the remaining balancing work needs to be handed over to [Scene 5] for processing.

Note: in the following [scenario 5], another situation will be derived when the current node is not a deleted node. The left and right child nodes of the current node are non leaf nodes. However, these two situations can be adapted to [scenario 3].

  • Scenario 5: the current node and its sibling nodes are black nodes, and its sibling nodes have no red child nodes

Since the current node and its sibling nodes are black nodes, the parent node of the current node can be either red or black nodes. Since the former node is a deleted node and its sibling node has no child nodes, the left and right child nodes of the current node and its sibling node are leaf nodes. As shown below:

Note: the underlined node is the current node.

Let's take the first tree in the above figure as an example to balance. First, set the color of the sibling node to red, and then set the parent node as the current node. As shown below:

Note: in the following derivation scenario, another situation will be derived when the current node is not an inserted node. The left and right child nodes of the current node are not leaf nodes, and the left and right child nodes of brother nodes are black nodes. However, both cases can be adapted to [scenario 5].

Don't think this is over. We have to continue to look at the type of brother nodes of the current node. From this, the following 5 cases can be derived:

  • The parent node of the current node is an empty node, which can be adapted to [scenario 1]

  • Currently, it is a red node, which can be adapted to [scenario 2]. As shown below:

Note: the underlined node is the current node

  • Both the current node and its sibling node are black nodes, and its sibling node has a red sub node, which can be adapted to [Scene 3]. As shown below:

Note: the underlined node is the current node

  • The current node is a black node and its brother node is a red node, which can be adapted to [Scene 4]. As shown below:

Note: the underlined node is the current node

  • Both the current node and its sibling node are black nodes, and its sibling node has two black child nodes, which can be adapted to [Scene 5]. As shown below:

Note: the underlined node is the current node

Delete summary: like the process of inserting balance, deleting balance is also a circular process. If the tree cannot be balanced after processing on the current node and its sibling nodes, you need to set its parent node as the current node and enter the next circular process. After the balance processing of [scenario 1] where the current node is the root node, [scenario 2] where the current node is the red node, and [scenario 3], there is no need to rotate or change the node color again. The tree is already in the balance state. In [Scene 4] and [Scene 5], after repeatedly rotating and changing color to balance the tree, it is found that the current node is either the root node or the red node, or the result of [Scene 3]. Therefore, in summary, when the current node is the root node or the black node, or the result of [scenario 3] processing, the tree has been balanced. So you can see why the current node should be set as a black node in [scenario 2].

If you are still dizzy just looking at the above, it doesn't matter. Let's go directly to the code. It may be clearer for you to understand the code according to the insertion and deletion scenarios above.

4.4 code example

  • java code example:
public class RBTree<K extends Comparable<K>, V> {
    
    private final static int RED = 0, BLACK = 1;
    
    private Node root;
    
    private int size;
    
    /*Get the key of the root node*/
    public Entry<K, V> getRoot() {
        return null == root ? null : new Entry<>(root.key, root.value);
    }
    
    /*Get the number of nodes in the tree*/
    public int size() {
        return size;
    }
    
    /*Judge whether the tree with the given node as the root node is a red black tree*/
    public boolean isRBTree(Node node) {
        // If the current node is empty, recursive verification starts from the root node
        node = null == node ? root : node;
        if (null == node) { // The empty tree is also a red black tree
            return true;
        }
        // Get the parent node, left child node and right child node of the current node
        Node parent = node.parent, nodeLeft = node.left, nodeRight = node.right;
        if (null != parent && parent.left != node && parent.right != node) {
            // The parent node is not empty, but the left and right child node references of the parent node do not point to the current node, so it is not a binary tree
            return false;
        }
        if (null != nodeLeft) { // The left child node of the current node is not empty
            if (nodeLeft.parent != node || nodeLeft.compareTo(node) >= 0) {
                // The parent node reference of the left child node does not point to the current node, which is not satisfied. It is a binary tree.
                // Or if the key value of the left child node is greater than or equal to the key value of the current node, it is a binary search tree (the key value of the current node is greater than that of the left child node and less than that of the right child node)
                return false;
            }
            if (RED == nodeLeft.color) {
                if (RED == node.color) {
                    // Both the current node and the left child node of the current node are red nodes. If they are not satisfied, they are a red black tree (two consecutive red nodes cannot appear on any path in the red black tree)
                    return false;
                }
            } else {
                if (null == nodeRight) {
                    // The left child node is a black node and the right child node is an empty node. It is not satisfied that it is a red black tree (the number of black nodes on any path from a node to any leaf node it can reach must be equal)
                    return false;
                } else if (RED == nodeRight.color && (null == nodeRight.left || null == nodeRight.right)) {
                    // The left child node is black, the right child node is red, and one of its child nodes is Nil node. It is not satisfied that it is a red black tree (the number of black nodes on any path from a node to any leaf node it can reach must be equal)
                    return false;
                }
            }
            if (!isRBTree(nodeLeft)) { // Recurse the left sub node to judge whether the sub tree meets the characteristics of red black tree
                return false;
            }
        }
        if (null != nodeRight) { // The right child node of the current node is not empty
            if (nodeRight.parent != node || nodeRight.compareTo(node) <= 0) {
                return false;
            }
            if (RED == nodeRight.color) {
                if (RED == node.color) {
                    return false;
                }
            } else {
                if (null == nodeLeft) {
                    return false;
                } else if (RED == nodeLeft.color && (null == nodeLeft.left || null == nodeLeft.right)) {
                    return false;
                }
            }
            if (!isRBTree(nodeRight)) {
                return false;
            }
        }
        return true;
    }
    
    /*Find value by key*/
    public V find(K key) {
        if (null == key) {
            throw new NullPointerException();
        }
        Node node = findNode(key, root);
        return null == node ? null : node.value;
    }
    
    /*Find the node with the smallest Key value*/
    public Entry<K, V> findMin() {
        Node node = root;
        while (null != node && null != node.left) {
            node = node.left;
        }
        return null == node ? null : new Entry<>(node.key, node.value);
    }
    
    /*Find the node with the largest Key value*/
    public Entry<K, V> findMax() {
        Node node = root;
        while (null != node && null != node.right) {
            node = node.right;
        }
        return null == node ? null : new Entry<>(node.key, node.value);
    }
    
    /*Insert node into red black tree*/
    public V put(K key, V value) {
        if (null == key) {
            throw new NullPointerException();
        }
        Node current = root, parent = null;
        // Gets the parent node of the location where the node is to be inserted
        int compare = 0;
        while (null != current && 0 != (compare = key.compareTo(current.key))) {
            current = compare > 0 ? (parent = current).right : (parent = current).left;
        }
        if (null != current) { // The key to insert already exists
            V ov = current.value;
            current.value = value;
            return ov;
        }
        if (null == parent) { // The tree to insert is empty
            root = new Node(key, value, BLACK, null);
        } else { // Insert new node
            Node insert = new Node(key, value, RED, parent);
            current = compare < 0 ? parent.left = insert : (parent.right = insert);
            fixAfterPut(current); // Rebalance the tree after inserting nodes
        }
        ++size;
        return null;
    }
    
    /*Delete node from red black tree*/
    public V remove(K key) {
        if (null == key) {
            throw new NullPointerException();
        }
        Node remove, parent, replace;
        if (null == (remove = findNode(key, root))) { // The node to be deleted cannot be found in the tree
            return null;
        }
        V value = remove.value;
        if (null != remove.left && null != (replace = remove.right)) {
            // The left and right child nodes of the deleted node are not empty nodes. The deleted node and subsequent nodes will be replaced
            while (null != replace.left) {
                replace = replace.left;
            }
            remove.key = replace.key;
            remove.value = replace.value;
            remove = replace;
        }
        // There is at most one non leaf node at this time
        if (null != (null == (replace = remove.left) ? replace = remove.right : replace)) {
            // If one of the left and right child nodes of the deleted node is not empty, the deleted node and child node will be replaced
            remove.key = replace.key;
            remove.value = replace.value;
            remove = replace;
        }
        // At this time, all are leaf nodes
        if (null == (parent = remove.parent)) { // Delete node as root node
            root = null;
        } else {
            fixBeforeRemove(remove); // You need to rebalance the tree before deleting nodes
            remove.parent = parent.right == remove ? parent.right = null : (parent.left = null); // Last delete node
        }
        --size;
        return value;
    }
    
    /*The binary tree is traversed in medium order to ensure the traversal of data from small to large*/
    public void forEach(Consumer<Entry<K, V>> action) {
        Deque<Node> deque = new LinkedList<>();
        for (Node node = root; node != null || !deque.isEmpty(); ) {
            for (; node != null; node = node.left) {
                deque.push(node);
            }
            Node pop = deque.pop();
            action.accept(new Entry<>(pop.key, pop.value));
            node = pop.right;
        }
    }
    
    /*Find node*/
    private Node findNode(K key, Node current) {
        Node found = null;
        for (int compare; null != current && null == found; ) {
            if ((compare = key.compareTo(current.key)) > 0) {
                current = current.right;
            } else if (compare < 0) {
                current = current.left;
            } else {
                found = current;
            }
        }
        return found;
    }
    
    /*Left rotation node*/
    private void rotateLeft(Node rotate) {
        // Gets the right child node of the rotation node
        Node right, parent, broLeft;
        if (null == rotate || null == (right = rotate.right)) {
            return;
        }
        if (null != (broLeft = rotate.right = right.left)) {
            // Set the right child node of the rotation node as the left child node of the right child node, and set the left child node parent node of the right child node as the rotation node
            broLeft.parent = rotate;
        }
        if (null == (parent = right.parent = rotate.parent)) {
            // The parent node of the right child node is set as the parent node of the rotation node. If the parent node is empty, the right child node is set as the root node and the color is set to black
            (this.root = right).color = BLACK;
        } else if (parent.left == rotate) {
            parent.left = right;
        } else {
            parent.right = right;
        }
        right.left = rotate;
        rotate.parent = right;
    }
    
    /*Right rotation node*/
    private void rotateRight(Node rotate) {
        // Gets the left child of the rotation node
        Node left, parent, broRight;
        if (null == rotate || null == (left = rotate.left)) {
            return;
        }
        if (null != (broRight = rotate.left = left.right)) {
            // Set the left child node of the rotation node as the right child node of the left child node, and set the right child node parent node of the left child node as the rotation node
            broRight.parent = rotate;
        }
        if (null == (parent = left.parent = rotate.parent)) {
            // Set the parent node of the left child node as the parent node of the rotation node. If the parent node is empty, set the left child node as the root node and set the color to black
            (this.root = left).color = BLACK;
        } else if (parent.left == rotate) {
            parent.left = left;
        } else {
            parent.right = left;
        }
        left.right = rotate;
        rotate.parent = left;
    }
    
    /*After inserting data, balance the tree*/
    private void fixAfterPut(Node current) {
        for (Node parent, grandfather, graLeft, graRight; ; ) {
            if (null == (parent = current.parent)) {
                // TODO: the parent node of the current node is an empty node, which is suitable for [scenario 1]
                current.color = BLACK;
                break;
            }
            if (BLACK == parent.color || null == (grandfather = parent.parent)) {
                // TODO: the parent node of the current node is a black node, or the grandfather node is an empty node (the parent node is the root node), which is suitable for [scenario 2]
                break;
            }
            if ((graLeft = grandfather.left) == parent) { // The parent node is the left child node of the parent node
                /*
                 * Node analysis:
                 * 1,The current node is not empty and is a red node
                 * 2,The parent node of the current node is not empty and is a red node
                 * 3,The grandfather node of the current node is not empty and is a black node
                 */
                if (null != (graRight = grandfather.right) && RED == graRight.color) {
                    // TODO: the uncle node of the current node is a red node, which is suitable for [scenario 4]
                    graRight.color = BLACK; // Set the node color to black
                    parent.color = BLACK; // Set the parent node color to black
                    grandfather.color = RED; // Set the grandfather node color to red
                    current = grandfather; // Set the grandfather node as the current node
                } else {
                    // TODO: the uncle node of the current node is a leaf node or a black node, which is suitable for [scenario 3]
                    if (current == parent.right) {
                        // The current node is the right child node of the parent node
                        rotateLeft(current = parent); // Make the parent node the current node and rotate the current node to the left
                        grandfather = (parent = current.parent).parent; // Reassign parent and grandfather nodes
                    }
                    parent.color = BLACK; // Set the parent node color to black
                    grandfather.color = RED; // Set the grandfather node color to red
                    rotateRight(grandfather); // Rotate the parent node to the right
                }
            } else { // The parent node is the right child node of the grandfather node. No comments will be made here
                if (null != graLeft && RED == graLeft.color) {
                    graLeft.color = BLACK;
                    parent.color = BLACK;
                    grandfather.color = RED;
                    current = grandfather;
                } else {
                    if (current == parent.left) {
                        rotateRight(current = parent);
                        grandfather = (parent = current.parent).parent;
                    }
                    parent.color = BLACK;
                    grandfather.color = RED;
                    rotateLeft(grandfather);
                }
            }
        }
    }
    
    /*Balance the number of nodes before deleting them*/
    private void fixBeforeRemove(Node current) {
        for (Node parent, left, right; null != current // Current node is not empty
                && null != (parent = current.parent); ) {  // TODO: the parent node of the current node is an empty node, which is suitable for [scenario 1]
            if (RED == current.color) { // TODO: the current node is a red node, which is suitable for [scenario 2]
                current.color = BLACK;
                break;
            }
            if ((left = parent.left) == current) { // If the current node is the left child of the parent node
                /*
                 * Node analysis:
                 * 1,The current node is a black node
                 * 2,The sibling node of the current node is not a leaf node
                 */
                if (RED == (right = parent.right).color) { // TODO: the sibling node of the current node is a red node, which is suitable for [scenario 4]
                    /*
                     * Node analysis:
                     * 1,The parent node is a black node;
                     * 2,The left and right child nodes of brother nodes are black nodes;
                     */
                    right.color = BLACK; // Set sibling node color to black
                    parent.color = RED; // Set the parent node color to red
                    rotateLeft(parent); // Rotate the parent node to the left (the current node is still the left child of the parent node)
                    right = parent.right; // Retrieve the sibling node of the current node
                }
                /*
                 * Node analysis:
                 * 1,The sibling node of the current node must be a black node
                 */
                Node broLeft = right.left, broRight = right.right;
                if ((null == broRight || BLACK == broRight.color) && (null == broLeft || BLACK == broLeft.color)) {
                    // TODO: there is no red node in the left and right child nodes of the current node's brother node, which is suitable for [scenario 5]
                    /*
                     * Node analysis:
                     * Case 1: the left and right child nodes of the current node's sibling node are black nodes
                     * Case 2: the left and right child nodes of the current node's sibling node are leaf nodes
                     */
                    right.color = RED; // Set the sibling node color to red
                    current = parent; // Make parent node current
                } else { // TODO: the sibling node of the current node has at least one red sub node, which is suitable for [scenario 3]
                    if (null == broRight || BLACK == broRight.color) {
                        // If the right child node of a sibling node is a leaf node or a black node, the left child node of the sibling node must be a red node
                        broLeft.color = BLACK; // Set the color of the left child node of the sibling node to black
                        right.color = RED; // Set the sibling node color to red
                        rotateRight(right); // Rotate sibling node right
                        right = parent.right; // Retrieve the right child node
                        broRight = right.right;
                    }
                    right.color = parent.color; // Set the color of the sibling node to the color of the parent node
                    broRight.color = BLACK; // Set the color of the right child node of the sibling node to black
                    parent.color = BLACK; // Set the parent node color to black
                    rotateLeft(parent); // Rotate parent node left
                    break;
                }
            } else { // The current node is a right child node, so no comments will be made here
                if (RED == left.color) {
                    left.color = BLACK;
                    parent.color = RED;
                    rotateRight(parent);
                    left = parent.left;
                }
                Node broLeft = left.left, broRight = left.right;
                if ((null == broLeft || BLACK == broLeft.color) && (null == broRight || BLACK == broRight.color)) {
                    left.color = RED;
                    current = parent;
                } else {
                    if (null == broLeft || BLACK == broLeft.color) {
                        broRight.color = BLACK;
                        left.color = RED;
                        rotateLeft(left);
                        left = parent.left;
                        broLeft = left.left;
                    }
                    left.color = parent.color;
                    broLeft.color = BLACK;
                    parent.color = BLACK;
                    rotateRight(parent);
                    break;
                }
            }
        }
    }
    
    class Node implements Comparable<Node> {
        K key;
        V value;
        int color;
        Node parent, left, right;
        
        public Node(K key, V value, int color, Node parent) {
            this.key = key;
            this.value = value;
            this.color = color;
            this.parent = parent;
        }
        
        @Override
        public int compareTo(Node node) {
            return key.compareTo(node.key);
        }
    }
    
    public static class Entry<K, V> {
        private final K key;
        private final V value;
        
        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
        
        public K getKey() {
            return key;
        }
        
        public V getValue() {
            return value;
        }
        
        @Override
        public String toString() {
            return "Entry{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }
    
}
  • java code test case:
public class RBTreeTest {
    
    @Test
    public void put() {
        ThreadLocalRandom random = ThreadLocalRandom.current();
        RBTree<Integer, String> tree = new RBTree<>();
        for (int i = 0; i < 100; ++i) {
            int key = (random.nextInt(100000) & Integer.MAX_VALUE) % 100;
            tree.put(key, String.valueOf(key));
        }
        RBTree.Entry<Integer, String> root = tree.getRoot();
        System.out.printf("rootKey=%d, rootValue=%s, size=%d, isRBTree=%b\n", root.getKey(), root.getValue(), tree.size(), tree.isRBTree(null));
    }
    
    @Test
    public void remove() {
        ThreadLocalRandom random = ThreadLocalRandom.current();
        RBTree<Integer, String> tree = new RBTree<>();
        for (int i = 0; i < 100; ++i) {
            int key = (random.nextInt(100000) & Integer.MAX_VALUE) % 100;
            tree.put(key, String.valueOf(key));
        }
        //
        while (tree.size() > 0) {
            tree.remove(tree.getRoot().getKey());
            System.out.printf("size=%d, isRBTree=%b\n", tree.size(), tree.isRBTree(null));
        }
    }
    
    @Test
    public void find() {
        ThreadLocalRandom random = ThreadLocalRandom.current();
        RBTree<Integer, String> tree = new RBTree<>();
        for (int i = 0; i < 100; ++i) {
            int key = (random.nextInt(100000) & Integer.MAX_VALUE) % 100;
            tree.put(key, String.valueOf(key));
        }
        System.out.println(tree.find(random.nextInt(100000) % 100));
    }
    
    @Test
    public void findMin() {
        ThreadLocalRandom random = ThreadLocalRandom.current();
        RBTree<Integer, String> tree = new RBTree<>();
        for (int i = 0; i < 100; ++i) {
            int key = (random.nextInt(100000) & Integer.MAX_VALUE) % 100;
            tree.put(key, String.valueOf(key));
        }
        System.out.println(tree.findMin());
    }
    
    @Test
    public void findMax() {
        ThreadLocalRandom random = ThreadLocalRandom.current();
        RBTree<Integer, String> tree = new RBTree<>();
        for (int i = 0; i < 100; ++i) {
            int key = (random.nextInt(100000) & Integer.MAX_VALUE) % 100;
            tree.put(key, String.valueOf(key));
        }
        System.out.println(tree.findMax());
    }
    
    @Test
    public void foreach() {
        ThreadLocalRandom random = ThreadLocalRandom.current();
        RBTree<Integer, String> tree = new RBTree<>();
        for (int i = 0; i < 100; ++i) {
            int key = (random.nextInt(100000) & Integer.MAX_VALUE) % 100;
            tree.put(key, String.valueOf(key));
        }
        RBTree.Entry<Integer, String> root = tree.getRoot();
        System.out.printf("rootKey=%d, rootValue=%s, size=%d, isBSTree=%b\n", root.getKey(), root.getValue(), tree.size(), tree.isRBTree(null));
        System.out.println(tree.findMin().getValue() + " " + tree.findMax().getValue());
        tree.forEach(System.out::println);
    }
    
}
  • C code example:

Since I am developing in java, the syntax and coding style of C are not very standard, so we will have a look

#define _CRT_SECURE_NO_WARNINGS
#pragma once

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#ifdef __cplusplus
extern "C" {
#endif // __cplusplus

	/*Red black tree node*/
	typedef struct _RBNode
	{
		void *p_key; // The key can be of any type. The key value comparator compares the size of the key
		void *p_value; // value can also be any type
		char color; // 0 stands for red, and non-0 stands for black
		struct _RBNode *p_parent, *p_left, *p_right;
	}RBNode;

	/*Red black tree structure*/
	typedef struct _RBTree
	{
		int size; // Number of nodes
		RBNode *p_root; // Root node pointer
		// Key value comparator in the tree, parameter 1: key value pointer that must be compared, parameter 2: key value pointer that must be handed over, parameter 3: return value pointer
		int(*p_kcmp)(void *, void *, char *);
	}RBTree;

	/*
	 * Create an empty red black tree;
	 * Parameter list:
	 *   p_tree: Red black tree pointer;
	 *   Key_Comparator: Represents the key value comparator;
	 * Return value:
	 *   NULL: Represents that the function execution failed;! NULL: represents the returned red black tree pointer;
	 */
	RBTree *create_RBTree(int(*p_kcmp)(void *, void *, char *));

	/*
	 * Judge whether the tree with the given node as the root node is a red black tree;
	 * Parameter list:
	 *	 p_tree: Red black tree pointer;
	 *   p_node: The starting node pointer that needs to be judged. If it is empty, take the root node;
	 *   p_res: Judgment result: 0: not a red black tree; 1: Is a red black tree;
	 * Return value:
	 *	 0: Represents that the function execution failed;! 0: indicates that the function is executed successfully;
	 */
	int is_RBTree(RBTree *p_tree, RBNode *p_node, char *p_res);

	/*
	 * Find node in red black tree
	 * Parameter list:
	 *   p_key: key pointer of the node to be searched;
	 *   p_tree: Pointer to the red black tree to be searched;
	 *   p_res: Found value;
	 * Return value:
	 *   0: Represents that the function execution failed;! 0: indicates that the function is executed successfully;
	 */
	int find_RBTree(void *p_key, RBTree *p_tree, void **p_res);

	/*
	 * Find the node with the lowest Key value in the red black tree
	 * Parameter list:
	 *   p_tree: Pointer to the red black tree to be searched;
	 *   p_res: Found value;
	 * Return value:
	 *   0: Represents that the function execution failed;! 0: indicates that the function is executed successfully;
	 */
	int findMin_RBTree(RBTree *p_tree, RBNode **p_res);

	/*
	 * Find the node with the largest Key value in the red black tree
	 * Parameter list:
	 *   p_tree: Pointer to the red black tree to be searched;
	 *   p_res: Found value;
	 * Return value:
	 *   0: Represents that the function execution failed;! 0: indicates that the function is executed successfully;
	 */
	int findMax_RBTree(RBTree *p_tree, RBNode **p_res);

	/*
	 * Insert node into red black tree
	 * Parameter list:
	 *   p_key: key of the node to be inserted
	 *   p_value: value of the node to insert
	 *   p_tree: Red black tree to insert node
	 * Return value:
	 *   0: Represents that the function execution failed;! 0: indicates that the function is executed successfully;
	 */
	int put_RBTree(void *p_key, void *p_value, RBTree *p_tree);

	/*
	 * Delete node from red black tree
	 * Parameter list:
	 *   p_key: key of node to be deleted
	 *   p_tree: Red black tree to delete node
	 *   p_res: Delete the value pointer of the node. If NULL is passed in, this part of space will be released inside the function
	 * Return value:
	 *   0: Represents that the function execution failed;! 0: indicates that the function is executed successfully;
	 */
	int remove_RBTree(void *p_key, RBTree *p_tree, void **p_res);

	/*
	 * Release red and black trees
	 * Parameter list:
	 *	 p_tree: Red and black trees that need to be released
	 */
	void free_RBTree(RBTree *p_tree);

#ifdef __cplusplus
}
#endif // __cplusplus
#include "RBTree.h"

int findNode(int(*p_kcmp)(void *, void *, char *), void *p_key, RBNode *p_curr, RBNode **p_res);

void rotateLeft(RBTree *p_tree, RBNode *p_rotate);

void rotateRight(RBTree *p_tree, RBNode *p_rotate);

void fixAfterPut(RBTree *p_tree, RBNode *p_current);

void fixBeforeRemove(RBTree *p_tree, RBNode *p_current);

RBTree *create_RBTree(int(*p_kcmp)(void *, void *, char *))
{
	if (!p_kcmp) // If the key value comparator function is empty, you cannot create a red black tree
		return NULL;

	// Open up space for red black tree and initialize
	RBTree *p_tree = NULL;
	size_t st_size = sizeof(RBTree);
	if (!(p_tree = (RBTree *)malloc(st_size)))
		return NULL;
	memset(p_tree, 0, st_size);
	p_tree->p_kcmp = p_kcmp;

	return p_tree;
}

int is_RBTree(RBTree *p_tree, RBNode *p_node, char *p_res)
{
	if (!p_tree) // The red black tree to be verified cannot be empty
		return 0;

	// If the incoming node to be submitted for inspection is empty, the verification starts from the root node. If the root node is also empty, success is returned (the empty tree is also a red black tree)
	if (!(p_node = !p_node ? p_tree->p_root : p_node))
		return *p_res = 1;

	// Get the parent node, left child node, right child node and other pointers of the current node
	RBNode *p_parent = p_node->p_parent, *p_nodeL = p_node->p_left, *p_nodeR = p_node->p_right;

	// If the parent node is not empty, but the pointers of the left and right child nodes of the parent node do not point to the current node, it is not a binary tree
	if (p_parent && p_parent->p_left != p_node && p_parent->p_right != p_node)
		return !(*p_res = 0);

	char compare = 0;
	if (p_nodeL)  // The left child node of the current node is not empty
	{
		if (!p_tree->p_kcmp(p_nodeL->p_key, p_node->p_key, &compare)) // Compare the size of the key of the left child node and the key of the right child node
			return 0;

		// The parent node reference of the left child node does not point to the current node, which is not satisfied. It is a binary tree. Or the key value of the left child node is greater than or equal to the key value of the current node. If it is not satisfied, it is a binary search tree
		if (p_nodeL->p_parent != p_node || compare >= 0)
			return !(*p_res = 0);

		if (!p_nodeL->color)
		{
			if (!p_node->color) // Both the current node and the left child node of the current node are red nodes. If not satisfied, it is a red black tree
				return !(*p_res = 0);
		}
		else
		{
			if (!p_nodeR) // The left child node is a black node and the right child node is an empty node. If it is not satisfied, it is a red black tree
				return !(*p_res = 0);

			// The left child node is black, the right child node is red, and one of its child nodes is Nil node. It is not satisfied that it is a red black tree
			if (!p_nodeR->color && (!p_nodeR->p_left || !p_nodeR->p_right))
				return !(*p_res = 0);
		}

		// Recurse the left sub node to judge whether the sub tree meets the characteristics of red black tree
		if (!is_RBTree(p_tree, p_nodeL, p_res))
			return 0;
		else if (!*p_res)
			return 1;
	}

	if (p_nodeR) { // The right child node of the current node is not empty
		if (!p_tree->p_kcmp(p_nodeR->p_key, p_node->p_key, &compare))
			return 0;
		if (p_nodeR->p_parent != p_node || compare <= 0)
			return !(*p_res = 0);
		if (!p_nodeR->color)
		{
			if (!p_node->color)
				return !(*p_res = 0);
		}
		else
		{
			if (!p_nodeL)
				return !(*p_res = 0);
			if (!p_nodeL->color && (!p_nodeL->p_left || !p_nodeL->p_right))
				return !(*p_res = 0);
		}
		if (!is_RBTree(p_tree, p_nodeR, p_res))
			return 0;
		else if (!*p_res)
			return 1;
	}

	return *p_res = 1;
}

int find_RBTree(void *p_key, RBTree *p_tree, void **p_res)
{
	if (!p_key || !p_tree || !p_res)
		return 0;
	RBNode *p_node = NULL;
	if (!findNode(p_tree->p_kcmp, p_key, p_tree->p_root, &p_node)) // Judge whether the node search function fails to execute
		return 0;
	*p_res = !p_node ? NULL : p_node->p_value;
	return 1;
}

int findMin_RBTree(RBTree *p_tree, RBNode **p_res)
{
	if (!p_tree || !p_res)
		return 0;
	RBNode *p_node = p_tree->p_root;
	while (p_node && p_node->p_left)
		p_node = p_node->p_left;
	*p_res = p_node;
	return 1;
}

int findMax_RBTree(RBTree *p_tree, RBNode **p_res)
{
	if (!p_tree || !p_res)
		return 0;
	RBNode *p_node = p_tree->p_root;
	while (p_node && p_node->p_right)
		p_node = p_node->p_right;
	*p_res = p_node;
	return 1;
}

int put_RBTree(void *p_key, void *p_value, RBTree *p_tree)
{
	if (!p_key || !p_tree)
		return 0;

	RBNode *p_parent = NULL, *p_curr = p_tree->p_root;

	// Gets the parent node of the location where the node is to be inserted
	char compare = 0;
	while (p_curr)
	{
		if (!p_tree->p_kcmp(p_key, p_curr->p_key, &compare))
			return 0;
		if (!compare)
			break;

		p_parent = p_curr;
		p_curr = compare > 0 ? p_curr->p_right : p_curr->p_left;
	}

	if (p_curr) // The key to insert already exists
	{
		if (p_curr->p_key && p_curr->p_key != p_key)
			free(p_curr->p_key);
		if (p_curr->p_value && p_curr->p_value != p_value)
			free(p_curr->p_value);
		p_curr->p_key = p_key;
		p_curr->p_value = p_value;
		return 1;
	}

	// Open up the red black tree node space and initialize it
	RBNode *p_insert = NULL;
	size_t st_size = sizeof(RBNode);
	if (!(p_insert = (RBNode *)malloc(st_size)))
		return 0;
	memset(p_insert, 0, st_size);
	p_insert->p_key = p_key;
	p_insert->p_value = p_value;

	if (!(p_insert->p_parent = p_parent)) // The red black tree to insert the node is an empty tree
		(p_tree->p_root = p_insert)->color = 1;
	else // The red black tree to insert the node is not an empty tree. Insert the node directly
	{
		if (compare < 0)
			p_parent->p_left = p_insert;
		else
			p_parent->p_right = p_insert;

		fixAfterPut(p_tree, p_insert); // Rebalance the tree after inserting nodes
	}

	++p_tree->size;
	return 1;
}

int remove_RBTree(void *p_key, RBTree *p_tree, void **p_res)
{
	if (!p_key || !p_tree)
		return 0;

	RBNode *p_remove = NULL, *p_parent = NULL, *p_replace = NULL;
	if (!findNode(p_tree->p_kcmp, p_key, p_tree->p_root, &p_remove)) // Judge whether the node search function fails to execute
		return 0;

	if (!p_remove) // If the node to be deleted is not found, it will be returned directly
		return 1;
	else if (p_res) // If the pointer representing the return value is not empty, it means that the value value of the deleted node needs to be passed out
		*p_res = p_remove->p_value;
	else if (p_remove->p_value) // Directly release the value of the deleted node
		free(p_remove->p_value);
	p_remove->p_value = NULL;

	if (p_remove->p_left && (p_replace = p_remove->p_right))
	{ // The left and right child nodes of the deleted node are not empty nodes. The deleted node and subsequent nodes will be replaced
		while (p_replace->p_left)
			p_replace = p_replace->p_left;

		void* temp = p_remove->p_key;
		p_remove->p_key = p_replace->p_key;
		p_replace->p_key = temp;

		p_remove->p_value = p_replace->p_value;
		p_replace->p_value = NULL;

		p_remove = p_replace;
	}
	if ((p_replace = !(p_replace = p_remove->p_left) ? p_remove->p_right : p_replace))
	{ // If one of the left and right child nodes of the deleted node is not empty, the deleted node and child node will be replaced
		void* temp = p_remove->p_key;
		p_remove->p_key = p_replace->p_key;
		p_replace->p_key = temp;

		p_remove->p_value = p_replace->p_value;
		p_replace->p_value = NULL;

		p_remove = p_replace;
	}

	if (!(p_parent = p_remove->p_parent)) // Delete node as root node
		p_tree->p_root = NULL;
	else
	{
		fixBeforeRemove(p_tree, p_remove); // You need to rebalance the tree before deleting nodes

		// Last delete node
		p_remove->p_parent = NULL;
		if (p_parent->p_right == p_remove)
			p_parent->p_right = NULL;
		else
			p_parent->p_left = NULL;
	}
	
	// Free up space for deleted nodes
	if (p_remove->p_key)
		free(p_remove->p_key);
	if (p_remove)
		free(p_remove);
	p_remove = p_remove->p_key = NULL;

	--p_tree->size;
	return 1;
}

void free_RBTree(RBTree *p_tree)
{
	if (!p_tree)
		return;

	for (RBNode *p_node = NULL; p_node = p_tree->p_root; )
		remove_RBTree(p_node->p_key, p_tree, NULL);
	
	free(p_tree);
	p_tree = NULL;
}

static int findNode(int(*p_kcmp)(void *, void *, char *), void *p_key, RBNode *p_curr, RBNode **p_res)
{
	if (!p_kcmp || !p_key || !p_res)
		return 0;

	RBNode *p_found = NULL;
	for (char compare = 0; p_curr && !p_found; )
	{
		if (!p_kcmp(p_key, p_curr->p_key, &compare))
			return 0;

		if (compare > 0)
			p_curr = p_curr->p_right;
		else if (compare < 0)
			p_curr = p_curr->p_left;
		else
			*p_res = p_found = p_curr;
	}

	return 1;
}

static void rotateLeft(RBTree *p_tree, RBNode *p_rotate)
{
	RBNode *p_right, *p_parent, *p_broLeft;

	if (!p_tree || !p_rotate || !(p_right = p_rotate->p_right)) // If the right child node of the rotation node is empty, you do not need to rotate and return directly
		return;

	// Set the right child node of the rotation node as the left child node of the right child node, and set the left child node parent node of the right child node as the rotation node
	if (p_broLeft = p_rotate->p_right = p_right->p_left)
		p_broLeft->p_parent = p_rotate;

	if (!(p_parent = p_right->p_parent = p_rotate->p_parent))
		// The parent node of the right child node is set as the parent node of the rotation node. If the parent node is empty, the right child node is set as the root node and the color is set to black
		(p_tree->p_root = p_right)->color = 1;
	else if (p_parent->p_left == p_rotate)
		p_parent->p_left = p_right;
	else
		p_parent->p_right = p_right;

	p_right->p_left = p_rotate;
	p_rotate->p_parent = p_right;
}

static void rotateRight(RBTree *p_tree, RBNode *p_rotate)
{
	RBNode *p_left, *p_parent, *p_broRight;

	if (!p_tree || !p_rotate || !(p_left = p_rotate->p_left))
		return;

	if (p_broRight = p_rotate->p_left = p_left->p_right)
		p_broRight->p_parent = p_rotate;

	if (!(p_parent = p_left->p_parent = p_rotate->p_parent))
		(p_tree->p_root = p_left)->color = 1;
	else if (p_parent->p_left == p_rotate)
		p_parent->p_left = p_left;
	else
		p_parent->p_right = p_left;

	p_left->p_right = p_rotate;
	p_rotate->p_parent = p_left;
}

static void fixAfterPut(RBTree *p_tree, RBNode *p_current)
{
	for (RBNode *p_parent, *p_gparent, *p_graLeft, *p_graRight; ; )
	{
		if (!(p_parent = p_current->p_parent)) // If the parent node is empty, the current node is the root node
		{
			p_current->color = 1;
			break;
		}

		if (p_parent->color || !(p_gparent = p_parent->p_parent)) // The parent node is black, or the grandfather node is empty (the parent node is the root node)
			break;

		if ((p_graLeft = p_gparent->p_left) == p_parent) // The parent node is the left child node of the parent node
		{
			if ((p_graRight = p_gparent->p_right) && !p_graRight->color) // The uncle node is not empty and is a red node
			{
				p_graRight->color = 1; // Set the node color to black
				p_parent->color = 1; // Set the parent node color to black
				p_gparent->color = 0; // Set the grandfather node color to red
				p_current = p_gparent; // Set the grandfather node as the current node
			}
			else // The uncle node is empty or black
			{
				if (p_current == p_parent->p_right) // The current node is the right child node of the parent node
				{
					rotateLeft(p_tree, p_current = p_parent); // Make the parent node the current node and rotate the current node to the left
					p_gparent = (p_parent = p_current->p_parent)->p_parent; // Reassign parent and grandfather nodes
				}
				p_parent->color = 1; // Set the parent node color to black
				p_gparent->color = 0; // Set the grandfather node color to red
				rotateRight(p_tree, p_gparent); // Rotate the parent node to the right
			}
		}
		else  // The parent node is the right child node of the parent node
		{
			if (p_graLeft && !p_graLeft->color)
			{
				p_graLeft->color = 1;
				p_parent->color = 1;
				p_gparent->color = 0;
				p_current = p_gparent;
			}
			else
			{
				if (p_current == p_parent->p_left)
				{
					rotateRight(p_tree, p_current = p_parent);
					p_gparent = (p_parent = p_current->p_parent)->p_parent;
				}
				p_parent->color = 1;
				p_gparent->color = 0;
				rotateLeft(p_tree, p_gparent);
			}
		}
	}
}

static void fixBeforeRemove(RBTree *p_tree, RBNode *p_current)
{
	for (RBNode *p_parent, *p_left, *p_right; p_current && (p_parent = p_current->p_parent); )
	{ // The current node is not empty, and the parent node of the current node is not empty
		if (!p_current->color)
		{
			/*
			 * If the current node is a red node:
			 * 1,The sibling node of the current node is empty;
			 * 2,Alternatively, the current node has a black sub node and a red sub node respectively, and the sub nodes of the red sub node are empty nodes or black nodes;
			 */
			p_current->color = 1;
			break;
		}
		/*
		 * Current node status:
		 * 1,The current node is not empty and is a black node
		 * 2,The sibling node of the current node is not empty
		 */
		if ((p_left = p_parent->p_left) == p_current) // If the current node is the left child of the parent node
		{
			if (!(p_right = p_parent->p_right)->color)
			{
				/*
				 * If the sibling node of the current node is a red node, then:
				 * 1,The parent node must be a black node;
				 * 2,The left and right child nodes of brother nodes must be black nodes;
				 */
				p_right->color = 1; // Set sibling node color to black
				p_parent->color = 0; // Set the parent node color to red
				rotateLeft(p_tree, p_parent); // Rotate the parent node to the left (the current node is still the left child of the parent node)
				p_right = p_parent->p_right; // Retrieve the sibling node of the current node
			}
			RBNode *p_broLeft = p_right->p_left, *p_broRight = p_right->p_right;
			if ((!p_broRight || p_broRight->color) && (!p_broLeft || p_broLeft->color))
			{ // If there is no red node in the left and right child nodes of the sibling node, the left and right child nodes of the sibling node are Nil nodes or black nodes
				p_right->color = 0; // Set the sibling node color to red
				p_current = p_parent; // Make parent node current
			}
			else // There must be a red sub node under the brother node
			{
				if (!p_broRight || p_broRight->color)
				{ // If the right child node of the sibling node is a Nil node or a black node, the left child node of the sibling node must be a red node
					p_broLeft->color = 1; // Set the color of the left child node of the sibling node to black
					p_right->color = 0; // Set the sibling node color to red
					rotateRight(p_tree, p_right); // Rotate sibling node right
					p_right = p_parent->p_right; // Retrieve the right child node
					p_broRight = p_right->p_right;
				}
				p_right->color = p_parent->color; // Set the color of the sibling node to the color of the parent node
				p_broRight->color = 1; // Set the color of the right child node of the sibling node to black
				p_parent->color = 1; // Set the parent node color to black
				rotateLeft(p_tree, p_parent); // Rotate parent node left
				break;
			}
		}
		else // The current node is the right child node
		{
			if (!p_left->color)
			{
				p_left->color = 1;
				p_parent->color = 0;
				rotateRight(p_tree, p_parent);
				p_left = p_parent->p_left;
			}
			RBNode *p_broLeft = p_left->p_left, *p_broRight = p_left->p_right;
			if ((!p_broLeft || p_broLeft->color) && (!p_broRight || p_broRight->color))
			{
				p_left->color = 0;
				p_current = p_parent;
			}
			else
			{
				if (!p_broLeft || p_broLeft->color)
				{
					p_broRight->color = 1;
					p_left->color = 0;
					rotateLeft(p_tree, p_left);
					p_left = p_parent->p_left;
					p_broLeft = p_left->p_left;
				}
				p_left->color = p_parent->color;
				p_broLeft->color = 1;
				p_parent->color = 1;
				rotateRight(p_tree, p_parent);
				break;
			}
		}
	}
}
  • Test case code C:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "RBTree.h"

#define _VALUE_SIZE 20

static int kcmp(void *p_key1, void *p_key2, char *p_res)
{
	int compare = *((int *)p_key1) - *((int *)p_key2);
	if (compare > 0)
		*p_res = 1;
	else if (compare < 0)
		*p_res = -1;
	else
		*p_res = 0;
	return 1;
}

RBTree *init_RBTree(int n_size, int max_key)
{
	RBTree *p_tree = NULL;
	p_tree = create_RBTree(kcmp);
	if (!(p_tree = create_RBTree(kcmp)))
	{
		printf("Error creating red black tree\n");
		return NULL;
	}

	int *p_key = NULL;
	char *p_value = NULL;
	srand((unsigned int)time(NULL));
	for (int i = 0; i < n_size; ++i) {
		if (!(p_key = (int *)malloc(sizeof(int))))
		{
			printf("open up key Space failure\n");
			return p_tree;
		}
		if (!(p_value = (char *)malloc(_VALUE_SIZE)))
		{
			if (!p_key)
				free(p_key);
			p_key = NULL;
			printf("open up value Space failure\n");
			return p_tree;
		}
		_itoa_s((*p_key = rand() % max_key), p_value, _VALUE_SIZE, 16);
		if (!put_RBTree(p_key, p_value, p_tree))
		{
			printf("Failed to insert node into red black tree\n");
			return p_tree;
		}
	}

	return p_tree;
}

void testFind_RBTree()
{
	RBTree *p_tree = NULL;
	if (!(p_tree = init_RBTree(100, 1000)))
	{
		printf("Red black tree initialization failed\n");
		return;
	}
	RBNode *p_root = p_tree->p_root;
	printf("Red black tree initialized successfully: root_key=%d, size=%d\n", *((int *)p_root->p_key), p_tree->size);

	srand((unsigned int)time(NULL));
	int key = rand() % 1000;
	void *p_value = NULL;
	find_RBTree(&key, p_tree, &p_value);
	if (p_value)
		printf("key=%d, value=%s\n", key, (char *)p_value);
	else
		printf("key=%d, value=NULL\n", key);

	free_RBTree(p_tree); // Release red and black trees
}

void testPutAndRemove_RBTree()
{
	RBTree *p_tree = NULL;
	if (!(p_tree = init_RBTree(100, 1000)))
	{
		printf("Red black tree initialization failed\n");
		return;
	}
	RBNode *p_root = p_tree->p_root;
	printf("Red black tree initialized successfully: root_key=%d, size=%d\n", *((int *)p_root->p_key), p_tree->size);

	char isRBTree = 0;
	for (int i = 0; i < 20; ++i)
	{
		RBNode *p_node = p_tree->p_root;
		if (p_node)
		{
			printf("delete[root_key=%d]After,", *((int *)p_node->p_key));
			remove_RBTree(p_node->p_key, p_tree, NULL);
			is_RBTree(p_tree, NULL, &isRBTree);
			printf("p_tree[%s]A red black tree, size=%d\n", isRBTree ? "still" : "no", p_tree->size);
		}
	}
	
	free_RBTree(p_tree); // Release red and black trees
}

int main(void)
{
	testPutAndRemove_RBTree();
	//testFind_RBTree();

	system("pause");
	return EXIT_SUCCESS;
}

 

Tags: Java C data structure

Posted by kolanos7 on Tue, 10 May 2022 14:03:36 +0300