preface
Good morning, I’m Tong Ge.
In the last video, we talked about the nature of red-black trees from binary trees, binary search trees, balanced trees, AVL trees, 2-3 trees, two-three-four trees, AND B trees. Finally, we came to the essence of red-black trees: red-black trees are two-three-four trees. Please see the picture below:
We know that the principle of two-three-four insert, delete and find elements is fairly simple, so can we use two-three-four trees to remember red-black trees?
The answer is yes. In this video, we’re going to take a look at how to use two-three-four trees to quickly learn red-black trees without having to memorize them
Ok, let’s move on to today’s lesson.
Have the 2-3-4 tree again
Let’s give a picture to briefly review the process of inserting element N into a 2-3-4 tree:
Concern princess number tong elder brother read source code, view the content of the previous section.
Left red black tree, right red black tree, AA tree
Before explaining the red black tree, Tong Brother will introduce some interesting concepts to you first, which are left red black tree, right red black tree and AA tree.
Picture too small? Try landscape!
In fact, according to the concept of red-black tree, the above three trees are all red-black trees, and the elements are identical, so it can be said that they are different varieties of the same red-black tree.
A careful student would have noticed that ① and ② had evolved from the same two-three-four tree, and ③ that the two-three-four tree had shrunk into a two-three-three tree.
So what exactly is a red-black tree?
A red-black tree is a binary lookup tree where each node has a color attribute, either red or black.
First, a red-black tree is a binary search tree. In addition, it must meet the following five requirements:
- Nodes are red or black;
- The root node is black;
- All leaf nodes are black; (Leaf node is NULL node)
- Two children of each red node are black; (There cannot be two consecutive red nodes on the path from the root node to each leaf node.)
- All paths from any node to each leaf node contain the same number of black nodes;
You don’t need to memorize this concept, because it’s really hard to remember it, but tong Ge will teach you an easier way.
So, do you see all three graphs above are red black trees?
Not really, because some of the leaves are red.
Actually, they’re all red-black trees, so let me fill them out:
Take a closer look. Do you meet the five rules? !
So, you see, if YOU draw any tree, it might meet the definition of a red-black tree, so for the sake of memory, we’re going to divide red-black trees into these types: left-leaning red-black trees, right-leaning red-black trees, and AA trees.
LLRB (left-learning red-black Tree), if a node has Red children, then its Red children are tilted to the Left.
How do you understand that?
The leaves are all null nodes. That’s the classic red-black tree. There’s no such requirement in Tongog.
Let’s see, a node has either one child or two children, right.
What if this node has a red child, one or two, if there’s only one red child, then that child can only be on the left, if there’s two red children, you don’t care.
Therefore, in the whole red-black tree, if there are red nodes, they can only be in the following two forms:
Similarly, RLRB (right-learning red-black Tree) is the same, that is, the Red child node is tilted to the Right, and its Red child node can only be in the following two forms:
All right, both left – and right-leaning red-black trees are fairly normal, and there’s also a twisted red-black Tree called the AA Tree.
Of course, instead of going Dutch at dinner, AA is the abbreviation of the author’s name: Arne Andersson.
In AA tree, all the red child nodes in the red-black tree must be the right node, and the left child node is not allowed to be the red child node. Therefore, in AA tree, the red child node can only be the following form:
It can also be interpreted as severely rightist (will I get a tea date for saying that?).
Actually, the AA tree can be viewed as a two-three-four tree to the right, rather than a two-three-four tree, so you can draw a picture of that.
There is also the possibility of a red black tree, for example, the red child node can only be the left child node, whether it is called BB tree, I don’t know, there is another possibility of a red black tree like the following:
This tree up here, it has both red children on the left and red children on the right, and it actually fits the definition of a red black tree, so it’s just a normal red black tree.
Given that there are so many different forms of red-black trees, how do we quickly remember them?
It’s hard. It’s really hard. So, we only need to remember one form, like a left-leaning red-black tree, and all the other forms are the same, no strong form memory at all.
So, I’m going to use the left-leaning red-black tree as a whole, which is a little different from the classic red-black tree, and unlike anything you’ve seen before, so please don’t get tangled up.
Interesting insert element
First, let’s agree on one thing: the inserted node must be red, but if it’s the root node, color it black.
With this convention in mind, we slowly unpack the insertion process in a red-black tree using a step-by-step diagram.
-
Insert the first element F
The first element, which must be the root node, is directly colored black:
-
Insert the second element
There are two cases: less than F, greater than F.
(1) Suppose the inserted element is D, then, it is smaller than F, so it will become the left child node of F:
Now, D is the red left child, so there’s no need to rebalance.
(2) Suppose the inserted element is K, then, it is larger than F, so it will become the right child node of F:
In this case, K is the red right child, which does not conform to the rules of left-leaning red-black trees, so you need to rebalance. So how do you rebalance?
So let’s go back to the nature of red-black trees — two-three-four trees, and red-black trees with F and K would be two-three-four trees:
And if YOU take this two-three-four tree and convert it to a left-leaning red-black tree, it becomes:
Let’s draw a comparison:
So, you see, it’s really easy to understand a red-black tree with a two-three-four tree, which would be a normal three-node for a two-three-four tree, but for a red-black tree it would be like inserting a right child node, and then doing a left-handed color change.
-
Insert the third element
Let’s take the red-black tree of F and K as an example and add another element to it. There are three possible cases, which we can analyze one by one:
(1) Suppose the inserted element is D, which is smaller than F, so it will become the left child node of F:
At this point, it doesn’t fit the definition of a red-black tree, so we need to rebalance. So how do we balance? Come on, above:
If you insert D, for a two-three-four tree you get a four-node, but for a red-black tree you have to go through a right-handed re-color process.
(2) Suppose the inserted element is G, which is larger than F and smaller than K, so it will become the right child node of F:
Obviously, it also doesn’t fit the definition of a red-black tree, so it also needs rebalancing:
Insert element G, for a two-three-four tree, just to form an ordinary four-node, while for a red-black tree, you need to rotate F left to become the same state as in case (1), then rotate G right to change color, and finally rebalance to red-black tree.
(3) Suppose the inserted element is N, which is larger than K, so it will become the right child node of K:
At this point, it fits the definition of a red-black tree, so it doesn’t need to be rebalanced, but let’s draw the same picture for comparison:
Ok, so from the above analysis, I inserted three elements in a row, and you can see that for two-three-four, they all form a four-node, and for red-black trees, they all end up like this:
So, let’s insert a fourth element.
-
Insert the fourth element
Let’s take the red-black tree F K N as an example, and insert the fourth element. There are four possible situations, that is, one of the four child nodes of F and N, respectively. To simplify things, let’s go straight to the figure above:
(1) Suppose D, which is the left child node of F
(2) Suppose G, which is the right child node of F
(3) Suppose M, which is the left child node of N
(4) Assume Q, which is the right child node of N
Ok, so this is the end of the four elements, and you can see that when you insert the fourth element, for a two-three-four tree, you get a five node, and then you split, and for a red-black tree, you go through a bunch of left turns, right turns, discoloration, and then you get the two-three-four tree, isn’t that funny? ^^
-
Insert fifth element
I’m so tired of drawing, I leave it to you
Remove elements
Whether it’s a two-three-four tree or a left-leaning red-black tree, deleting elements is a lot more complicated than inserting elements, so let’s look at deleting elements in a two-three-four tree.
The 2-3-4 tree deletes elements
To illustrate, I constructed a two-three-four tree like the one below:
For the 2-3-4 trees, delete nodes 3 or 4 leaf node is the most simple, such as C and D P Q R both leaf nodes, delete the two nodes of an arbitrary element can be deleted directly, after 4 node to delete an element into 3 nodes, 3 after delete an element node into two nodes, does not affect the balance of the original tree, for instance, After C is deleted, the result is as follows:
However, deleting two nodes is different. For example, in the figure above, deleting nodes A, B, F, G, H, J, L and N directly will cause the tree to be unbalanced. Therefore, some measures should be taken to ensure that the tree is still balanced after deleting L.
The answer is — steal!
Yes, it’s stealing, stealing elements from other places to fill the gap, just like we’re paddling at work, always looking for something to fill the hours, right?
So, how do you steal it?
In general, there are two main categories: children steal from their parents, parents steal from their children, and stealing may involve merging or migrating elements.
Let’s take A look at how the process of deleting nodes A, B, F, G, H, J, L and N is stolen. Please be careful with the following pictures.
(1) Delete A
When deleting an element A, steal A B from the parent node. When B is empty, steal A C from its right child node.
(2)
Deleting B is easy, just steal C from the right child node.
(3) Delete F
The process of deleting F is more complicated. In short, it always revolves around a principle: if the child node fails to steal, it should steal the parent node, and the stolen elements may be merged or migrated.
The rule of merging is always to keep the whole tree in order, for example, if you steal an I from the parent node, it’s bigger than H, so H has to be on the left child of I, and the left child already has G, so you have to merge them.
Similarly, the process of moving J is the same, so J has to be to the left of K, and it has to be to the right of I.
(4) Delete G
In fact, it is the same as stealing I when deleting F, so I won’t go into details.
(5) Delete H
The process is exactly the same as that of deleting F.
(6) Delete J
When deleting J, steal K from the parent node first, and then the parent node becomes 3 nodes. Therefore, directly merge the two elements to the left of M.
(7) Delete L
The process of deleting L is similar to the process of deleting J, in that it steals K from the parent node and then merges the two elements to the left of M.
(8) Delete N
When deleting N, the parent steals an O, and the parent steals a P from its right child
Ok, so far, two-three-four tree to delete elements of the process of the complete analysis, I this example almost contains all the scenes, please draw more carefully experience, although draw want to vomit blood.
Left-leaning red-black tree deletes elements
Note: Deletion of red-black trees is a little more complicated, and would be more complicated if strong types were tied to a 2-3-4 tree, so the following is not exactly tied to a 2-3-4 tree.
First, I’d like to ask a question: how can a binary lookup tree remain a binary lookup tree after deleting elements?
If it’s a leaf node, you delete it and it doesn’t matter, but what about non-leaf nodes? For example, delete the M element.
In fact, there are two ways: one is to find the leading node of M and get the position of M, and the other is to find the successor node of M and get the position of M.
What is a front node? What is a successor node? It’s like you’ve only heard of parents and children in binary trees, right?
We know that binary search trees are essentially ordered, and this order refers to the natural order of elements (and the insertion order).
So, if you sort all the elements in the binary tree, the node before M is the leading node, and the node after M is the successor node.
Another way to visualize this is that the largest element in the left subtree of M is the leading node of M, and the smallest element in the right subtree of M is the successor node of M.
So, after deleting M, it is ok to move L or N to the position of M, at this point, we can ensure that the binary search tree is still a binary search tree.
But everyone seems to like the succeeded node, the smallest node in the right subtree and if you look at the source code you will see a word called the succeeded node.
Okay, so that’s all we have to say about binary search trees deleting elements, but let’s go back to red-black trees deleting elements.
To illustrate, I constructed the following red-black tree:
Let’s look at one of the simplest case, if you remove the leaf node is red, for example, above the three elements of C, P, R, if only it so it’s parent a child node, delete it directly, what also don’t tube, such as C, if its parent node has two child nodes, then will be divided into two cases, one kind is to remove the right child node, the direct delete, For example, R, or the left child that you delete, you do a simple left rotation, like P.
We’re talking about a left-leaning red-black tree, and if it’s a classic red-black tree, there’s no rotation required to remove the red leaf node.
OK, let’s look at the second case, what if we delete the black leaf node?
We know that once the black node is removed, it’s definitely not a red-black tree, so there’s definitely some rebalancing going on.
If you look at the classic red-black tree, and you look at the color of its sibling, and maybe the color of its sibling’s children, there are three or four different ways that you can’t remember, but I’m going to give you a better way to make sure that you remember it once you look at it.
Let’s take the deletion of node F as an example. I first give the diagram and then describe the detailed steps:
It’s very simple, F is the black node, right, so figure out how to make it red, how to make it red?
You have to start with the upper node, the red of the upper node can actually be passed down, and then the whole tree is still a red black tree, and it doesn’t break the balance of the original red black tree, until F becomes a red leaf node, and then it’s easy to delete it.
This approach is much easier to understand than the classic red-black tree approach.
Let’s take another example of removing L, directly above:
Okay, so that’s all about removing leaf nodes, but what if you’re deleting non-leaf nodes, like E.
According to the characteristics of binary search trees, then we will find a F E subsequent node, then move it to the position of E, but, at this point, do not meet the definition of a red-black tree, so you can see, in fact, delete the E is equivalent to indirectly delete F the source node position, therefore, and transformed the delete the leaf node of the above.
It’s a very simple process, and you end up with essentially the same result as if you were to delete F, except that the element where E was is now F, so I’m not going to draw it.
You can think of the process of deleting M
Finally finished, it is not easy to see the students here, may have exceeded the time for a breakfast, I am sorry!
Afterword.
In this section, we start from the essence of red-black trees, namely two-three-four trees, and completely master a way to understand red-black trees without rote memorization. Have you got it? Feel free to leave a comment.
M: Talk is cheap, show me the code!
Ok, in the next section, I will show you the code, please look forward to it!
Pay attention to princess “Tong Elder brother read source code”, unlock more source code, foundation, architecture knowledge.