Foreplay red and black trees are both familiar and unfamiliar to many children. Familiarity is the focus of studying in school and preparing for interviews. And then after years of neglect, it’s almost forgotten now. If you’re reading this, you’re about to graduate and under pressure to find a job. Or maybe you feel like you need to go over it all over again. Or just look at it. Congratulations, you’ve earned it. So I’m going to reintroduce you to red black trees, and in simple language, understand red black trees.
Before we study red-black trees, we need to understand binary search trees (BST).
Binary search tree
To understand binary search trees, let’s first look at what are the properties of binary search trees?
1, all nodes in the left subtree are less than or equal to the value of their root node
2, all nodes on the right subnumber are greater than or equal to the value of its root node
3. The left and right subtrees must also be binary sort trees respectively
If we look at the tree below, it is a typical binary search tree
So the question is, why does it have to be this way? In other words, what’s good about this structure? So let’s look for the value of 10. How does it find this node step by step? What are the steps? And then we look down.
1, find the root node 9, see the following figure:
2. Since 10 is greater than 9, we find 13 on the right, see the picture below:
3, and because 10 is small and 13, so find the left child 11, look at the picture below:
4, this is a step that we don’t have to go through and we all know, we find the left kid, and we find exactly 10. That’s exactly what you’re looking for.
May have children shoes will ask, this is not the idea of binary search? Indeed, the maximum number of lookups required is equal to the height of the binary lookup tree. Of course, when inserting nodes, this is the same idea, layer by layer to find the right place to insert. However, binary search trees have a relatively large defect, and this defect will affect its performance. Let’s first look at an insert operation in one case:
If the initial binary search tree had only three nodes, the following figure would look like this:
We insert five nodes in turn: 7,6,5,4,3. Look at the inserted image below:
Can you see that? Do you feel uncomfortable, if the root node is large enough, it is not the “left leg” will become extremely long, that is to say, the search performance is compromised, almost linear search.
Is there a good way to solve this problem? Solve the imbalance caused by multiple insertion of new nodes? That’s where the red-black tree comes in.
A red-black tree is a balanced binary search tree. A red-black tree is balanced by the fact that it does not become “lame” with a long left leg or a long right leg. In addition to the characteristics of the binary search tree, it also has the following characteristics:
- Nodes are red or black
- The root node is black
- Each leaf node is a black NULL node.
- Two children of each red node are black.
- All paths from any node to each of its leaves contain the same black node.
Here is a typical red-black tree:
A lot of kids are going to be surprised, oh my god, that’s a lot of rules. Yes, because of these rules, red black trees are self-balanced. The maximum path is not more than twice the minimum path.
When nodes are inserted and removed, the balance is disturbed and the tree needs to be adjusted to regain balance. So when does it break the rule of a red-black tree?
1. Let’s look at the figure below:
Insert a new node with a value of 14 into the original red-black tree. Since the parent node 15 is black, this situation does not break the structure and no changes are required.
2. Insert 21 into the original tree? , see the figure below:
Since the parent node 22 is red, this situation breaks rule 4 of red-black trees and must be adjusted. So how exactly should adjust? There are two ways to change color and rotate, divided into left rotation and right rotation.
【 discoloration 】 :
In order to conform to the rules of red-black trees, nodes are red to black or black to red. The figure below shows the portion of a red-black tree. Note that node 25 is not the root node. Since links 21 and 22 appear in red, it does not comply with rule 4, so make 22 red black:
But this still does not comply with rule 5, so we need to change 25 black to red, as shown below:
You think it’s over by now? Naive, since 25 and 27 are two consecutive red nodes (rule 4), you need to turn 27 red to black.
It’s finally over. It’s all rules. It’s much more comfortable.
[Left rotation]
In other words, rotate two nodes counterclockwise so that the parent node is replaced by his right child and he becomes his left child.
[Right rotation]
Rotate the two nodes clockwise so that their parent node is replaced by the left child and they become their right child.
It looks so complicated. How do you use it? It’s really complicated. Let’s talk about a typical example for your reference:
Take the example of just inserting 21 nodes:
The first thing we need to do is change the color of node 25 and the nodes below:
Since the root node must be black, it needs to change color, resulting in the following image:
There are two paths (17-) 8->6->NULL) where the number of black nodes is not 3, but 4. Take 13 as X and 8 as Y and rotate it to the right:
Finally change color according to the rules:
So we’re finally done, adjusted to the rules.
So with all this effort, all this complexity, where is this going to be used, what are the applications?
In fact, the MAP in STL is a red-black tree.
Conclusion:
The general idea of red and black is described above, there are many situations to consider, this article is simply about the idea, you can go to Baidu to see the consideration of various situations. Thank you for your support!