IDEA plug-ins commonly used by programmers: github.com/silently952…

Wechat official account: Beta learning Java

preface

In the last article, we used binary trees as an implementation of Map, and finally analyzed the time complexity and worst-case scenario of this version; In this article, we will use red-black trees to implement Map, which improves the binary tree version in the previous article. The definition of the Map interface and the common methods implemented, such as the binary tree lookup method (GET), will not be repeated; Implement Map based on binary tree

Red-black tree is one of the most difficult knowledge points in data structure, although it is rarely used in actual business development work, but it is a favorite knowledge point of interviewers.

I have read a lot of articles about red black trees before, but most of them are from the properties of red black trees, not from the theoretical model of red black trees, so red black trees are difficult to understand.

It is necessary to understand and master the red-black tree. Java HashMap converts a linked list into a red-black tree when the number of nodes exceeds 8. The TreeMap base layer also uses red-black trees;

Red-black trees are almost perfectly balanced compared to the binary trees we discussed in the last article, and are able to ensure that the running time of operations is logarithmic

Before learning red black trees, let’s take a look at the properties of red black trees. For each property, we need to ask a Why, with questions to learn red black trees; If we understand these problems, then we understand the nature of red-black trees, but we are still a little far from implementation.

  • Property 1. The node is red or black. (Why: Why do nodes distinguish colors, and what is the function of red nodes?)
  • Property 2. The root is black. (Why: Why the root node must be black)
  • Nature 3. All leaves are black. (according to)
  • Property 4. There cannot be two consecutive red nodes on all paths from each leaf to the root. (why)
  • Property 5. All paths from each leaf of any node contain the same number of black nodes. (why)
  • Property 6. Every new node inserted must be red (why)

Balanced search tree

Red-black trees are approximately balanced binary trees. The theoretical model corresponding to red-black trees can be 2-3 trees or 2-3-4 trees. So before learning red-black trees, we need to know about 2-3 trees and 2-3-4 trees.

The relationship between red-black trees and 2-3 and 2-3-4 trees is like the relationship between interfaces and implementation classes; 2-3 trees are interfaces to 2-3-4 trees, while red-black trees are interface-based implementations

Two – three, two – three-four are all special cases of B

2-3 tree

In order to ensure the absolute balance of the tree, the nodes in the tree are allowed to store multiple keys. In 2-3 trees, one node can have two links with one key value, and the same node is allowed to contain up to two keys and three links.

2-3 Tree is shown as follows:

To find the

The search process of a 2-3 tree is similar to that of a binary tree. The search key is compared with the key in the node. If a node with the same search key is encountered, the search is hit. Otherwise, continue to search in the corresponding subtree. If an empty link is encountered, the search is not hit.

insert

  • Insert a key into a node with a single key: The current node has only one key. Add a key directly to the current node

  • Insert a new key into a node with a double key: Insert a new key into the current node, if the current node has more than two keys

  • Insert into a node whose parent is also a double key

Through the demonstration of the three cases above, we find that the growth of 2-3 trees is different from that of standard binary trees. The growth of binary trees is from top down, while the growth of 2-3 trees is from bottom up.

In the last article on binary trees, we found that the worst case is when the nodes are inserted in order, causing the binary tree to degenerate into a linked list, and the performance of the binary tree decreases. Let’s use 2-3 tree sequential insertion to see how, for example, insert 1,2,3,4,5,6,7

From this we can see that in the worst case 2-3 trees are perfectly balanced and have good performance. But this is theory, and there is still a long way to go

Left-leaning red-black tree based on 2-3 tree implementation

After understanding the theoretical model 2-3 tree of red-black tree, we can realize our red-black tree based on 2-3 tree.

Since there are nodes with double bonds in the 2-3 tree, and since we need to represent nodes with double bonds in the binary tree, we need to add a color attribute color to the node. If the node is red, it means that the current node and the parent node together constitute the nodes with double bonds in the 2-3 tree.

