In 2017, Xiao Grey once published a cartoon about red and black trees. Due to the short time, part of the knowledge point was passed over, and the explanation was not very detailed and comprehensive.
Recently, Xiao Grey made a summary of this knowledge point again, divided into two parts, I hope you can thoroughly understand the red-black tree this important data structure.
————— the next day —————
— — — — — —
What are the properties of binary lookup trees (BST)?
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 node.
3. The left and right subtrees are also binary sort trees.
The tree below is a typical binary search tree:
1. Check root node 9:
The node with the value of 10 can only be in the right subtree of the root node. The node with the value of 10 can be in the right subtree of the root node.
10 < 13, so check left child 11:
10 < 11; 10 < 11;
Suppose the initial binary search tree has only three nodes, the root 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. Given the properties of binary search trees, what would the result look like?
1. The node is red or black.
2. The root is black.
3. Every leaf node is a black NIL node.
4 Each red node has two children that are black. (No two consecutive red nodes on all paths from each leaf to the root)
5. All paths from any node to each leaf contain the same number of black nodes.
The tree below is a typical red-black tree:
When can I break the rules of a red-black tree, and when can I not break the rules? Let’s take two simple examples:
1. Insert new node with value 14 into the original red-black tree:
Since parent 15 is black, this does not break the rules of red-black trees, and no adjustments are required.
Insert new node (21) into the original red-black tree:
Since parent 22 is red, this situation breaks rule 4 of red-black trees (both children of each red node are black) and must be adjusted to conform to red-black tree rules again.
Color:
To re-conform to the rules of red-black trees, try to change the red node to black, or the black node to red.
The following figure shows part of the red-black tree (subtree). The newly inserted node Y is a red node, and its parent node X is also red, which does not comply with rule 4, so we can change node X from red to black:
However, simply changing the color of one node will cause an extra black node to appear in the associated path, thus breaking rule 5. Therefore, we need to make further adjustments to other nodes, which will be explained later.
Left rotation:
Rotate the two nodes of the red-black tree counterclockwise so that the parent node is replaced by its right child and it becomes its left child. It’s a weird thing to say, but look at the picture below:
In the picture, Y, the child on the right, takes X’s place, and X becomes his child on the left. This is a left rotation.
Right rotation:
Rotate the two nodes of a red-black tree clockwise so that the parent is replaced by its left child and the parent becomes its right child. Take a 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.
Situation 1: The new node (A) is at the root and has no parent.
(Hollow triangles represent subtrees below nodes)
In this case, the new node is directly changed to black, and rule 2 is satisfied. At the same time, the black root increases the number of black nodes on each path by one, so rule 5 is not broken.
Situation 2: The parent of the new node (B) is black.
In this case, the new red node B does not break the red-black tree rule, so no adjustments are needed.
Situation 3: The parent and uncle of the new node (D) are red.
In this case, two red nodes B and D are consecutive, violating rule 4. So let’s make node B black:
This creates a black node in the path of node B, breaking rule 5. So let’s make node A red:
At this point, nodes A and C become consecutive red nodes, and we make node C black again:
After the above adjustment, this part of the red black tree rules again.
Situation 4: The parent of the new node (D) is red, the uncle node is black or has no uncle, and the new node is the right child of the parent, and the parent (B) is the left child of the grandfather.
We rotate node B to the left so that the new node D becomes the parent and the original parent B becomes the left child of D:
So we’re in situation 5.
Situation 5: The parent of the new node (D) is red, the uncle node is black or has no uncle, and the new node is the left child of the parent, and the parent (B) is the left child of the grandfather.
We rotate node A to the right so that node B becomes the grandfather and node A becomes the right child of node B:
Next, we make node B black and node A red:
After the above adjustment, this part of the red black tree rules again.
These are the five scenarios involved in red-black tree insertion.
One might ask, what if the parent of scenario 4 and 5, B, is the right child of the grandparent, A?
Quite simply, if the parent in scenario 4 is a right child, it becomes a mirror image of scenario 5, changing from a right-handed operation to a left-handed one; If the parent B in scenario 5 is a right child, it becomes a mirror image of scenario 4, changing the original left-handed operation to right-handed.
Given the following red-black tree, the newly inserted node is 21:
Obviously, the new node 21 and its parent 22 are consecutive red nodes, which violates rule 4. How can we adjust this?
Let’s review the five scenarios we’ve just described. The current situation fits scenario 3:
“The parent and uncle of the new node are red.”
So we go through three changes, 22 becomes black, 25 becomes red, 27 becomes black:
After the above adjustment, the subtree with node 25 as root conforms to the red-black tree rule, but node 25 and node 17 become continuous red nodes, which violates rule 4.
Thus, we consider node 25 to be a new node that corresponds to the mirror image of situation 5:
“The parent of the new node is red, the uncle node is black or has no uncle, and the new node is the right child of the parent, and the parent is the right child of the grandfather.”
So we rotate it left around root 13 so that node 17 becomes the new root:
Next, make node 17 black and node 13 red:
In this way, our red-black tree becomes compliant again.
— — the END — — –
Like this article friends, welcome to pay attention to the public number programmer xiao Grey, watch more exciting content
