preface
Originally only in the application and simple idea of understanding to introduce the creation and use of red black tree. During this period of time, I want to have an in-depth study of red-black tree, mainly referring to wikipedia content, plus some of my own understanding and learning, and try to truly implement this data structure. Today, Koizumi will take you hand lift red black tree! Without further ado, our red-black tree journey is about to begin.
define
As usual, I’m going to give you the definition of a red black tree, but let’s take a look at what a red black tree looks like on Wikipedia.
Wikipedia Red black tree (Red — black tree) is a self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. It was invented by Rudolf Bell in 1972 and is known as the “symmetric binary B tree”, and its modern name derives from a paper written by Leo J. Guibas and Robert Sedgewick in 1978. Red-black trees have a complex structure, but their operations have a good worst-case run time and are efficient in practice: it can find, insert, and delete in O(log n) time, where n is the number of elements in the tree.
The definition of unpretentious is no different from the introduction I gave you in the last article, so I just took it. Cough cough cough 、、、、
Properties:
- Nodes are only red or black
- The root node must be black
- The leaf node must be a black NULL node.
- The left and right child nodes of the red node are black nodes
- Any node has the same number of black nodes to its leaf node
The five properties of red-black trees are important to keep in mind as we go along.
Algorithm on
Koizumi will take you to start our red and black tree journey, sit well, sit well, start.
So our first stop is going to be our nodes and we’re going to go through the basic details of our red-black tree operations.
Nodes in a red-black tree
Node properties
According to the properties of red-black trees, we know that nodes of red-black trees must have at least properties: store value, left and right child nodes, node color, and parent node.
From this point of view, it seems that there is only one more color than the general binary tree. In addition, we know that the most annoying thing of binary tree is the node before the node (such as the parent node of a node, the uncle node, etc.). Therefore, in order to achieve the purpose of efficiency, the node of red-black tree also contains 5. The parent node.
- Stored value
- The left child node
- The right child node
- The node color
- The parent node
Find relevant nodes
- Finding grandfather nodes
- Finding tertiary nodes
- Finding sibling nodes
In fact, this wave of operations is easy to understand, mainly in preparation for various “rotation” operations, the rotation process must involve three generations of “people” (nodes) things. So these three operations to find relevant nodes are necessary.
For the sake of brief description, the nodes are named as follows:
Current node N, parent node P, grandfather node GP, uncle node U, brother node S, NIL (note not NULL).
Code — node
class Node{
public Node parent = null;
public Node left = null, right = null;
public int val = 0;
public COLOR color = COLOR.RED;
public Node(a){}public Node(Node parent, Node left, Node right, int val) {
this.parent = parent;
this.left = left;
this.right = right;
this.val = val;
}
Node grandParent(a) {
if (parent == null) {return null;
} else {
returnparent.parent; }}Node uncle(a) {
if (parent == grandParent().left) {
return grandParent().right;
} else {
returngrandParent().left; }}Node sibling(a) {
if (this == parent.left) {
return parent.right;
} else {
returnparent.left; }}}Copy the codeThe first is left-handed
Left-handed: N floats up and P sinks. The left subtree of N becomes the right subtree of P, and P becomes the left child of N. N then becomes the left child (or right child) of the GP node.
The initial state P is the left child of GP, and the same is true for the right subtree.
The first is dextral
Dextral: N floats up and P sinks down. The right subtree of N becomes the left subtree of P, and P becomes the right child of N. N then becomes the left child (or right child) of the GP node.
Here we also give the case where the initial state P is the left child of GP, and the right subtree is not described here.
The above left and right rotation is based on the deepest node N, followed by another rotation with the above intermediate P node as the N node. The advantage of this is that there is no need to introduce a grandparent node (because you need to call a function to find it every time).
The second is left-handed
Left-rotation: NR (right child node of N) floats and N sinks. The right subtree of NR becomes the left subtree of N, and N becomes the right child node of NR. NR then becomes the left child (or right child) of the P node.
This is the same as the case where the initial state N is the left child of P.
The second is dextral
Dextral: The NL node floats up and the N node sinks. The right subtree of the NL node becomes the left subtree of the N node, and the N node becomes the right child of the NL node. NL then becomes the left child (or right child) of P.
This is also the case where the initial state N is the left child of P.
As for left-right rotation, Koizumi’s principle takes the deepest node as the reference node N, that is, the first left-right rotation.
Code — Rotation
public void rotate_right(Node n) {
Node gp = n.grandParent();
Node p = n.parent;
p.left = n.right;
if(n.right ! = NIL) { n.right.parent = p; } n.right = p; p.parent = n;if (root == p) {
root = n;
}
n.parent = gp;
if(gp ! =null) {
if (gp.left == n.parent) {
gp.left = n;
} else{ gp.right = n; }}}public void rotate_left(Node n) {
Node gp = n.grandParent();
Node p = n.parent;
p.right = n.left;
if(n.left ! = NIL) { n.left.parent = p; } n.left = p; p.parent = n;if (root == p) {
root = n;
}
n.parent = gp;
if(gp ! =null) {
if (gp.left == n.parent) {
gp.left = n;
} else{ gp.right = n; }}}Copy the codeRed black tree creation
With the basics of red-black trees covered, we’ll move on to red-black tree creation.
We measure the efficiency of a data structure in three main ways: query, insert, and delete. These three aspects are also the three unavoidable operations in creating data structures.
The query
In fact, the query process is relatively simple, that is, according to the rules of binary search tree time complexity O(logn) can be queried. Query operations are not our primary concern.
The following insertion and deletion operations need to consider whether the structure of the final tree still conforms to the five properties of red-black tree, and then adjust the corresponding tree structure.
Hold on! We’re going to speed up!
insert
- To ensure property 5 (the same number of black nodes in the path from any node to the leaf node), the default inserted nodes are all red nodes.
- Insert nodes replace NIL nodes, and then adjust the tree structure. (This simplifies our classification of insertion cases without considering the problem of its own child nodes)
The two-point insertion rule is important, and note that the tree structure is adjusted after the insertion, otherwise you will get confused about the classification of the cases.
From shallow to deep, there are many cases of insertion, so let’s start with the simplest.
Case 1. The new node N is inserted at the root node
Insert the root node, assign the left and right child nodes to NIL, and leave the parent node empty.
Since the new nodes are all red, and the root node must be black according to property 1, another color-changing operation is needed to end the insertion operation.
Case 2. A new node N is inserted, and its parent node P is black
Insert after the black P node, since the inserted node is the red node, so in this case, the insert operation does not break any properties, end.
Case 3. The new node N is inserted, and its parent node P is red, and its tertiary node U is also red
For insertion of N nodes, and U P node if it is red node, N nodes also to red, then 4 violates the nature, and also because U node to red, so the GP nodes into red, P, U nodes change color to black which can conform to the nature of the four makes the tree structure and path node number are consistent with the black nor contrary to nature. 5.
However, this introduces the problem that GP’s parent may be red or GP may be the root node, at which point GP nodes need to be inserted (equivalent to inserting a new red node).
Case 4. A new node N is inserted. The parent node P is red, the tertiary node U is black, P is the left (right) child node of GP, and N is the right (left) child node of P
For case 4, we first do a left (right) rotation, adjust the position to the above position, and then go to case 5. Property 5 still satisfies, but not property 4.
Case 5. A new node N is inserted. The parent node P is red, the tertiary node U is black, P is the left (right) child node of GP, and N is the left (right) child node of P
For case 5, we first to a right of P, P buoyancy, GP to sink, so will make the right and left sides of the rotating after P black node number is not the same (because black GP sink node, rotating and get to the leaf node P left subtree leaf node will be less than right subtree arrive after a black), so the color again for operation, P color is black, If GP changes color to red, property 4,5 can be satisfied.
At this point, the insertion operation is explained, from the simplest insertion of the root node, to the parent node, tertiary node color has covered all cases. Now it’s full speed ahead, buckle up, and the more complicated deletion operation is about to begin.
Code — insert
private void insert(Node n, int data) {
if (n.val >= data) {
if(n.left ! = NIL) insert(n.left, data);else {
Node tmp = newNode(); tmp.val = data; tmp.left = tmp.right = NIL; tmp.parent = n; n.left = tmp; insertAdjust(tmp); }}else {
if(n.right ! = NIL) insert(n.right, data);else {
Node tmp = newNode(); tmp.val = data; tmp.left = tmp.right = NIL; tmp.parent = n; n.right = tmp; insertAdjust(tmp); }}}private void insertAdjust(Node n) {
// Case 1: the insertion point is the root
if (n.parent == null){
root = n;
n.color = COLOR.BLACK;
return;
}
// Case 2: the parent node is black and inserting a red node has no effect
if (n.parent.color == COLOR.RED) {
// Scenario 3: The parent node is red, the tertiary node is red ====
if (n.uncle().color == COLOR.RED) {//
n.grandParent().color = COLOR.RED;
n.parent.color = n.uncle().color = COLOR.BLACK;
insertAdjust(n.grandParent());
} else {
// Case 4: parent node is red, tertiary node is black. The parent is the left subtree, and the node is the right subtree ====
if (n.parent.right == n && n.grandParent().left == n.parent) {
rotate_left(n);
insertAdjust(n.left);
} else if (n.parent.left == n && n.grandParent().right == n.parent) {
// Case 4: parent node is red, tertiary node is black. The parent node is the right subtree, which is the left subtree ====
rotate_right(n);
insertAdjust(n.right);
}else if (n.parent.left == n && n.grandParent().right == n.parent) {
// Case 5: parent node is red, tertiary node is black. The parent node is the left subtree, which is the left subtree ====
n.grandParent().color = COLOR.RED;
n.parent.color = COLOR.BLACK;
rotate_right(n.parent);
} else{ n.grandParent().color = COLOR.RED; n.parent.color = COLOR.BLACK; rotate_left(n.parent); }}}}Copy the codedelete
To delete, red and black tree takes a little skill, if you want to delete a node, you need to the node in the left subtree or right subtree of the minimum maximum substitution to the node, then remove to replace node, which is equivalent to the node were transferred to have only one child (child nodes is empty nodes NIL) also can be thought of only one child node of the node.
In this paper, Koizumi uses the minimum value of the right subtree.
Ok, so we know that the final conversion is to handle nodes with only one child. Therefore, most of the discussion in the following paper is about how to adjust the structure of the tree according to the minimum position of the original right subtree after deletion.
As shown in the figure, the stored value of X is the value we want to delete (the previous replacement value work has been done), and the N node is the child node of this X node. Therefore, when we delete X, N will replace the position of X, and the subsequent explanation is based on such prerequisite.
So when the deleted node is black, we will still discuss several cases from simple to complex.
Case 1. Delete node X as the root node
Removing the root is simple, no additional action is required, and the above substitutions are done.
Case 2. The deleted node X is black and its child node N is red
We can just change the color of the child node to black to satisfy the five-point property.
Case 3. After node X is deleted, child node N of node X is in red, and N is the left (right) child node of parent node P
First, a left rotation operation is performed to make S become the new GP node of N, then the color of P node turns red and S node turns black, so that the number of black nodes from S to each leaf node is the same.
However, there is still a problem. The number of paths from P to leaf node is inconsistent, that is, p-X-n is now P-N, that is, one black node is missing. At this point, the situation continues to push down to the following situation to solve.
Case 4. After node X is deleted, P node, S node, SL node, and SR node of child node N of X are black, and N is the left (right) child node of parent node P
In this case, since the rest of the p-n path has one less black node, changing the color of the S node to red causes the black nodes to be the same between the arriving paths through P.
However, the difference between the black node that goes through P and that does not go through P is still 1, so the structure of the P node needs to be adjusted.
Case 5. After node X is deleted, P node is red, S node, SL node, and SR node are black, and N is the left (right) child node of parent node P
Case 6. After node X is deleted, S node is black, SL node is red, SR node is black, and N is the left (right) child node of parent node P
Case 7. After node X is deleted, S node and SL node are black, SR node is red, and N is the left (right) child node of parent node P
In case 7, SR was directly left rotated to change color, and then P node sank to change color, and S node kept the same color as the original P node. In this way, the black nodes through the path of the original P node are fully filled, and the number of black nodes in the right subtree does not change, maintaining the property of 5.
At this point, we of the construction of the red and black to on end, the article as much as possible all the all the insert and delete operations, and restore its process, according to the basic operation of these red and black tree along with pictures are better understood, so there is no too much explanation, for insert and delete operations, we consider the fourth and fifth nature then change color + the majority can be solved.
Code — delete
private Node getSmallestChild(Node n) {
if (n.left== NIL) {
return n;
}
return getSmallestChild(n.left);
}
private boolean delete(Node n, int data) {
if (n.val > data) {
if(n.left == NIL) {
return false;
}
return delete(n.left, data);
} else if (n.val < data) {
if (n.right == NIL) {
return false;
}
return delete(n.right, data);
} else if (n.val == data){
if (n.right == NIL) {
deleteOneChild(n);
return true;
}
Node smallest = getSmallestChild(n.right);
int tmp = n.val;
n.val = smallest.val;
smallest.val = tmp;
deleteOneChild(smallest);
return true;
} else {
return false; }}private void deleteOneChild(Node n) {
Node child = n.left == NIL ? n.right:n.left;// N has only one subtree
if (n.parent == null && n.left == NIL && n.right == NIL) {
// Case 1: Delete the root node with no left or right child nodes;
n = null;
root = n;
return;
}
if (n.parent == null) {
// Case 1: Delete the root node and have left or right child (but only one child).
child.parent = null;
root = child;
root.color = COLOR.BLACK;
return;
}
// Delete node X
if(n.parent.left == n) {
n.parent.left = child;
} else {
n.parent.right = child;
}
child.parent = n.parent;
if(n.color == COLOR.BLACK) {
// The deleted node X is red. No further action is required. If it is black, there will be one less black node in the path to the leaf node
if (child.color == COLOR.RED) {
// Case 2: the deleted node X is black and its children are red, so the children become black.
child.color = COLOR.BLACK;
} else {
// Adjust the tree structuredeleteAdjust(child); }}}private void deleteAdjust(Node n){
if (n.parent == null) {
n.color = COLOR.BLACK;
return;
}
Case 3: after node X is deleted, its child node N is black, so look at the color of its brother node S
// If it is red, you can rotate it and then change color. S becomes black, P becomes red, and N remains a child of P.
// But then, from P, the path to the leaf through N and not through N will still differ by one node (the node we deleted) p-x-n = p-n
// Enter the following situation
if (n.sibling().color == COLOR.RED){
n.parent.color = COLOR.RED;
n.sibling().color = COLOR.BLACK;
if (n == n.parent.left) {
rotate_left(n.sibling());
} else{ rotate_right(n.sibling()); }}// Case 4: After node X is deleted, the child node N is black, and the parent node, brother node S and child nodes of S are black. After the color changes, adjust the parent node of N
if (n.parent.color == COLOR.BLACK && n.sibling().color == COLOR.BLACK
&& n.sibling().left.color == COLOR.BLACK && n.sibling().right.color == COLOR.BLACK) {
n.sibling().color = COLOR.RED;
deleteAdjust(n.parent);
} else if (n.parent.color == COLOR.RED && n.sibling().color == COLOR.BLACK
&& n.sibling().left.color == COLOR.BLACK && n.sibling().right.color == COLOR.BLACK){
// Case 5: After node X is deleted, its child node N is black, its parent node is red, its brother node S and its child nodes are black, so change the color of P and S to complement the black nodes in the p-n path.
n.sibling().color = COLOR.RED;
n.parent.color = COLOR.BLACK;
} else {
if (n.sibling().color == COLOR.BLACK) {
// Case 6: N is the left child of P, the left child of S is red, and the right child is black, so change color + left rotation, and then enter case 7
if (n == n.parent.left && n.sibling().left.color == COLOR.RED && n.sibling().right.color == COLOR.BLACK) {
n.sibling().color = COLOR.RED;
n.sibling().left.color = COLOR.BLACK;
rotate_left(n.sibling().left);
} else if(n == n.parent.right && n.sibling().right.color == COLOR.RED && n.sibling().left.color == COLOR.BLACK) { n.sibling().color = COLOR.RED; n.sibling().right.color = COLOR.BLACK; rotate_left(n.sibling().right); }}// Case 7: N is the left child of P, S is the left child of black, and S is the right child of red, then dextral + color change
n.sibling().color = n.parent.color;
n.parent.color = COLOR.BLACK;
if (n == n.parent.left) {
n.sibling().right.color = COLOR.BLACK;
rotate_left(n.sibling());
} else{ n.sibling().left.color = COLOR.BLACK; rotate_right(n.sibling()); }}}Copy the codeconclusion
Brake ！！！！ It’s a bit of a rush. After watching the delete operation, after watching our entire red-black tree creation process, we also need to slow down, think about the beauty of this, and understand why it has a lower time complexity, why it is more efficient. For insert and delete, it is recommended to read over and over again to understand the progression and relationship between these situations, and to think about some of them.
Well, this time the hand tearing red black tree to this end, Koizumi’s algorithm training journey continues.