Interview old Enemy: Red and black Tree

After reading this article, you will know:

As we mentioned in the previous article “Revisiting Data Structures: Finding, inserting, and deleting binary sort trees”, the performance of binary sort trees depends on the number of levels of the tree:

• The best case is O(logn), which exists in the case of a complete binary sorting tree, and its access performance is approximately half search;
• The worst case is O(n), such as when the inserted elements are ordered and the resulting binary sort tree is a linked list, in which case all the elements need to be traversed (see figure b below).

In order to address the shortcomings of sorted binary trees, Rudolf Bayer invented another improved sorted binary tree in 1972: Red-black trees, which he called “symmetric binary B-trees”, were first proposed by Leo J. Guibas and Robert Sedgewick in 1978.

This paper introduces the basic properties and operations of red black tree.

What is a red-black tree

Red-black tree is essentially a binary search tree, but it adds an extra mark (color) on the basis of the binary search tree, and has certain rules. These rules allow red-black trees to be balanced, with worst-case complexity O(logn) for insertion, deletion, and lookup.

Its statistical performance is better than balanced binary trees (AVL trees), so red-black trees are used in many places. For example, in the Java Collections framework, many parts (HashMap, TreeMap, TreeSet, etc.) have red-black tree applications, and these collections provide good performance.

Since TreeMap is implemented by red-black tree, this paper will use the code of TreeMap related operations to analyze and demonstrate.

Black height

Five characteristics of red-black trees

The red-black tree adds the following requirements on the basis of the original binary search tree:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

What it means in Chinese:

1. Each node is either red or black;
2. The root node is always black;
3. All leaf nodes are black (note that leaf nodes are NIL nodes in the figure above);
4. Both children of each red node must be black;
5. The path from any node to each leaf node in the subtree contains the same number of black nodes;

Note: Property 3 specifies that every leaf node of a red-black tree is empty, and no leaf node is black. But the Red-black tree implemented in Java will use NULL to represent empty nodes, so walking through a red-black tree will see no black leaf nodes, but instead every leaf node will be red.

Property 4 means: there are no two consecutive red nodes on the path from each root to node, but black nodes can be consecutive. Therefore, given the number of black nodes N, the shortest path case is N consecutive black, the height of the tree is n-1; The longest path has red and black nodes and the height of the tree is 2(n-1).

Property 5 is the most important condition for being a red-black tree, and subsequent insert and delete operations are to comply with this rule.

Red-black tree is not a standard balanced binary tree, it uses property 5 as a balancing method to improve its performance.

Red black tree left – right rotation

Specify left rotation of node X:

