6 k word | red and black tree red and black fruit, red and black tree introduction to you and me – a red-black tree

Red-black tree is a common self-balanced binary search tree, which is often used in associative arrays and dictionaries. It is widely used in low-level implementations of various languages. Java TreeMap and TreeSet are implemented based on red-black tree. This post will explain the definition, creation and use of red-black trees.

I. Definition of red-black tree

(1) Each node is either black or red.


(2) The root node is black.


(3) Each leaf node is black.


(4) If a node is red, its children must be black


(5) From any node to the leaf node, the black node is the same.

I direct copy in the period of introduction to algorithms for the description of a red-black tree, a lot about the interpretation of a red-black tree, and I begin to copy a blunt description, confusing, and hope to be able to this note 1, gradual lead readers to understand the red-black tree, so we will speak of from the meaning of a red-black tree, why do we need a red-black tree.

Balanced binary search tree

Let’s build a binary search tree using such an array [42, 37, 18, 12, 11, 6, 5]. Since any point in the array can be the root of the binary search tree, this tree is not unique. Let’s take an extreme example (insert elements sequentially with 42 as the root).

In this example, the binary search tree degenerates into a linked list, and the search time complexity is O(n), losing its meaning as a binary search tree. To keep the binary search tree from being too “skewed”, we need to build a balanced binary search tree

It can be seen that the search time complexity of balanced binary search tree is O(logn), which avoids the possible degradation into linked list caused by randomly selecting root nodes to build binary search tree. Here is the official definition of a balanced binary search tree:

Balanced binary search tree: short for balanced binary tree. Is a highly balanced binary tree proposed by the former Soviet Union mathematicians Adelse Velskil and Landis in 1962, also known as AVL tree according to the English name of scientists. It has the following properties:


Property 1. Can be an empty tree.


Property 2 If the tree is not empty, the left and right subtrees of any node are balanced binary trees, and the absolute value of the difference in height is not more than 1

(If you are not familiar with the concept of balanced binary search trees, you are advised to consult the relevant documentation. This note will not cover balanced binary search trees in detail.)

From the above example, we can see that the key to building a balanced binary search tree is to choose the “right” root node. So how can we choose the right root node every time we build a balanced binary search tree? Here we use another important tree: 2-3 trees (pronounced 2-3 trees), 2-3 trees are equivalent to red black trees, and understanding 2-3 trees is very helpful in understanding both red black trees and Class B trees.

Basic concepts of 2-3 trees

The so-called 2-3 tree is a tree that meets the nature of binary search tree, and the node can store one element or two elements, and each node has two or three children.

Properties 1. Meet the properties of binary search tree


Property 2. A node can hold one or two elements


Property 3. Each node has two or three child nodes

A 2-3 tree is also essentially a search tree, different from a binary search tree in that 2-3 nodes may hold two elements and each node may have three child nodes. There are two types of nodes in a 2-3 tree: 2-node (with two children) and 3-node (with three children)

2-3 tree creation

Let’s see how to create a 2-3 tree. The rules for creating 2-3 trees are as follows:

Rule 1. When a new node is added, it is not added to the empty position, but to the last leaf node


Rule 2. Four nodes can be decomposed into a tree consisting of three 2-nodes, and the root node of the new tree must be merged upward with the parent node after decomposition

Let’s still use the example array above [42,37,18,12,11,6,5] and still use sequential insertion to build 2-3 trees to see if we degenerate into a linked list.

Notice that at each step of the creation of the 2-3 tree, the entire tree is always in balance. Since the 2-3 tree has been able to maintain the balance, why we need a red and black tree, this is because the 2-3 tree each node storing 1 ~ 2 elements, and the nature of the fusion node split up is not easy to code, so we hope that through some of the rules, the 2-3 tree into a binary tree, and the converted binary tree can still keep balance.

Equivalence between 2-3 trees and red-black trees

In this section, we take a 2-3 tree as an example to transform it from 2-3 tree to a red-black tree, so as to learn the conversion rules of 2-3 tree and red-black tree and realize the equivalence between 2-3 tree and red-black tree.

For a 2-node in a 2-3 tree, which itself is the same as a node in a binary search tree, it can be directly converted to a black node in a red-black tree, but for a 3-node, we need to do a little conversion:

1. Split the 3-node into a tree, and the left element of the 3-node becomes a subtree of the right element

2. Mark the original left element as red (to indicate that the red node and its parent used to be flat in the 2-3 tree)

Let’s convert a 2-3 tree of a complex point. According to the above two transformation rules, we directly convert the 2-node into a black node, split the 3-node into a subtree, and mark the left element in red. This process should be easy to understand. So all the red nodes are only going to be on the left subtree.

Analysis of basic properties of red-black trees

