A red-black tree is a balanced binary tree, but not a perfectly balanced binary tree. Although we would like a data structure in which all lookups end in ~lgN comparisons, it is too expensive to keep the tree perfectly balanced in dynamic inserts, so let’s relax a bit and try to find a data structure that can do lookups in logarithmic time. At this moment, the red-black tree stood out.
Read the following to understand the insert and delete operations of ordinary binary trees.
Red-black tree is formed by adding a color attribute to each node in a common binary tree, and the whole red-black binary tree should simultaneously satisfy the following five properties
There are five properties that red-black trees need to satisfy:
Property 1: The node is red or black;
The nodes in the tree are either red or black, and there’s nothing else, so it’s a red black tree, right?
Property 2: The root node is black;
The root node is always black. It can’t be red.
Property 3: Every leaf node (NIL or empty node) is black;
This might be a little hard to understand, but look at the picture:
So this picture is a red-black tree, and the NIL node is an empty node, and it’s black.
Property 4: The two children of each red node are black (that is, there are no two consecutive red nodes);
It means that two consecutive nodes can’t be consecutive red, and two consecutive nodes means that the parent node and the child node can’t be consecutive red.
Property 5: All paths from any node to each leaf node contain the same number of black nodes;
It can be seen from the figure above that there are three black nodes in the same number;
Everything we do when we insert or delete is to adjust the tree to conform to these five properties.
So let’s start with two basic operations, rotation.
The purpose of rotation is to transfer a node with more nodes to another node with fewer nodes. Rotation is often used in insert and delete operations, so memorize it.
Here are left and right:
L:
Right:
insert
Let’s talk about insertion
Let’s make it clear what each node is called
Because must satisfy the five properties of a red-black tree, if we insert a black node, it violated the nature of the five, need to be adjusted, mass if we insert node is red, it is only in being inserted in the parent node is red in violation of the nature of the four or when to insert the node is the root of nodes, the violation of the nature of the two, so, We change the color of the node we want to insert to red.
Here are a few possible insert situations:
1. When the inserted node is the root node, black it directly;
2. When the parent of the node to be inserted is black.
Inserting a red node at this point does not break any of these five properties. So you don’t have to adjust it.
3. If the parent node of the node to be inserted is red and the parent node is the left branch of the grandfather node.
This should be divided into two cases, one is the uncle node is black, one is the uncle node is red.
When the uncle is black, it is also divided into two situations. One is that the node to be inserted is the left branch of the parent node, the other is that the node to be inserted is the right branch of the father.
Let’s first look at the case where the node to be inserted is the left branch of the parent node:
In this case, property 4 is violated, so we need to adjust the operation to make it conform to property 4. We can switch the color of the grandfather node and the parent node by right-rotation, so that it becomes:
This adjustment can conform to property four without damaging other properties.
When the inserted node is the right branch of the parent node:
When the node to be inserted is the right branch of the parent node, we can rotate the parent node to the left first, as follows:
If we see the original parent node is new to insert a node, the former being inserted as a new parent node, it becomes when to insert a node in the case of the left branch of the parent node, yes, yes, is according to when being inserted in the case of the left branch of the parent node of rotation, rotation after into is as follows:
4. If the parent node of the node to be inserted is red and the parent node is the right branch of the grandfather node;
So this is a mirror image of what we’re talking about in case 3, so we can just switch the left and right of case 3.
5. If the parent node of the node to be inserted is red and the uncle node is also red, as follows:
At this point, just color the father node and uncle node black, and the grandfather node red.
So that’s all of the insertion.
delete
First you need to understand the normal binary tree deletion operation:
1. If you want to delete a leaf node, you can delete it directly.
2. If the element to be deleted has a child node, the child node can be moved directly to the location of the deleted element.
3, if there are two child nodes, elements can be deleted at this time the right branch of the minimum node (deleted elements right branch of the leftmost node) and swaps be deleted elements, we put the deleted element called subsequent right branch of the leftmost node (following element), and then according to the situation of case 1 or 2. As shown in figure:
Swap the deleted element with the smallest element on the right side, as shown below:
Then delete the deleted element:
The deleted elements referred to below refer to the deleted elements that have been exchanged.
After the addition of colors, the removed elements and their successors are interchangeable only, not interchangeable colors. Note this.
Let’s start with the red black tree deletion rules:
1. When the deleted element is red, it has no effect on the five properties and is directly deleted.
2. If the element to be deleted is black and is the root node, delete it directly.
3. When the deleted element is black and a right child node is red, black the right child node to the position of the deleted element, as shown in the figure:
by
become
4. When the deleted element is black and the sibling node is black, the two children of the sibling node are also black, and the parent node is red, the color of the sibling node and the parent node will be changed. NIL element means that each leaf node has two empty NIL elements that are black in color, which can be treated as two black elements when needed and ignored when not.
As shown in figure:
by
To:
5. When the deleted element is black and is the left branch of the parent node, and the brother is black and the right branch of the brother is red, it is necessary to exchange the colors of the brother and the father, and black the father and the right branch of the brother, and turn left with the parent node as the center. As shown in figure:
By:
To:
6. When the deleted element is black and is the left branch of the parent node, and the brother is black and the left branch of the brother is red, it is necessary to swap the color of the brother and the left child node of the brother and turn it right, and then it becomes the same as rule 5, and then rotate it according to Rule 5. As shown in figure:
by
The color of the left child node of the first sibling and the left child node of the first sibling are changed to the right and become:
Then rotate according to rule 5 to become:
7. If the deleted element is black and is the right branch of the parent element, it is the mirror of case 5. Case 6.
8. The deleted element is black and the sibling node is black. The child of the sibling node is black and the father is black.
By:
To:
9. When the deleted element is black, the left branch of the parent element, and the sibling node is red, the color of the sibling node and the parent node need to be switched, and the parent node is left rotated, which becomes case 4. The operation can be performed according to case 4, and the changes are as follows:
By:
Swap the color of the sibling node with the parent node, and make left-rotation with the parent node:
In accordance with the operation of case 4, become:
Ok, now that I’ve done deleting, one thing I didn’t do is always remember to change the color of the root element to black when adding and deleting.
There is no language implementation here, just the insertion and deletion steps of red black tree, you can follow the steps to implement the red black tree yourself.
Click here to build a red-black tree step by step.
The last
1, the implementation of a red-black tree is a tree of 2, 3, 4, just will double node or three points marked in red, if you put the red nodes in the same height and its parent element, and put it as an element and the parent element, you can discover, turned into a highly for lgN binary tree, the tree 2.3.4 of great enlightening significance to the red-black tree.
2. The above steps can be derived without rote memorization, because we are rebalancing a balanced red-black tree that has been disrupted by insertion or deletion, giving way by rotation, and changing the red-black color to conform to the five basic properties. Such as four meeting the delete operation situation, we can remove that removing elements, found the left than the right one less black element, this time, how to do, we found that siblings child element has a red element, this will not affect the nature of the five operation, so we through change color, rotation, can let the two sides of the number of black.
3. The purpose of the rotation operation is to transfer an element to another place and conform to the properties of the binary tree. The purpose of the color swap is to maintain the five properties of the red-black tree.
4, always remember that all operations are to maintain the five properties.
Finally, there is a simpler red-black binary tree. This simple red-black binary tree is actually a 2.3 tree. It only allows the left node to be red, but it is definitely not as good as the red-black tree. This simple red and black binary tree is introduced in the fourth edition of algorithm. After mastering this simple red and black binary tree, it will feel simple and easy.
The last of the last of the last, must try to deduce their own insert delete rules ah, or often forget, is a sleep up to see a little meng force of the kind of forget.