Private void rotateLeft(Entry p) {if (p! = null) { Entry r = p.right; // p is x, r is y. // After left-spin, the right subtree of x becomes the left subtree of y β if (r.eft! = null) r.left.parent = p; //β confirms father as X. r.parent = P. parent; If (p.parent == null) // If (p.parent == null) // If (p.parent == null) // If (p.parent == null) Else if (p.p arent. Left = = p) / / if x has the father and it is my father's left child, now recognize y x father left children, don't x the p.p arent. Left = r; Else // If x is the father's right child, the father recognizes y as the father's right child and discards x p.arent. right = r; r.left = p; // the old father x is now its left child. }}Copy the code

As you can see, the left rotation of the x node is turning x into the right child of y, and giving the left child of Y to X as the right subtree.

Simply put, left-rotation moves a node (β) from the right subtree to the left subtree.

Specify the right rotation of node Y:

private void rotateRight(Entry p) { if (p ! = null) { Entry l = p.left; p.left = l.right; if (l.right ! = null) l.right.parent = p; l.parent = p.parent; if (p.parent == null) root = l; else if (p.parent.right == p) p.parent.right = l; else p.parent.left = l; l.right = p; p.parent = l; }}Copy the code

Balanced insertion in a red-black tree

Red-black tree insertion is mainly divided into two steps:

• First, as with binary search tree insert, search, insert
• Then adjust the structure to make sure it meets the red-black tree state
  
  
  • Recolor the node
  • And perform related rotation operations on the tree

On the basis of binary search tree insertion, in order to restore the balance, the insertion repair operation is continued.

Insertion of binary lookup tree

Adjust the red-black tree structure after insertion

The fifth feature of a red-black tree states that the path from any node to each leaf node of its subtree contains the same number of black nodes. That is, when we insert a black node into a red-black tree, we violate this feature.

Meanwhile, the fourth feature stipulates that the children on the left and right of the red node must be black nodes. When we insert a red node under a red node, this feature will be violated.

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

Adjust the thought

[There are two cases of adjustment after insertion and red dye:]

Case 1. Both the father node and the uncle node are red:

Suppose node N is inserted, then the father node P and uncle node U are red, and the grandfather node G must be black.

The child of the red node cannot be red. In this case, no matter whether N is the left child or the right child of P, both P and U should be dyed black and G red. So this subtree has the same number of blacks on the left and right, and it also satisfies feature 4.

But after this change, G becomes red. If G’s father is red, doesn’t it violate feature 4? This problem is the same as after we insert and dye it red, so we need to take the grandfather node G as the new adjustment node, adjust the operation again, and then cycle until the father node is not red, there is no problem.

Case 2. The father node is red and the uncle node is black:

Suppose node N is inserted, then the parent node P is red, the uncle node U is black, and the grandfather node G must be black.

The child of the red node cannot be red, but the parent node P cannot be black either, because this path has an extra black node. What to do?

Since can’t change you, that we don’t, I change a more suitable for me!

How do we get rid of P? By turning the grandparent G right, P becomes the root of the subtree, and G becomes the right subtree of P.

After dextral rotation, G goes to the right subtree, then turn P into black, with a black node, and then turn G into red, and then balance!

So what we’re doing is we’re inserting node N into the left child of the parent node P, and if N is the right child of P, we’re going to have to do one more left rotation to solve the situation.

N is the child to the right of P, and if you rotate P to the left, you get this.

Verify this procedure with TreeMap’s code:

private void fixAfterInsertion(Entry x) { x.color = RED; // While (x! = x! = x! = x! = x! = null && x ! Color == RED) {if (parentOf(x) == leftOf(parentOf(x)))) {// Insert the parent node of node X into the left child Entry y = rightOf(parentOf(parentOf(x))); SetColor (parentOf(x), BLACK); if (parentOf(x) == RED) {setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else {// If the uncle node y is not red, we need to right-rotate the parent node to become the root node, the grandfather node to go to the right subtree, then the father node to become black, the grandfather node to become red // special case: If (x == rightOf(parentOf(x))) {x = parentOf(x); rotateLeft(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); Y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == leftOf(parentOf(x))) { x = parentOf(x); rotateRight(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } root.color = BLACK; }Copy the code

Red black tree balance removed

The insertion balance of red-black tree needs to be well understood. If you do not understand it before, the adjustment balance after deletion is even more difficult to understand.

Deletion of red-black trees is also a two-step process:

1. Deletion of binary lookup tree
2. Structural adjustment

Deletion of binary lookup tree

Structure adjustment after deletion

According to the fifth property of red-black trees:

If the node to be deleted is red, its deletion does not damage the properties of the current tree. If the deleted node is black, further adjustments are required to ensure that the subsequent tree structure meets the requirements.

This is the case where the black nodes are deleted.

Adjust the thought

[There are three main steps for adjustment after deletion] :

The first step:

• If the brother is red, it means the children are black[Rotation case 1]
  
  
  • Turn your brother black
  • Father made it red
  • Left rotation father (hey hey, brother give me a black child)
  • Now compare the rotated brothers

Step 1 Explanation:

The goal of this step is to turn the sibling node black into one of the two situations in step 2.

The tree remains in its original equilibrium until further changes are made.

Step 2, there are two situations:

Case 1: The children of sibling nodes are all black

• Turn a brother red
• Continue next wave (this subtree is done, explore the parent node, go to the next tree, go to step 3)

Step 2 Situation 1 Explanation:

Here after brother nodes become red, from its parent node to all paths are unified under the less one, also does not affect other characteristics at the same time, but after their brother nodes become red, if there is a father node is red, 4 May violate the red-black tree characteristics, therefore need a identification, adjust to a higher level of the tree.

Case 2: At most one child of the sibling node is black

• Blackened the kid who wasn’t black[Rotation 2]
  
  
  • Brother get red
  • Brother right rotation
  • Then compare the rotated brother
• Paint your brother the same color as your father
• And then he blackened his father
• Blackened my brother’s right kid
• The parent node is left-handed
• Investigate the root node and proceed to step 3

Step 2 Situation 2 Explanation:

In case 2 of rotation, the left and right children of the sibling node are moved to the right for subsequent operations, as shown in the figure below:

The rotation of case 3 moves the sibling’s child to the left, while the black parent changes to the left, as shown below:

Step 3:

• If you’re not looking at the root node and it’s black, go back to the first step and look at the upper tree;
• Exit if you’re looking at the root node or if the node isn’t black
  
  
  • I’m going to color this node in black.

Step 3 Explanation:

The root node is selected as the end mark in the third step, because in the second step, it may happen that we just add a black node to the subtree that deleted the black node without affecting other subtrees. At this time, our adjustment has been completed, and we can directly set the adjustment node x = root, which is equal to declaring the end of adjustment.

Because what we’re doing right now is maybe we’re just adjusting the middle of a tree, maybe we have a parent here, all the way up to the root. The current subtree is missing a black node, it is not enough to ensure that the whole is qualified.

There needs to be a guarantee in the code. Let’s say that B is already red. So the adjustment is complete, and finally I will color B, the node that the adjustment target x points to, black. This ensures that the black node is replaced.

The four cases discussed earlier occur when the current node is the left child of the parent node. If the current node is the right child of the parent node, the corresponding symmetric operation can be performed, and the process is the same.

The specific rotation direction is determined by the left/right position of the adjusted node on the parent node.

Verify this procedure with TreeMap’s code:

private void fixAfterDeletion(Entry x) { while (x ! = root && colorOf(x) == BLACK) { if (x == leftOf(parentOf(x))) { Entry sib = rightOf(parentOf(x)); If (colorOf(sib) == RED) {setColor(sib, BLACK); setColor(parentOf(x), RED); rotateLeft(parentOf(x)); sib = rightOf(parentOf(x)); } if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib), BLACK); setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; }} else {Entry sib = leftOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib), BLACK); setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x, BLACK); }Copy the code

conclusion

Red black trees are not really balanced binary trees, but in practical applications, the statistical performance of red black trees is higher than that of balanced binary trees, but the extreme performance is slightly worse.

The insertion and deletion adjustment logic of red-black tree is complicated, but the ultimate goal is to satisfy the five characteristics of red-black tree, especially 4 and 5.

In order to simplify the operation, we directly color the inserted node red, as long as the parent of the inserted node is not red.

In the adjustment after deletion, a node is missing in the subtree where the black node is deleted, which needs to be compensated or a black node is damaged to others. The specific adjustment method depends on the subtree of the sibling node.

The insertion and deletion of red-black trees are complicated and difficult to understand in tree data structures, but just remember that red-black trees have special balancing rules, and to maintain balance, we rotate or color according to the condition of the neighboring trees.

There must be something special about red-black trees that are so hard to understand. Its ordered, fast features are useful in many scenarios, such as TreeMap, TreeSet, and so on from the Java Collections framework.

Thanks