After completing the 2-3 tree to red-black tree transformation, we review the five properties of red-black trees:

(1) Each node is either black or red

That’s the definition of a red-black tree. There’s nothing to say.

(2) The root node is black

The root node corresponds to either a 2-node or a 3-node in a 2-3 tree, both of which are black, so the root node must be black. It can be easily seen from the mapping between tree nodes and red-black tree nodes in figure 2-3

(3) Each leaf node is black

Note that the leaf here refers to the empty leaf node, and the full form of the red-black tree above should look like this:

(4) If a node is red, its children must be black

Since every node of a red-black tree is transformed from a 2-3 tree, the node connected by the red node must be a 2-node or 3-node, and the root node of either 2-node or 3-node is black, so the child node of the red node must be black

(5) From any node to the leaf node, there are the same number of black nodes

That’s one of the most important properties of red-black trees, and that’s what makes red-black trees valuable. Since red-black trees are converted from 2-3 trees, each black node must correspond to some 2-node or 3-node of 2-3 trees, so the black nodes of red-black trees can also have the balance of 2-3 trees. If this property is not clear enough, you can look at the transformation diagram above for 2-3 trees and red-black trees to understand it.

Time complexity analysis of red-black tree

There are many proofs on the Internet that use mathematical induction to calculate the time complexity of red-black trees, so I won’t go into them here. Simple we can think about that for a normal balanced binary search tree, its search time complexity is O (logn), and as a red-black tree, there are in the worst case, namely lookup process, after the nodes are all original 2-3-3 nodes in a tree, cause path extended twice, the time complexity is O (logn) 2, Since coefficients can be ignored in the calculation of time complexity, the search time complexity of red-black tree is still O(logn). Of course, due to the existence of this coefficient, the search efficiency of red-black tree is lower than that of ordinary balanced binary tree (AVL tree) in practice.

Since red-black trees are less efficient than AVL trees, what are the advantages of red-black trees? In fact, the advantages of red-black trees are reflected in their insertion and deletion operations. The insertion and deletion performance of red-black trees is higher than that of AVL trees. In the subsequent sections on red-black tree creation, readers should be able to experience the advantages of red-black trees in adjusting tree balance operations.

In the previous section, we explained how to convert a 2-3 tree to a red-black tree. Now let’s see how to create a red-black tree without going through the 2-3 tree. After all, we can’t write code to create a 2-3 tree and then convert it to a red-black tree. Let’s recall the 2-3 tree creation rule:

Rule 1. When a new node is added, it is not added to the empty position, but to the last leaf node



Rule 2. Four nodes can be decomposed into a tree consisting of three 2-nodes, and the root node of the new tree must be merged upward with the parent node after decomposition

Simply speaking, the creation of 2-3 trees can be divided into two steps: “merge” and “split”. In order to achieve these two steps, we need to add several other operations to the basic operation of binary tree creation, respectively:

1. Keep the root node black

2. Rotate left

3. Right

4. Color flip

Keep the root node black and rotated left

Since we insert nodes into two or three trees by fusion, the newly added nodes have a horizontal relationship with the original nodes, so when we add nodes to a red-black tree, we add red nodes.

We insert the first red node, 42, and the first step conflicts with property 2 of the red-black tree, “The root node is black.” To resolve this conflict, we change the root node to black.

Let’s go ahead and insert node 37, and again, the new nodes are red

Here we need to think about it, if we reverse the order, first insert the 37 again insert 42, is directly add 42 to 37 right subtree, this is clearly wrong, because in the front two or three trees turn red and black tree in the process, we have learned that all the red node will only appear in the left subtree, so we need to be left to rotate, Rotate the position and color of the node.

Here are two independent nodes, if the node has left and right subtrees, can it still satisfy the properties of a binary search tree after rotation? We need to generalize to the general case. Let’s look at an example:

After the above steps, we have completed the normal left rotation, and we can write a few lines of pseudocode corresponding to this, calling 37 node and 42 target

function leftRotate(node) {​ 
​    node.right = target.left 
    target.left = node 
    target.color = node.color 
    node.color = RED
​​}Copy the code

Color flip

Turn of the previous section we introduced left, left rotating situation is actually corresponds to the 2-3 tree to generate 3 – nodes, nodes from 2 – to 3 – this step, from 3 to 4 – – node, and then to break up this step 4 – node and corresponding to the red-black tree what operation, let’s look at a simple example.

We take a red-black tree with two nodes as an example. Now the two red-black nodes correspond to the 3-node of the 2-3 tree [37 42]. We add a new red node 66, which is temporarily added to the right subtree of node 42 according to the principle of binary search tree. As we said earlier, the red node indicates that the node has a horizontal relationship with its parent in the 2-3 tree. In other words, the situation where the left and right children are red nodes actually corresponds to the temporary 4-node in the 2-3 tree. Of course, we know that red nodes can only appear on the left subtree, so we need to do some deformation.