Make some changes to the nodes of the binary tree in the previous article. The code is as follows:

class Node implements TreeNode { public static final boolean RED = true; public static final boolean BLACK = false; public K key; public V value; public Node left; public Node right; public boolean color; Public int size = 1; Public Node(K key, V value, Boolean color) {this.key = key; this.value = value; this.color = color; } @Override public Node getLeft() { return this.left; } @Override public Node getRight() { return this.right; } @Override public Color getColor() { return color ? Color.RED : Color.BLACK; }}Copy the code

Because red black trees themselves are binary trees, so the binary tree search method implemented in the last article can be directly applied to red black trees without any modification.

In this paper, we implemented the 2-3 tree red-black tree reference algorithm 4, and we stipulate that the red node can only appear in the left node, namely left-leaning red-black tree. Why do red nodes only appear on the left node? In fact, the right side is also ok, only the left node is allowed because it reduces the number of possible cases and requires relatively little code to implement.)

Red-black tree properties explained

Red black tree as the realization of 2-3 trees, based on 2-3 trees to see the nature of red black tree is not dry meanness agreement, also do not need to forcibly memory.

  • Property 1. The node is red or black. (Why: Why do nodes distinguish colors, and what is the function of red nodes?)

As we have explained above, the main purpose of color differentiation is to represent the situation of the two-bond nodes in the binary tree of 2-3. If the node is red, it means that the current node and the parent node together form a number of 2-3 double bonds. Black nodes represent ordinary nodes in a binary tree

  • Property 2. The root is black. (Why: Why the root node must be black)

The root node itself has no parent node and cannot form a 2-3 tree double bond, so it cannot be a red node.

  • Nature 3. All leaves are black. (according to)

The leaves mentioned here are actually empty links, hollow links are not drawn in the above figure.

  • Property 4. There cannot be two consecutive red nodes on all paths from each leaf to the root. (why)

This property is understood again based on the role of red nodes. If there are two consecutive red nodes, then the node with three bonds with the parent node, but this is not allowed in the left-leaning red-black tree of 2-3 tree implementation. (Three keys are allowed in red-black trees based on a two-three-four tree implementation, but only with one red node on the left and right, and not consecutively, as explained in a later extension.)

  • Property 5. All paths from any node to each of its leaves contain the same number of black nodes. (why)

This property can be understood based on the theoretical model of 2-3 trees. Because red nodes represent the height of the parent node, only black nodes contribute to the height of the tree in a red-black tree, so all paths from any node to each of its leaves contain the same number of black nodes

  • Property 6. Every new node inserted must be red (why)

This property does not appear in Baidu Encyclopedia, but it can be seen on some foreign websites. I think it is also helpful to understand red black tree, so I add it here. Above we have demonstrated the 2-3 tree insert key process, first insert the key to the node, and then determine whether to split, because the first insert build to the current node of the 2-3 tree double bond or 3 key, and only through the use of red in the red and black tree nodes and the parent node of the 2-3 tree double bond or 3 key, so every time the newly inserted node must be red.

2-3 trees are represented in left – leaning red – black trees

  • Representation of a single key node in a 2-3 tree in a red-black tree

  • The representation of the double bond node in a 2-3 tree in a red-black tree, since it’s a left-leaning red-black tree, only the red node appears on the left

It might not be intuitive to just look at the nodes, but how can a 2-3 tree be represented as a left-leaning red-black tree

When we drag the red node to the same height as the parent node, we can compare it with the 2-3 tree and find that the red-black tree represents the 2-3 tree very well

Determine the color of the node

I need to define a method to determine what color the node is, return true if it’s red, false otherwise, okay

protected boolean isRed(Node node) {
    if (Objects.isNull(node)) {
        return Node.BLACK;
    }
    return node.color;
}
Copy the code

rotating

When inserting or deleting a red-black tree, there may be red nodes on the right or two consecutive red nodes. In these cases, we need to complete the repair by rotation operation.

