— — — — — —
— — — — — —
What are the properties of a binary search tree?
1. The value of all nodes in the left subtree is less than or equal to the value of its root node.
2. The value of all nodes in the right subtree is greater than or equal to the value of its root.
3. The left and right subtrees are also binary sorting trees.
The tree below is a typical binary search tree:
1. Check the root node.
2. Because 10 > 9, so check right child 13:
3. Since 10 < 13, so check the left child 11:
4. Because 10 < 11, so look at the left child 10, find 10 is the node to look for:
Suppose the initial binary search tree has only three nodes, the root node value is 9, the left child value is 8, and the right child value is 12:
Next we insert the following five nodes: 7,6,5,4,3. According to the binary search tree property, what is the result going to be?
1. The node is red or black.
2. The root node is black.
3. Each leaf node is a black NIL node.
4 The two children of each red node are black. (There cannot be two consecutive red nodes on all paths from each leaf to root)
5. All paths from any node to each of its leaves contain the same number of black nodes.
Here is a typical red-black tree:
When does it break the red-black tree rule, and when does it not break the rule? Let’s take two simple chestnuts:
1. Insert a new node with value 14 into the old red-black tree:
Since the parent node 15 is black, this situation does not break the rules for red-black trees and no adjustments are required.
2. Insert a new node with value 21 into the old red-black tree:
Since the parent 22 is a red node, this situation breaks rule 4 for red-black trees (two children of each red node are black) and must be adjusted to fit the red-black tree rule again.
Color:
To reconform to the red-black tree rule, try turning the red node black, or the black node red.
The figure below represents part of the red-black tree, and it is important to note that node 25 is not the root node. Change node 22 from red to black because nodes 21 and 22 appear red in succession, which does not conform to rule 4:
But that’s not the end of the equation, because the extra black node breaks rule 5, so a chain reaction takes place that continues to change node 25 from black to red:
It’s still not over, because node 25 and node 27 form two more consecutive red nodes, and we need to continue to change node 27 from red to black:
Left rotation:
Rotate the two nodes of the red-black tree counterclockwise so that the parent node is replaced by its own right child and it becomes its own left child. It’s weird. Look at this:
In the picture, Y as the right child takes the place of X, and X becomes his left child. This is a left rotation.
Right rotation:
Rotate the two nodes of the red-black tree clockwise so that the parent node is replaced by its own left child and it becomes its own right child. Look at the picture below:
In the picture, Y, the left child, takes the place of X, and X becomes his right child. This is a right rotation.
Let’s take the case where we just inserted node 21:
First, what we need to do is to change the color, and change the color of node 25 and the nodes below it:
In this case node 17 and node 25 are two consecutive red nodes, so make node 17 black? I’m afraid not. This not only breaks rule 4, but also makes it impossible to make node 13 red according to rule 2 (root nodes are black).
The color change will not solve the problem, so let’s treat node 13 as X and node 17 as Y, and rotate left as shown in the previous diagram:
Since the root node must be black, it needs to change color, and the result is as follows:
Is that the end? Don’t. Because two of the paths (17 -> 8 -> 6 -> NIL) have four black nodes and the other paths have three black nodes, which does not comply with rule 5.
At this point we need to view node 13 as X and node 8 as Y and rotate it to the right as shown in the previous diagram:
Finally, according to the rules for color change:
In this way, our red-black tree becomes regularized again. The adjustment process for this example is more complicated, and it goes through the following steps:
Color change -> left turn -> Color change -> Right turn -> color change
A few notes:
1. As for the adjustment of self-balance of red-black trees, there are many cases involved in the insertion and deletion of nodes, which cannot be expanded to list one by one due to space constraints. Interested friends can refer to Wikipedia, which is very clear.
2. The example of the red-black tree adjustment process in the cartoon is a relatively complex situation, and those who do not understand it need not be obsessed with it. The key is to understand the main idea of the red-black tree self-balancing adjustment.
— — the END — — –
For those of you who like this article, please long click on the image below to follow the subscription account Programmer Grey for more exciting content
