Writing in the front
- Binary tree
- Balanced binary tree AVL
A red-black tree is also a binary search tree, so why do you need a red-black tree when you have an AVL tree?
Before the AVL balanced binary tree implementation talked about why use balanced binary tree AVL (bintree degradation problems of similar list), the biggest function is used to find, its time complexity is O (logn), but after insertion or deletion of AVL tree node, if the height difference is greater than 1, at this point, the AVL tree balance is destroyed, You need to rotate to achieve balance. As a result, if frequent insertions and deletions occur in a scenario that requires frequent tuning, performance deteriorates.
Therefore, red-black tree is proposed to solve the problem of frequent insertion and deletion of balanced tree.
Let’s look at two-three-four trees before we look at red-black.
The 2-3-4 trees
In a binary tree, each node has one data item (which can be understood as the value of the node, key) and a maximum of two child nodes. A two-three-four tree is a multi-tree if it allows more items and children per node, and it is also a balanced tree (b-tree).
A two-three-four tree is a B-tree with order 4, so it is also called a quadtree. It has the following properties:
-
A node with one key has two children, a node with two keys has three children, a node with three keys has four children, and the nodes corresponding to the key are called two-three-four nodes, three-three nodes, and four-four nodes. That’s why it’s called a two-three-four tree, right
-
All leaf nodes are always on the same layer
-
The values of each node are in order from left to right. All the keys in the subtree between two keys must be larger than the left key of their parent and smaller than the right key of their parent. The following
Like this two-three-four tree:
In the picture above:
If there are 2 links, there are 2 nodes
There are three links for three nodes
There are four links for four nodes
The insert
The insertion of a two-three-four tree is always in the leaf node and generally does not allow the insertion of duplicate keys.
If the leaf node at the time of insertion is not full (that is, 4 nodes), such as inserting data 45, as follows:
Node split
If the insert node is 4 nodes, then the nodes need to be split to balance the tree (assuming that the split node is not the root node). A 4 node can be split into a root node and two child nodes (each with a key) and then inserted into the children. If the split node data are respectively expressed by ABC:
If the parent node of the split node is full, split the node again.
Two-three-four tree deletion if interested can go to Baidu themselves, many online
Point it
Red and black tree
A red-black tree is also a binary search tree and a self-balancing tree with the following properties:
- Nodes are red or black (either black or red)
- The root node is black
- All null nodes are called leaf nodes and are black
- All children of red nodes are black (i.e. no consecutive red nodes)
- All paths from any node to its leaf node contain the same number of black nodes
Like this common red-black tree:
From the above properties, it can be concluded that the longest path from the root node to the leaf node is not more than twice the shortest path
Why is that?
According to property 5 above, we know that the red-black tree in the figure below has three black nodes on each path. So the shortest path has length 2(path with no red nodes). According to property 4(no continuous red nodes) and property 2,3 (leaves and roots must be black nodes). Then we can conclude:
Shortest path: A path with 3 black nodes can have at most 2 red nodes (red-black interval exists), and the shortest path is 2. Longest path: the longest path for a red-black tree with a black depth of 2 (the root is also black) is 4.
From this we can see that the red-black tree is roughly balanced. (Less than a balanced binary tree, AVL’s balancing factor is at most 1)
Note: If properties 1-5 are mentioned below, the above properties are indicated respectively. For example, property 2 means “the root node is black”.
Equivalence between two-three-four trees and red-black trees
Red-black trees are derived from two-three-four trees, with one red-black tree corresponding to one definite two-three-four tree and one two-three-four tree corresponding to multiple red-black trees.
The above two-three-four trees and red-black trees look completely different, but they are actually equivalent. A two-three-four tree can be turned into a red-black tree by a few rules, such as:
In the figure above, there are two conditions for the three nodes:
- Right-leaning: Red is on the right
- Left-leaning: Red is on the left
Thus, this determines that a red-black tree corresponds to a definite two-three-four tree, and that a two-three-four tree corresponds to multiple red-black trees. Then we convert the original two-three-four tree to a red-black tree according to the above rule, as follows:
The transformation between nodes corresponds as follows:
Red-black trees generated by rules:
So how exactly do two-three-four trees correspond to red-black trees? Is that the simple substitution up here? So how do I adjust when I insert or delete, what rules do I use to adjust that? Let’s move on.
Left-leaning red-black trees
In the equivalent substitution above, 3 nodes can be transformed into 2 different types of red-black trees, namely left-leaning red-black trees and right-leaning red-black trees. The following content is mainly explained by left-leaning red-black trees.
So what is a left-leaning red-black tree?
A node can have either one child or two children, and if it has one red child, it can only be on the left, and if it has two red children, it can only be red on both sides. The same goes for right-leaning red-black trees:
Now that we know the left-leaning red-black tree, let’s see what the red-black tree adjustment has to do with it and the two-three-four tree, so let’s move on.
Red black tree adjustment
The insert
According to the above property, if we insert an element that violates it, then we need to adjust it to comply with the above property. There are only two possible ways to adjust:
- Change the color of the node
- Rotate the node
Rotation and discoloration
Left-handed: take a node as the pivot (rotation node), its right child node becomes the parent of the rotation node, the left child node of the right child node becomes the right child node of the rotation node, and the left child node remains unchanged
Right-rotation: take a node as the pivot (rotation node), its left child node becomes the parent of the rotation node, the right child node of the left child node becomes the left child node of the rotation node, and the right child node remains unchanged
The insert operation here mainly analyzes the situation in the insert process from the process of inserting nodes and the rules of left-leaning red-black trees and right-leaning red-black trees.
Basic definition:
- Uncle-node: a sibling node of the new node’s parent (null if no uncle-node exists)
- Grandparent: indicates the parent node of the parent node of the new node
- Rule for inserting nodes: New nodes are red nodes by default
The numbers 1-5 below indicate the number of nodes to be inserted from the root node (including the root node).
- Create a red black tree (
13Is the root node, null nodes are not shown here), according to the properties of red-black trees: the root node is black
-
Insert the second node, and there are two situations
-
If the inserted node is less than 13, then the node is the left child node of 13. If the inserted node 8, then it is a red-black tree, which also conforms to the rule of left-leaning red-black tree.
-
If the inserted node is larger than 13, the node is the right child node of 13. If the inserted node is 17.
At this time, node 17 is the right child node, which does not conform to the rule of left-leaning red-black tree, so how to adjust its balance? We restore the above image to a two-three-four tree:
This two-three-four tree is actually a three-node tree, and it’s turned into a left-leaning red-black tree by following the left-leaning rules (black for the parent and red for the child) :
Let’s compare the insertion of a two-three-four tree to a red-black tree:
As you can see from the figure above, this is a 3-node for a two-three-four tree, and a left-rotation color for a red-black tree by inserting a right child node. If not to the left, that would be the first case, neither rotating nor changing color
Through one and two steps, we can get the first case:
Case 1: The inserted new node is at the root of the tree or the parent of the inserted new node is black, and no operation is required to balance it
-
-
When the third node is inserted, nodes 13 and 17 are used as examples, there are three conditions
-
If the number of inserted nodes is smaller than 13, the node is the left child node of 13. If the number of inserted nodes is 8, the node is the left child node of 13
By the nature of a red-black tree you can’t have a continuous series of red nodes, so you have to adjust it to balance, so how do you adjust it to balance? Let’s revert to a two-three-four tree:
Compare the two-three-four tree with the red-black tree insert again:
As you can see from the figure above, for a two-three-four tree it is a four-node tree, and for a two-three-four tree to become a left-leaning red-black tree it is the parent black-child red. For a red-black tree it’s inserting a left child node, doing a right rotation and changing color. What about the discoloration here? So it’s going to be a two-three-four tree going to be a red-black tree, the parent black, the child red.
Due to left-leaning reasons, the new node is the left child node of its parent node, and the parent node is also the left child node of its parent node. The second situation can be obtained:
Case 2: The parent node of the inserted new node is red, and the uncle-parent node is black (if there is no null node, null node is black node), and the new node is the left child node of its parent node, and the parent node is also the left child node of its parent node. In this case, only one dextral discoloration is required.
In fact, we can think of the above nodes 13 and 17 as the left child node of 17 by leaning to the left. If not leaning to the left, in the order of insertion, it should look like this:
So, if I insert a node greater than 17, then this is exactly the opposite of case two. If I insert node 25:
Here the third case can be deduced very simply:
Case 3: The parent node of the inserted new node is red, and the uncle node is black (if there is no null node, null node is black node), and the new node is the right child node of its parent node, and the parent node is also the right child node of its parent node. A left-handed discoloration is required in this case.
-
If the inserted node is larger than 13 and smaller than 17, this node is the right child node of 13. If the inserted node is 15, this node is the right child node of 13
Certainly not conforming to the properties of red-black trees, here is the comparison:
In this case, you can see that the insertion node still forms a two-three-four tree, which is rotated to the left, which is the same thing as above, and then rotated to the right, which is changing color, which is the final red-black tree.
Case 4: The parent node of the inserted new node is red, and the uncle node is black (if there is no null node, null node is black node), and the new node is the right child node of its parent node, and the parent node is the left child node of its parent node. This situation requires a left, then a right, and finally color.
Similarly, if not left, when inserting node 15:
Case 5: The parent node of the inserted new node is red, and the uncle node is black (if there is no null node, null node is black), and the new node is the left child node of its parent node, and the parent node is the right child node of its parent node. This situation requires a right, then left, and finally color.
-
If the node to be inserted is larger than 17, the node is the right child node of 17. If the node to be inserted is 25
In this case, it’s going to be a red-black tree that satisfies this condition, and this is going to be case one, so you don’t have to do anything.
So, inserting three nodes consecutively forms a four-node for a two-three-four tree, and this for a red-black tree:
-
-
When the fourth node is inserted, take nodes 13, 17, and 25 as an example. At this time, there may be four cases, that is, the fourth node may be the left and right child node of 13, the left and right child nodes of 25.
-
If it is the left child node of 13, insert node 11, that is, insert the node to the left of the root node
The color changes in the figure above correspond to three nodes of a two-three-four tree, with three nodes left-leaning into a left-leaning red-black tree with parent black and child red, and two nodes corresponding to black.
-
If it is the right child node of 13, insert node 15, that is, insert node 15 to the left of the root node
In the figure above, it is handled in the way of left-leaning. If not left-leaning, it is much simpler, because there is no need to turn left, and the color can be changed directly, as follows:
-
For the left child node of 25, insert node 22, that is, insert node 22 to the right of the root node
-
If it is the right child node of 25, insert node 27, that is, insert node 27 to the right of the root node
If you don’t tilt to the left, you can directly change color:
According to the above analysis of the fourth node insertion, it can be seen that when the new node is inserted, its parent node and its uncle node are both red. If the left inclination is not taken into account, they are only color-changed, so scenario 6 is obtained:
Case 6: If the parent and uncle of the inserted node are red, do the color change operation to balance them.
-
At this point, the red-black tree insertion cases are analyzed, and if you understand the transition from a two-three-four tree to a red-black tree, you don’t have to remember what happens when you insert a node.
summary
Based on the above analysis of the insert operation, the following points can be summarized:
- If the new node is the root node or the parent node is black, no operation is required (black parent).
- If the parent and uncle of the inserted new node are both red, do the color change operation (red parent red uncle)
- If the parent of the inserted new node is red, the uncle node is black (red parent black uncle)
- If the new node and the left child node, the parent node is the left child node, first right and then color (child left parent left)
- If the new node is a right child node, the parent node is a left child node, first left, then right, then color (child right, parent left)
- If the new node is a left child node, the parent node is a right child node, first right-turn and then right-turn and then change color (child left parent right)
- If the new node is the right child node, the parent node is the right child node, first turn left and then change color (child right parent right)
Delete operation
The deletion of the red-black tree is much more complicated if it is reduced to a two-three-four tree, so the binary sorting tree deletion method is used here. The deletion of red-black tree is similar to that of binary sorting tree, which can be divided into three cases, namely, the deleted node has no child node, has one child node and has two child nodes. In other words, the deletion of red-black tree should first consider whether there are children nodes and then consider the color of the deleted node. So in the deletion of a red-black tree, there are six cases (3*2).
There is no child node
Scenario 1: If a node is deleted, there is no child node and the node is red
According to properties 4 and 5 of red-black tree, if the deleted node is red, its parent node must be black. Therefore, in this case, the property of red-black tree will not be destroyed, and it can be deleted directly. Delete node 27 as shown in the following figure
Case 2: If a node is deleted, no child node exists and the node is in black
This situation is more complex, it is recommended to read the other several before looking back.
The deletion of case 2 is further divided into the following types:
(1) The sibling node of a node to be deleted is black, and the sibling’s side (left or right) is red
In the figure above, if node D is deleted, 1 black node passing through path D is reduced, and node B is rotated (left) to the position of P with P as the pivot.
In addition, the BS node on the same side as B becomes black, and the P node becomes black, and the replacement node is null deleted to achieve local balance.
Similarly, if node D is on the right, node B is on the left, and node BS is on the left, then the balance can be achieved by right-rotation + discoloration.
② The sibling node of the deleted node is black, and the other side (left or right) is red
Rotate BS and B (right) to change color and become ①.
Similarly, node D is on the right, node B is on the left, and node BS is on the left.
③ The sibling node of the node to be deleted is black, and the child node of the sibling node is black
-
If the parent node P of the node to be deleted is red, click
If you delete D, there’s one less black on the path that goes through D, so you can change P to black, so you delete D and you go through D
The black nodes of PI will be the same as before. But this will increase the number of black nodes in the path through node B by one, so that’s ok
I’m going to make node B red, so I have the same number of black nodes on my path.
-
If the parent node P of the deleted node is also black
D node deletion after, no matter how color can make about balance, because the left side is missing a black node, if the node B D brother into red, the left and right subtrees of black P node is the same, but after PB path of black nodes will be reduced by 1, so this time need to P nodes (make P to remove node analysis, But not actually delete).
④ The sibling node of the deleted node is in red
If the sibling node of a node to be deleted is red, the parent node must be black, and the child node of B must also be black
Here we left turn and color node B:
From the figure above, it can be seen that after rotation, the brother node of deleted node D becomes the black node BSL, which is the case ① or ② analyzed above.
This explains why a red-black tree deletion takes up to three rotations:
- If the right child node of BSL is red, it conforms to case ①, which changes color after one rotation, and a total of 2 rotations.
- If the left child node of BSL is red, it conforms to case ②, and after one rotation, it conforms to case ①, with a total of 3 rotations.
So the whole process only takes three rotations to balance, which is why delete is better than AVL.
There is a child node
Case 3: The deleted node has a child node, and the deleted node is red
The situation is as follows:
According to properties 4 and 5 of red-black tree, when constructing a red-black tree, the path of any node has the same black node, and red node and red node
The nodes are discontinuous, so if you delete a node that is red, the children must be black, which breaks property 5, so that’s what happens when you build a red-black tree
It won’t exist, so the deletion situation won’t exist.
Case 4: The node to be deleted has a child node, and the node to be deleted is black
If the deleted node is black, its child nodes must be red (black does not satisfy property 5). Therefore, you only need to replace the deleted node with its child nodes and then change
Since the black node is removed, the child nodes need to be changed to black due to property 5. For example, delete node 8:
There are two child nodes
The node to be deleted can be replaced by the predecessor node (the maximum value in the left subtree of the node is deleted) or the successor node (the minimum value in the right subtree of the node is deleted). If the node is deleted by the successor node, there are two cases:
Therefore, replacing the node to be deleted with the successor node is transformed into deleting the successor node, and adjustment is made by judging the deletion of the successor node.
If the successor node is ① :
Case 5: A deleted node has two children
- Succeeded if the successor node is red
- There is no right child node, corresponding to case one
- If there is a right child node, it can only be black, which does not satisfy property 5, corresponding to case 3
- Succeeded if the successor node is black
- There’s no right child node. Case two
- If there is a right child node, the right child node cannot be black, but only red, corresponding to case four
If the successor node is (2) :
Case 6: The deleted node has two children
- Succeeded if the successor node is red
- There are no children, so case one
- If there are child nodes, they can only be black, which does not satisfy property 5, corresponding to case 3
- Succeeded if the successor node is black
- There are no children. Case two
- If there are child nodes, they can only be red, which corresponds to case four
Two nodes are deleted by the way of the successor node. If it is the way of the precursor node, it may be different, but the analysis process is the same.
summary
The red-black tree deletion here is analyzed according to whether the deleted node has child nodes, but to sum up the six cases above, case 5 and Case 6 are simultaneously transformed into one, two and four above, so we only need to master these three cases.
To determine which is the case, use the following order:
- First look at the color of the deleted node
- Let’s look at the colors of the brothers
- Then look at the color of the sibling child node (the sibling child node first looks at the sibling right child node right and then the sibling left child node)
- Finally, look at the color of the parent node
conclusion
When they study the red-black tree looked at a lot of data, at the same time also let me very headache, such as how to calculate it and add or delete AVL efficiency, clearly when the new rotation is twice the number of times, but some post said AVL is higher than 2 times, 10 article is 10, but I still insist on your record in practice.
No interviewer will ask you to write a red black tree in your hand. If so, give him the keyboard. He can do it. And it’s not very useful for us to actually develop it, and you probably won’t write a red black tree by hand for the rest of your life. For example, you won’t implement HashMap yourself, so there’s no need to knock red black trees all the time, we just need to know the basic logic, like how to rotate and balance when adding, Delete when how to rotate to maintain the balance of the logic is enough. After you have the ability to code, you are likely to be able to write a simple demo of your own, the premise of writing code is to know the logic clearly.
The code is provided here, and you can download it if you need it:
data-structure
Before someone asked how the GIF above was done, the data structure visualization:
Data Structure Visualizations
reference
- Redblack trees remove nodes — that’s enough
- What’s the difference between an AVL tree and a red-black tree