Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "what is a red-black tree". The editor shows you the operation process through an actual case, and the operation method is simple, fast and practical. I hope this article "what is a red-black tree" can help you solve the problem.

Why is there a red-black tree?

You must be no stranger to binary tree search tree. First, take a look at the definition of binary search tree:

A binary search tree (Binary Search Tree) is either an empty tree or a binary tree with the following properties: if its left subtree is not empty, the value of all nodes on the left subtree is less than the value of its root node; if its right subtree is not empty, then the value of all nodes on the right subtree is greater than the value of its root node; its left and right subtrees are also binary sorting trees.

Theoretically, the time complexity of querying, inserting and deleting a node in a binary search tree is O (log (n)), which can fully meet our requirements, so why is there a red-black tree?

Let's take a look at an example of inserting into a binary search tree in turn (1, 2, 3, 4, 5, 6). After insertion, it looks like this.

As can be seen from the binary search tree degenerated into a linked list, in this case, the binary search tree is reduced to a linked list! When querying, inserting, and deleting an element, the time complexity becomes O (n), which is obviously unacceptable. The reason for this is that the binary search tree does not have a self-balancing mechanism, so there is the concept of balanced binary tree.

Balanced binary tree (Balanced Binary Tree) has the following properties: it is an empty tree or the absolute value of the height difference between its left and right subtrees is not more than 1, and both left and right subtrees are a balanced binary tree.

As the example just now, if we implement it with a balanced binary tree, after inserting the element, it should look like this (not unique).

The self-balanced binary tree ensures that in the worst case, the binary tree can still maintain absolute balance, that is, the absolute value of the height difference between the left and right subtrees is not more than 1. But this also brings a problem, that is, the definition of balanced binary tree is too strict, resulting in each insertion or deletion of an element, it is necessary to maintain the overall balance of the binary tree, which is too expensive. A binary search tree may degenerate into a linked list, and the cost of maintaining balance in a balanced binary tree is too high, so what should we do? This is about the wisdom of the "Doctrine of the mean". To put it bluntly, the definition of balance is relaxed and less strict, so that the binary tree does not degenerate into a linked list, and the cost of maintaining balance is acceptable. Yes, this is the red-black tree we're going to talk about. First, take a look at the definition of a red-black tree:

Red-black tree is a kind of binary search tree which contains red-black nodes and can balance itself. It must satisfy not only the properties of the binary search tree, but also the following properties:

Property 1: each node is either black or red.

Property 2: the root node is black.

Property 3: each leaf node (NIL) is black.

Property 4: the two sub-nodes of each red node must be black.

Property 5: the path from any node to each leaf node contains the same number of black nodes.

These are the five properties of a red-black tree. I believe many people have seen it, and there are not a few who can memorize it, but I am afraid that not many people really understand why it is defined in this way. Let's talk about the definition of red-black tree from the point of view of 2-3 trees. Looking at the red-black tree from 2-3 trees

Generally speaking, the binary tree we come into contact with most is that a parent node has at most two child nodes. The difference between a 2-3 tree and a binary tree is that a parent node can have two or three child nodes, and it also satisfies the properties similar to the binary search tree. And most importantly, all the leaf nodes of a 2-3 tree are on the same layer, and the last layer cannot have empty nodes, similar to a full binary tree.

Let's insert 10, 9, 8, 7, 6, 5, 4, 3, 2 and 1 in turn to see how 2-3 numbers are self-balanced.

The 2-3 tree first misses the search before inserting the element, then inserts the element into the leaf node, and then balances it, as detailed below.

Insert 10 first, as shown in the following figure

Insert 10 into 2-3 trees

Then insert the tree 9 less than 10 and integrate 9 into the leaf node 10 (and also the root node, of course). After the fusion is completed, it is as follows:

Insert 9 in 2-3 tree

This is a 3-node and does not need to perform a balancing operation. In the 2-3 tree, the node with two elements and three child nodes is called 3 nodes, and the node with one element and two child nodes is called 2 nodes.

Then insert 8, which is also integrated into the leaf node when inserting 8, as shown on the left side of the following figure

Insert 8 in 2-3 tree

8 after merging into the leaf node, the node has three elements, which does not meet the definition of 2-3 tree, so it is necessary to split the 3 nodes, that is, to split the left and right elements into 2 nodes, while the middle element is extracted and continues to integrate into its parent node. here it becomes a root node.

Continue to insert 7, as follows

After inserting 7 inserts into the 2-3 tree, each node satisfies the definition of the 2-3 tree and does not need to be balanced.

Then insert 6, or first find the leaf node, and then integrate it, as shown on the left side of the following figure

After the insertion of 6 into the 2-3 tree, the leaf nodes of 6, 7 and 8 no longer meet the definition of 2-3 tree, and need to be split, that is, the extracted element 7 is integrated into the parent node, and 6 and 8 are split into the left and right child nodes of 7.

Then insert 5, as shown in the following figure, again without the need for balancing

Insert 5 and then 4 in the 2-3 tree, or first find the leaf node and then integrate it, as shown on the left side of the following figure

After the insertion of 4 into the 2-3 tree, the leaf nodes of 4, 5 and 6 no longer meet the definition of 2-3 tree, and need to be split, that is, the extracted element 5 is integrated into the parent node, and 4 and 6 are split into the left and right child nodes of 5. After 5 is integrated into the parent node, the node has three elements 5, 7 and 9, so it needs to continue to split. Element 7 becomes the new root node, and 5 and 9 become the left and right child nodes of 7.