How do we convert this temporary non-standard red-black tree into a proper red-black tree? Recall that the 2-4 tree splits the 4-node into 3 2-nodes, and the root of the split subtree merges upward. Since the 2-node corresponds to the black node in the red-black tree, we directly flip 37 and 66 on the left and right subtrees to black, which is the color flip. Since the root node still needs to fuse upwards, we re-mark the root node in red (adding a new node)

Let’s write a couple of lines of code, because after all, all this back-and-forth isn’t for people, it’s for machines. The code is simple enough to turn the root node red and the left and right child elements black. Of course, only a tree structure like the one above (the root node is black and the left and right child elements are red) works with this color flip.

function flipColors(node) {
    node.color = RED
    node.left.color = BLACK
    node.right.color = BLACK
}Copy the code

Right rotation

We just inserted node 66, which is larger than 42, so it was added to the right subtree of node 42, and then we did the transformation using the color flip. However, the node is not always added to the right subtree. For example, insert node 12, which is less than 37, so node 12 is added to the left subtree of 37:

In this case, we need to rotate to the right, and we’ll go straight to the general case:

After the above steps, we have completed the normal right rotation, and we can write a few lines of pseudocode corresponding to this, calling 37 target and 42 node.

function rightRotate(node) {  
    node.left = T1  
    target.right = node  
    target.color = node.color  
    node.color = RED
}Copy the code

Other situations

We solved the two cases of adding nodes to the 3-node by color flip and right rotation, namely, the case of adding nodes larger than B, and the case of adding nodes smaller than A. What if the node is larger than A and smaller than B?

For the third case in the figure above, we need to combine left rotation, right rotation, color flip and other sub-processes to adjust to a correct red-black tree, using [37 40 42] as an example:

The process to summarize

If we summarize the three cases above, we can see that there are actually only five ways to insert nodes into a red-black tree

1. A 2-node is inserted and the node is smaller than the 2-node

2. A 2-node is inserted and the node is larger than the 2-node

3. Insert a 3-node with two nodes smaller than 3-node

4. Insert a 3-node and two nodes larger than 3-node

5. Insert a 3-node between two nodes of the 3-node

In fact, each of these five forms can be represented by a logical chain. Let’s review the conversion process in 6.4 where the inserted nodes are less than a and greater than B. I have hidden the specific numbers for generality.

We find that the process already includes the above five cases. If we insert nodes larger than A and larger than B, we can skip to step 4 and flip the color. If the node we insert is less than a and less than b, then skip to step 3; If the insert node is between AB, then it corresponds to step 2.

The three lines correspond to three cases of 3-node insertion

With this logical flow, our code is suddenly clear, we only need to judge by a few conditions, can describe all the red black tree rotation, let’s write a piece of code:

function add(node) {  
    // If the right node is red and the left node is black, then rotate it left, corresponding to case 2
    if(isRed(node.right) && ! isRed(node.left)) node = leftRotate(node)// If the left node is red and the left node of the left node is red, then rotate it right, corresponding to case 3
    if(isRed(node.left) && isRed(node.left.left)) node = rightRotate(node)    

    // If the left and right nodes are red, then flip the color, corresponding to case 4
    if(isRed(node.left) && isRed(node.right)) flipColors(node)

}Copy the code

At this point, we have achieved all the balancing operations of the red-black tree, and from this process, we can also draw the important conclusion that any imbalance of the red-black tree can be solved in three rotations, which is the advantage of the red-black tree over the AVL tree.

Comparison between red black trees and AVL trees

1. AVL tree is more balanced than red-black tree, and its search efficiency is also better than red-black tree. According to our previous analysis, the search time complexity of red-black tree is 2logn in the worst case, which is larger than that of AVL tree. AVL trees are strictly balanced, and red-black trees can only achieve “black balance”, that is, from any node to the leaf node, the same number of black nodes pass through, but the number of red nodes is uncertain, in the worst case, as many red nodes as black nodes pass through.

2. The performance of add-delete nodes in red-black trees is better than that of AVL trees. When adding or deleting nodes to red-black trees causes the imbalance of red-black trees, we only need three rotations at most to solve the problem

7. To summarize

As a final summary, red-black trees are a compromise between sacrificing some search performance in exchange for adding and deleting performance, with less rigorous balance in exchange for fewer rotations. In practice, red-black trees are more suitable if the tree to be maintained requires frequent addition and deletion of nodes, whereas AVL trees are more suitable.

Finally, I wish you to learn the red black tree soon, after all, your peers are abandoning you