Since the link of the parent node needs to be modified after the rotation operation is complete, the rotation method we defined needs to return to the rotated node to reset the link of the parent node

  • left-handed

The left-handed code is implemented as follows:

protected Node rotateLeft(Node h) { Node x = h.right; h.right = x.left; x.left = h; x.color = h.color; h.color = Node.RED; size(h); // Count the number of subtree nodes size(x); return x; }Copy the code

Respecify the links of the left and right subtrees of the two nodes and change the color of the nodes. The second is to calculate the number of nodes contained in each subtree. The calculation method is similar to the size implementation of binary tree in the previous article, which will not be repeated here. Please refer to “Implementing Map Based on Binary Tree”.

  • Right hand

The right-handed code is implemented as follows:

protected Node rotateRight(Node h) {
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = Node.RED;

    size(h);
    size(x);

    return x;
}
Copy the code

discoloration

In a 2-3 tree, when the key value of the node reaches 3, it needs to be split, and one node will float up. So how do you represent this operation in a red-black tree?

In red-black tree, node splitting is actually the change of node color. The red-black tree after a left-handed right-handed will eventually reach the parent node is black, around two child nodes is red (later can see details of the changes of the insert), the state is corresponding to the three key nodes in the 2-3 tree, then divided operation is the color of the left and right two child nodes into black, the parent node to become red.

The code implementation is as follows:

Protected void upSplit(Node Node) {if (objects.isnull (Node)) {return; } node.left.color = Node.BLACK; node.right.color = Node.BLACK; node.color = Node.RED; }Copy the code

insert

Insert to the single-key node
  1. If the inserted key is smaller than the current node’s key value, a new red left node is added

  1. If the inserted key is greater than the current node’s key value, then a red right node is inserted. Since only red nodes are allowed on the left, we need to left-rotate once

Insert into a double-bond node
  1. There are three ways to insert a new key into a double-key node. Let’s look at the simplest case first, where the value of the key is the largest. After the insertion, we only need to change the color

  1. In the second case, you insert the smallest key value, and then you insert two red nodes, so you rotate right, and then you change color

  1. In the third case, the key is inserted between the original two keys, so you need to rotate first left, then right, and finally change color

Based on the analysis of the above situations, we can conclude a unified rule of change:

  • If the right child is red and the left child is black, then left-rotation is performed
  • If the left child is red and his left child is red, then he goes right
  • If the left and right child nodes are red, the color switch is performed

The graph changes as follows:

After the above analysis we can now code to implement the red-black tree insert operation

@Override public void put(K key, V value) { if (Objects.isNull(key)) { throw new IllegalArgumentException("the key can't null"); } root = put(root, key, value); root.color = Node.BLACK; } private Node put(Node node, K key, V value) { if (Objects.isNull(node)) { return new Node(key, value, Node.RED); } int compare = key.compareTo(node.key); if (compare > 0) { node.right = put(node.right, key, value); } else if (compare < 0) { node.left = put(node.left, key, value); } else { node.value = value; } if (isRed(node.right) && ! isRed(node.left)) { node = rotateLeft(node); } if (isRed(node.left) && isRed(node.left.left)) { node = rotateRight(node); } if (isRed(node.left) && isRed(node.right)) { upSplit(node); } size(node); return node; }Copy the code

Since the root node must be black, so as to prevent the root node from turning red due to the color-changing operation, we set the root node to black after the insertion operation.

The first half of the red-black tree insertion operation is the same as the binary tree insertion operation implemented in the previous article. The only difference is the last three if operations, which are the code implementation of the uniform change rule summarized above.

The first if judgment handles if the right node is red and the left node is black, then left-rotation is performed

The second if judgment handles if the left node is red and its left node is also red, then the right rotation is performed

The third if determines that if both the left and right child nodes are red, then the color change is performed

delete

Deleting can be more troublesome than inserting because it can cause tree imbalance and possibly destroy the nature of red-black trees.

First of all, we need to go back to the theoretical model of 2-3 trees. If the node we delete is currently a double-bond node, we can directly delete it, and the height of the tree will not change its structure. Therefore, the key to delete a red-black tree is to ensure that the node to be deleted is a double-key node.

In the delete operation we will also achieve the color-changing operation, which is the opposite of the color-changing operation of the insert, with the parent node turning black and the two children turning red

protected void flipColors(Node h) { h.color = ! h.color; h.left.color = ! h.left.color; h.right.color = ! h.right.color; }Copy the code

Before the formal implementation of the deletion operation, we first discuss the red black tree deletion minimum and maximum situation, the final implementation of the deletion operation will also use the deletion minimum and maximum value

Delete minimum

The minimum value for binary tree deletion is to search through the left subtree of the tree until a node whose left subtree is null is deleted

The red-black tree similar to the deletion of the minimum, but we need to ensure that node is a double bond is to be deleted, so in the recursive to each node is a double bond is all need to keep the current node, then at the end to find the minimum value will be in a double bond node (because of recursive when already keep the parent node is double bond node).

So what if the current recursive node is guaranteed to be a double-bonded node? There are three scenarios:

  • The left child of the current node is a double-key node, deleted directly

  • The left child of the current node is a single-key node, but its brother is a double-key node, so move a node to the left child by rotation to form a double-key node, and then delete the node

  • The left and right child nodes of the current node are single-key nodes, so the parent node and the parent node form a three-key node through discoloration, and then delete the node

The above are all the cases in which the minimum value of red-black tree will be deleted. For the last two cases, for the sake of simple code implementation, we consider merging these two cases;

Change the initial root node to red, then change the color, then check whether Node.right. Left is red, if so, rotate it

The code for removing the minimum is as follows:

private Node moveToRedLeft(Node h) { flipColors(h); if (isRed(h.right.left)) { h.right = rotateRight(h.right); h = rotateLeft(h); flipColors(h); } return h; } @Override public void deleteMin() { if (isEmpty()) { throw new NoSuchElementException("BST underflow"); } if (! isRed(root.left) && ! isRed(root.right)) { root.color = Node.RED; } root = deleteMin(root); if (! isEmpty()) { root.color = Node.BLACK; } } private Node deleteMin(Node h) { if (h.left == null) { return null; } if (! isRed(h.left) && ! isRed(h.left.left)) { h = moveToRedLeft(h); } h.left = deleteMin(h.left); return balance(h); } private Node balance(Node h) { if (isRed(h.right) && ! isRed(h.left)) { h = rotateLeft(h); } if (isRed(h.left) && isRed(h.left.left)) { h = rotateRight(h); } if (isRed(h.left) && isRed(h.right)) { flipColors(h); } h.size = size(h.left) + size(h.right) + 1; return h; }Copy the code

After deleting the minimum value, we need to rebuild the red-black tree, because our previous operation may lead to the existence of 3-key nodes, and after deleting, we need to re-decompose 3 to build nodes. Balance in the above code is a reworking of the red-black tree.

Delete maximum value

The idea of deleting the maximum value is similar to the idea of deleting the minimum value

To delete the maximum value, you need to borrow a node from the left node, and the code is as follows:

@Override public void deleteMax() { if (isEmpty()) { throw new NoSuchElementException("BST underflow"); } if (! isRed(root.left) && ! isRed(root.right)) { root.color = Node.RED; } root = deleteMax(root); if (! isEmpty()) { root.color = Node.BLACK; }} private Node deleteMax(Node Node) {if (isRed(node.left)) { So let's borrow a node to the right. Node = rotateRight(node); } if (Objects.isNull(node.right)) { return null; } if (! isRed(node.right) && ! isRed(node.right.left)) { node = moveToRedRight(node); } node.right = deleteMax(node.right); return balance(node); } private Node moveToRedRight(Node node) { flipColors(node); if (isRed(node.left.left)) { node = rotateRight(node); flipColors(node); } return node; }Copy the code

Delete any node

The same transformation as the deletion minimum on the search path can ensure that any current node will not be a double-key node during the search.

If the key is on the left node, a change similar to deleting the minimum is performed, borrowing the node from the right;

If the key is on the right node, a change similar to deleting the maximum value is performed, borrowing the node from the left.

If the node to be deleted handles leaf nodes, it can be deleted directly. If it is a non-leaf node, then the left subtree is not empty and swaps with the maximum value in the left subtree, and then deletes the maximum value in the left subtree. If the left subtree is empty, swaps with the minimum value in the right subtree, and deletes the minimum value in the right subtree.

The code implementation is as follows:

@Override public void delete(K key) { if (isEmpty()) { throw new NoSuchElementException("BST underflow"); } if (! isRed(root.left) && ! isRed(root.right)) { root.color = Node.RED; } root = delete(root, key); if (! isEmpty()) { root.color = Node.BLACK; } } private Node delete(Node node, K key) { int compare = key.compareTo(node.key); If (compare < 0) {// find if (! isRed(node.left) && ! isRed(node.left.left)) { node = moveToRedLeft(node); } node.left = delete(node.left, key); } else if (compare > 0) {if (isRed(node.left)) {node = rotateRight(node); } if (! isRed(node.right) && ! isRed(node.right.left)) { node = moveToRedRight(node); } node.right = delete(node.right, key); } else { if (Objects.isNull(node.left) && Objects.isNull(node.right)) { return null; } if (objects.nonnull (node.left)) {// the left subtree is not empty node Max = Max (node.left); node.key = max.key; node.value = max.value; node.left = deleteMax(node.left); } else {// Right subtree is not empty Node min = min(node.right); node.key = min.key; node.value = min.value; node.right = deleteMin(node.right); } } return balance(node); }Copy the code

Draw a red-black tree to verify the implementation

Above we have implemented the main code for red-black trees, but the best way to verify that our red-black tree is really a red-black tree is to draw a red-black tree based on the version we have implemented, and then verify the properties of the red-black tree

Since how to draw a red-black tree is not the focus of this article, so I will not post the code, friends who need to go to the warehouse to check;

Write units to test the Map we implemented using red-black trees, and draw the red-black tree to verify that it works

@Test public void testDelete() throws IOException { RedBlack23RedBlackTreeMap<Integer, String> map = new RedBlack23RedBlackTreeMap<>(); map.put(8, "80"); map.put(18, "180"); map.put(5, "50"); map.put(15, "150"); map.put(17, "170"); map.put(25, "250"); map.put(40, "40"); map.put(80, "80"); map.put(30, "30"); map.put(60, "60"); map.put(16, "16"); map.draw("/Users/huaan9527/Desktop/redBlack4.png"); // Draw the red-black tree before deleting map.delete(40); map.delete(17); map.delete(25); map.nodes().forEach(System.out::println); / / print out according to the key since the childhood order node map. The draw ("/Users/huaan9527 / Desktop/redBlack5. PNG "); // Draw the deleted red black tree}Copy the code

Prints the results of node execution in sequence:

Delete the previous red-black tree

Deleted red black tree

conclusion

This article mainly discusses the red-black tree version based on 2-3 trees. Understanding and mastering the content of this article will also master the red-black tree, which is not false at all in the interview.

In order to deepen the understanding of red-black trees, you can implement red-black trees based on 2-3-4 trees by yourself. To compare the versions of the two red-black trees, you can refer to the code in my Git repository

All the source code has been put into github repository: github.com/silently952…

Give a red black tree site demonstration, the site to achieve a red black tree and the way we achieve this is different, we can refer to: www.cs.usfca.edu/~galles/vis…

Finally (pay attention, don’t get lost)

There may be more or less deficiencies and mistakes in the article, suggestions or opinions are welcome to comment and exchange.

Finally, writing is not easy, please do not white whoring I yo, I hope friends can point comment attention to three even, because these are all the power source I share 🙏