There are a lot of red-black tree jokes on the Internet, and many people say that red-black trees only exist in jokes, not in interviews or real projects. Take a look at what people are saying:
Usually, if an interviewer asks me the number red and black. I usually turn around and walk away. Not because it’s not the job to ask. It’s because. I TMD really no – – | | |
A lot of people looked at this netizen said, feel very piercing. Don’t worry, here’s something more poignant:
It’s so hard! Map map = new TreeMap(); Manual squint, that’s done
But yes, TreeMap is built with a red-black tree. Learning red-black tree is not just for the interviewer, martial arts novels say: moves are just a form, to practice magic, must understand the mind. This article will take you slowly away from the red – black tree veil, especially in the article dynamic graph will let you feel the rotation of the red – black tree is very intuitive. Of course, if you understand this article, your job interview will be easy
As we know, binary search tree is a good data structure, can quickly find a given keyword of the data items, and can quickly insert and delete data items. The problem with binary search trees, however, is that if random data is inserted into the tree, it performs very well, but if ordered or reversed data is inserted, the binary search tree performs very slowly. Because when numeric order is inserted, the binary tree is not balanced, and when placed on a line, it becomes a linked list… Its ability to quickly find, insert, and delete specified data items is lost.
To search a tree in fast O(logN) time, the tree needs to always be balanced (or at least mostly balanced), which means that for each node in the tree, the number of descendants to its left should be roughly equal to the number of descendants to its right. A red-black tree is such a balanced tree. For an item to be inserted, the insertion routine checks whether it will break the characteristics of the tree. If it does, the program will correct it, changing the structure of the tree as needed to keep the tree balanced. So what are the characteristics of red-black trees?
1. Characteristics of red-black trees
It has two main characteristics: 1. The nodes have color; 2. Follow rules to keep these colors in different permutations during inserts and deletions. The first feature is easily solved by adding a data field, such as a Boolean variable, to the node class to represent the color information of the node. The second feature is more complicated. Red-black trees have several rules, and if they follow these rules, then the tree is balanced. The main rules for red-black trees are as follows:
-
1. Each node is either red or black;
-
2. The root node is always black;
-
3. If the node is red, its children must be black (and vice versa);
-
4. Each path from root node to leaf node or empty child node must contain the same number of black nodes (that is, the same black height).
It is no accident that nodes inserted into red-black trees are all red, because inserting a red node is less likely to violate the red-black rule than inserting a black node. The reason: inserting a black node always changes the black height (against Rule 4), but inserting a red node only half the time violates Rule 3. Also, a violation of Rule 3 is easier to fix than a violation of Rule 4. This balance can be broken when a new node is inserted, so how is the red-black tree corrected?
2. Balance correction
Red-black trees modify their balance in three main ways, changing node color, left and right rotation. This seems a little abstract, so let’s go through them separately.
2.1 change color
Changing the node color is easier to understand because it violates rule 3. Suppose you now have A node E, and then you insert node A and node S, and node A is on the left child, and node S is on the right child. If another node is inserted at this point, then there is an imbalance, because the children of the red node must be black, but the newly inserted node is red. So you have to change the node color. So we change the two children of the root from red to black (more on why both are changed when we insert them below) and the parent node from black to red. It can be shown in the following schematic diagram:
2.2 a left-handed
Usually the left-handed operation is used to rotate a red link that leans to the right to the left. The schematic diagram is as follows:
Left-handed rotation has a lovely dynamic diagram that you can easily understand:
3 right-lateral
Right-handed rotation is just the opposite to left-handed rotation. I won’t repeat it here, just look at the schematic diagram:
Of course, dextral rotation also has a cute motion picture:
There are three main ways to correct the balance of red-black trees. We have a perceptual understanding, so when to correct? Which fixes should be used when? That’s what we’re going to talk about.
3. Red-black tree operation
The basic operations of red-black trees are add, remove, and rotate. What kind of rotation is used to correct the balance of red-black trees that may be disturbed by additions or deletions? We first introduce the nodes of red-black tree, and then analyze the specific implementation of left-handed and right-handed respectively. Finally, we discuss the specific operation of red-black tree.
3.1 Nodes of red-black tree
The red-black tree is an improvement on the binary search tree, so the nodes are similar to the binary search tree, except that a Boolean variable is added to represent the node color.
public class RBNode<T extends Comparable<T>>{
boolean color; / / color
T key; // Keyword (key)
RBNode<T> left; // Left child node
RBNode<T> right; // Right child node
RBNode<T> parent; / / the parent node
public RBNode(T key, boolean color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
public T getKey() {
return key;
}
public String toString() {
return "" + key + (this.color == RED? "R" : "B");
}
}
Copy the code3.2 Concrete realization of left-handed rotation
The concept of left-handedness is already perceptual, so I will not repeat it here. Let’s explore the concrete implementation of left-handedness from the following code combined with the diagram above:
/************* Left-rotate the red-black tree node x ******************/
/ *
* Left-turn schematic: Left-turn the node X
* p p
* / /
* x y
* / \ / \
* lx y -----> x ry
* / \ / \
* ly ry lx ly
* Left-handed rotation does three things:
* 1. Assign the left child of y to the right child of x, and assign x to the parent of the left child of y (when the left child of y is not null)
* 2. Assign the parent of x to the parent of y, and update the child of P to y(left or right)
* 3. Set the left child node of y to x and the parent node of x to y
* /
private void leftRotate(RBNode<T> x) {
//1. Assign the left child of y to the right child of x and x to the parent of the left child of y (when the left child of y is not null)
RBNode<T> y = x.right;
x.right = y.left;
if(y.left ! = null)
y.left.parent = x;
//2. Assign the parent of x to the parent of y, and update the child of P to y(left or right)
y.parent = x.parent;
if(x.parent == null) {
this.root = y; // If the parent of x is empty, set y to the parent
} else {
If (x == x.parent.left) // if x is the left child
x.parent.left = y; // set y to the left child as well
else
x.parent.right = y; // Otherwise set y to the right child
}
//3. Set the left child of y to x and the parent of x to y
y.left = x;
x.parent = y;
}
Copy the code3.3 Concrete realization of dextral rotation
The concept of dextral rotation has been perceptual understanding, and there is no need to repeat here, let’s explore the specific implementation of dextral rotation from the following code combined with the diagram above:
/************* Perform right-rotation on the red-black tree node y ******************/
/ *
* Schematic diagram of left rotation: Perform right rotation on node Y
* p p
* / /
* y x
* / \ / \
* x ry -----> lx y
* / \ / \
* lx rx rx ry
* Dextral does three things:
* 1. Assign the right child of x to the left child of y and y to the parent of the right child of X (when the right child of x is not null)
* 2. Assign the parent of y to the parent of x, and update the child of P to x(left or right)
* 3. Set the right child node of x to y and the parent node of y to x
* /
private void rightRotate(RBNode<T> y) {
//1. Assign the left child of y to the right child of x and x to the parent of the left child of y (when the left child of y is not null)
RBNode<T> x = y.left;
y.left = x.right;
if(x.right ! = null)
x.right.parent = y;
//2. Assign the parent of x to the parent of y, and update the child of P to y(left or right)
x.parent = y.parent;
if(y.parent == null) {
this.root = x; // If the parent of x is empty, set y to the parent
} else {
If (y == y.parent.right) // If x is the left child
y.parent.right = x; // set y to the left child as well
else
y.parent.left = x; // Otherwise set y to the right child
}
//3. Set the left child of y to x and the parent of x to y
x.right = y;
y.parent = x;
}
Copy the code3.4 Insertion Operations
After analyzing the major rotation operations in red-black trees, let’s move on to the common insert, delete, and so on. Let’s start with the insert operation. Since red-black tree is an improvement of binary search tree, the first half of insert operation works the same, that is, find the position to be inserted first, and then insert the node. Let’s look at the first half of insert code:
/ * * * * * * * * * * * * * * * * * * * * * * * to the red-black tree insert node * * * * * * * * * * * * * * * * * * * * * * /
public void insert(T key) {
RBNode<T> node = new RBNode<T>(key, RED, null, null, null);
if(node ! = null)
insert(node);
}
// Insert a node into a red-black tree, the same process as a binary search tree
private void insert(RBNode<T> node) {
RBNode<T> current = null; // Represents the parent of the last node
RBNode<T> x = this.root; // It is used to search down
//1. Find the insertion position
while(x ! = null) {
current = x;
int cmp = node.key.compareTo(x.key);
if(cmp < 0)
x = x.left;
else
x = x.right;
}
node.parent = current; // Find the location of the current node as the parent node
//2. Then determine whether node is inserted into the left or right child node
if(current ! = null) {
int cmp = node.key.compareTo(current.key);
if(cmp < 0)
current.left = node;
else
current.right = node;
} else {
this.root = node;
}
//3. Re-shape it into a red-black tree
insertFixUp(node);
}
Copy the codeThis is exactly the same idea as the binary search tree, and I won’t go over it here, but let’s look at the last step in the method, insertFixUp. Because the tree may be unbalanced after insertion, the insertFixUp method is mainly discussed by case, analyzing when to change color, when to turn left, when to turn right. Let’s start with a theoretical analysis of the specific case, and then look at the implementation of the insertFixUp method.
If it is the first time, the original tree is empty, so it only violates rule 2 of red-black trees, so just black out the root node. If the parent of the inserted node is black, it does not violate the rules of red-black trees; nothing needs to be done; But there are three situations where we start to change color and rotate:
-
1. The parent node of the inserted node and its uncle node (another child node of the grandfather node) are both red;
-
2. The parent node of the insert node is red, the uncle node is black, and the insert node is the right child of its parent node.
-
3. The parent node is red, the uncle node is black, and the parent node is the left child node of the parent node.
Let’s take a look at each of the three cases and then give the implementation code.
For case 1: the parent of the inserted node and its uncle node (another child of the grandfather node) are both red. In this case, there must be a grandparent, but we don’t know if the parent is the left child or the right child, but because of the symmetry, we just have to figure out what happens on one side, and the other case will also happen on the other. Consider the case where the parent node is the left child of the grandfather node, as shown in the left figure below:
In this case, we will do the following: black the parent node (5) and uncle node (8) of the current node (4), and red the grandfather node (7), as shown in the upper right figure. Then point the current node to its grandfather node and start the algorithm again from the new current node (see the program below for details). So this becomes case 2.
For case 2, the parent of the inserted node is red, the uncle node is black, and the inserted node is the right child of its parent. We need to do the following operations: take the parent node (2) of the current node (7) as the new node, and use the new current node as the fulcrum to perform left-rotation operation. This is done as shown in the lower left, so the lower left becomes case 3.
In case 3: the parent node of the inserted node is red, the uncle node is black, and the inserted node is the left child node of the parent node. We need to do the following operations: black the parent node (7) of the current node, red the grandfather node (11), right rotation on the grandfather node as the fulcrum. Finally, the root node is blackened, and the entire red-black tree is restored to balance, as shown in the upper right. At this point, the insert is complete!
We can see that if is from 1 began to happen, will walk the case 2 and 3, that is to say, this is the whole process, of course, in practice may not occur from case 1, if the starting condition 2, can adjust it to walk again a case 3, the if directly by adjusting case 3, the first two are not need to be adjusted. Therefore, the sequence relationship between discoloration and rotation can be expressed as: discoloration -> left-rotation -> right-rotation.
At this point, we are done inserting. Let’s take a look at the implementation of the insertFixUp method.
private void insertFixUp(RBNode<T> node) {
RBNode<T> parent, gparent; // Define parent and grandparent nodes
// The parent node exists and its color is red
while(((parent = parentOf(node)) ! = null) && isRed(parent)) {
gparent = parentOf(parent); // Get the grandparent node
// If the parent node is the left child of the grandfather node, else does the opposite
if(parent == gparent.left) {
RBNode<T> uncle = gparent.right; // Get the uncle node
//case1: Uncle node is also red
if(uncle ! = null && isRed(uncle)) {
setBlack(parent); // Black out the parent and uncle nodes
setBlack(uncle);
setRed(gparent); // Color the grandfather node red
node = gparent; // Place the location at the grandfather node
continue; // continue while, rejudge
}
//case2: The uncle node is black and the current node is the right child node
if(node == parent.right) {
leftRotate(parent); // Rotate left from the parent node
RBNode<T> tmp = parent; // Then swap the parent node with yourself in preparation for the following right-handed rotation
parent = node;
node = tmp;
}
//case3: The uncle node is black and the current node is the left child node
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
} else {// If the parent node is the right child of the grandfather node, it is the opposite of the above, and the essence is the same
RBNode<T> uncle = gparent.left;
//case1: Uncle node is also red
if(uncle ! = null & isRed(uncle)) {
setBlack(parent);
setBlack(uncle);
setRed(gparent);
node = gparent;
continue;
}
//case2: The uncle node is black and the current node is the left child node
if(node == parent.left) {
rightRotate(parent);
RBNode<T> tmp = parent;
parent = node;
node = tmp;
}
//case3: The uncle node is black and the current node is the right child node
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
// Set the root node to black
setBlack(this.root);
}
Copy the code
Big cock-a-doody monkey rich generation
I have calculated that the profit per click of the advertisement below is 0.7 yuan
↓↓ ↓↓ ↓ Click below to support