Then insert 3Pol 3 into the leaf node where 4 is located, and no balancing operation is required.

Insert 3 and then 2 in the 2-3 tree, or first find the leaf node and then integrate it, as shown on the left side of the following figure

After inserting 2 into the 2-3 tree, the leaf nodes of 2, 3 and 4 elements no longer meet the definition of 2-3 tree, and need to be split, that is, the extracted element 3 is integrated into the parent node, the 2 and 4 are split into the left and right child nodes of 3, and 3 is integrated into the parent node where 5 is located.

Finally, insert 2, also find the leaf node, and then integrate it, as shown in the following figure

By inserting 1 into the 2-3 tree, we have finished inserting 10, 9, 8, 7, 6, 5, 4, 3, 2, and 1 into the 2-3 tree in turn, and the 2-3 tree always maintains a balance. So, isn't it amazing. Look at the red-black tree again.

So what does a red-black tree have to do with a 2-3 tree? Now we transform the 2-3 tree into a binary tree. How to transform it? For 2 nodes, it remains the same; for 3 nodes, we first mark the element on the left of the 3 nodes in red, as shown in figure 2 below.

The transformation from 2-3 tree to red-black tree is then transformed into the form of figure 3; then the parent node of the child node in the middle of the 3 node is set to the red node in the parent node, as shown in figure 4; finally, we change the form of figure 4 to look like a binary tree, as shown in figure 5. Figure 5 is not very familiar, yes, this is the famous red-black tree we often talk about.

Let's go back and take a look at the five properties of the red-black tree.

From 2-3 trees to see the nature of the red-black tree 1: each node is either black or red.

There are 2 nodes and 3 nodes in the 2-3 tree, the element on the left of the 3 nodes is the red node, and the other nodes are black nodes.

Property 2: the root node is black.

In a 2-3 tree, the root node can only be 2 or 3 nodes, and the equivalent form of 2 nodes and 3 nodes in the red-black tree, as shown in the following figure

The equivalent form of 2 nodes and 3 nodes in the red-black tree obviously, in either case, the root node is black.

Property 3: each leaf node (NIL) is black.

The leaf node here does not refer to the leaf node where the left and right subtrees are empty, but that the node does not have a child node or is called a leaf node for an empty node. In property 2, we discuss that the root node is black, all discuss the situation that the root node is not empty, if the red-black tree is an empty tree, then the root node is also an empty leaf node, then the leaf node must be black.

Property 4: the two sub-nodes of each red node must be black.

From the point of view of the 2-3 tree, the red node corresponds to the element to the left of the 3 nodes in the 2-3 tree, so its child nodes are either 2 nodes or 3 nodes. The color of the nodes corresponding to both 2 and 3 nodes is black, which is discussed in property 2.

Property 5: the path from any node to each leaf node contains the same number of black nodes.

Property 5 should be the most important property of a red-black tree. The 2-3 tree is an absolutely balanced tree, that is, any node in the 2-3 tree starts from the leaf node and passes through the same number of nodes after reaching the leaf node. What about the red-black tree? In the 2-3 tree, the 2 nodes corresponding to the red-black tree is a black node, while the 3 nodes corresponding to the red-black tree is a red node and a black node. Therefore, whether it is 2 nodes or 3 nodes, there will be a black node in the red-black tree. Then the absolute balance in the 2-3 tree naturally means that the path from any node to each leaf node in the red-black tree contains the same number of black nodes.

I believe you now have a deeper understanding of the five properties of the red-black tree. So let's take a look at the three operations of the red-black tree to maintain balance, that is, discoloration, left-handed and right-handed.

First, let's take a look at the discoloration. The following figure is an example.

After the discoloration of the red-black tree inserts node 3 into the 2-3 tree, it no longer meets the definition of 2-3 tree and needs to be decomposed to extract element 2 as the parent node of 1 and 3, and then 2 continues to merge upward.

Corresponding to the red-black tree, node 3 is inserted first, and the newly inserted node in the red-black tree is red by default, and then does not meet the definition, so it needs to be decomposed. After decomposition, each node is 2 nodes, so it becomes black. On the other hand, the 2 nodes need to continue to merge upward, so they should turn red.

Then take a look at the right rotation. The following figure is an example.

After inserting element 1 into the right rotation of the red-black tree, the right rotation operation is carried out, first disconnecting the 2 nodes from the 3 nodes, and at the same time disconnecting the 2 from the right subtree of 2, and then connecting the right subtree of 2 to the left subtree position of 3. It will not violate the nature of the binary search tree, and then connect 3 to the right subtree position of 2. Finally, the color of the corresponding node should be changed, that is, the color of 2 nodes should be changed to the black of the original 3 nodes, and the color of 3 nodes should be changed to the red of the original 2 nodes.

Then take a look at the left rotation, which is similar to the right rotation. The following figure is an example

After inserting element 3 into the left rotation of the red-black tree, the left rotation operation is carried out, first disconnecting the 2 nodes from the 3 nodes, disconnecting the left subtrees of 3 and 3, and then connecting the left subtrees of 3 to the right subtree position of 2. It will not violate the nature of the binary search tree, and then connect 2 to the left subtree position of 3. Finally, the color of the corresponding node should be changed, that is, the color of 2 nodes should be changed to the red of the original 3 nodes, and the color of 3 nodes should be changed to the black of the original 2 nodes. This is the end of the content about "what is a red-black tree". Thank you for your reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.