To read this article, you need to know:
- Binary search tree (js version of the simple implementation can refer to binary search tree simple learning)
- Get a pen and paper (draw it yourself so you can really understand it)
- We recommend a good online red-black tree generation site (this can not demonstrate the process) :Virtual
- We all recommend the use of this online generation, but can not open, later I found the original website, he posted in his blog domain name, we can use: online generation
1. How to use red black tree in Libuv?
Libuv applies the red-black tree algorithm to signal. Let’s review how signal is used:
uv_signal_t signal_handle;
r = uv_signal_init(loop, &signal_handle);
CHECK(r, "uv_signal_init");
r = uv_signal_start(&signal_handle, signal_cb, SIGINT);
void signal_cb(uv_signal_t *handle, int signum) {
printf("signal_cb: recvd CTRL+C shutting down\n");
uv_stop(uv_default_loop()); //stops the event loop
}
Copy the codeEvery time the developer calls uv_signal_start, a node is inserted into the generated red-black tree. When the developer calls uv_signal_stop, a node is removed as follows:
static int uv__signal_start(uv_signal_t* handle, uv_signal_cb signal_cb, int signum, int oneshot) { ... . RB_INSERT(uv__signal_tree_s, &uv__signal_tree, handle); . . } static void uv__signal_stop(uv_signal_t* handle) { ... . removed_handle = RB_REMOVE(uv__signal_tree_s, &uv__signal_tree, handle); . . }Copy the codeLibuv defines a complete set of red-black tree implementations in macro form (source code in tree.h). Since macro code seems to be a bit of a drag, I’ve taken a screenshot of it. You can take a look at it:
Red black trees themselves are a very difficult concept to understand, plus C, so it’s not very friendly. So I according to the REALIZATION of C language, rewrite into Js version, the following explanation is based on Js language, so we do not panic ~
2. Basic concepts of red-black trees
2.1. Why are red-black trees needed?
Red black trees are based on binary search trees, so are binary search trees bad? Do you have to make another complicated one? The binary search tree is already a good data structure, which 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. Like the one below
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 process is checked to see if it will break the characteristics of the tree. If it does, the program will correct it and change the structure of the tree as needed to keep the tree balanced.
Why are there more scenes for red black trees between AVL and red black trees? In fact, this is a performance balance problem. Although AVL node search is better than red black tree, because of its strict conditions, it needs to do more operations in each insertion and deletion than red black tree. So sacrifice a little bit of search time to ensure that performance is not too bad each time a node is inserted or removed.
2.2 Features of red-black tree
- Property 1: Each node is either black or red.
- Property 2: The root node is black.
- Property 3: Each leaf node (NIL) is black.
- Property 4: Every red node must have two black children.
- Property 5: The path from any node to every leaf node contains the same number of black nodes.
Then, according to the above characteristics, there are the following inferences:
- Corollary 1: A red-black tree cannot have two red nodes next to each other
- Corollary 2: The shortest possible path in the tree is a path with all black nodes
- Corollary 3: The longest possible path in the tree is one where red nodes alternate with black nodes
- Corollary 4: Every path contains the same number of black nodes, so a red-black tree ensures that no path is twice as long as any other
- Corollary 5: If a node has sunspots, it must have two children
Thus, we get the data structure of the node:
functionNode(data) { this.leftNode = null this.rightNode = null this.parentNode = null this.data = data this.rbColor = RED // The reason why it is initialized to red is explained below.Copy the code2.3 Correction operation of red-black tree
Redblack tree corrections are based on rotations and discoloration, because we need to understand left and right rotation before we can understand what happens when we insert a node.
2.3.1, left-handed
Here is a left-handed animation:
As can be seen from the figure, the so-called left rotation means that the node to be rotated moves to the left, that is, to move counterclockwise. The operation is completed by the following three things:
- Assign the left child of S to the right child of E, and E to the parent of the left child of S (when the left child of E is non-null)
- Assign E’s parent p(non-null) to E’s parent, while updating the child of the parent before E to y(either left or right, depending on where E is at the time)
- Set the left child of S to E and the parent of E to S
According to the above introduction, the code implemented with Js is as follows (the comments in the code refer to the comments at the top of the function) :
/ * * * * * * * * * * * * * to the red and black tree node x for left-handed operation * * * * * * * * * * * * * * * * * * / / * * sinistral diagram: Left-handed * p p * / / * x y * / \ / \ * lx y -----> x ry * / \ / \ * ly ry lx ly * Left-handed 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, P (non-null), to the parent of y, and update the child of P to y(left or right) * 3. Let's set the left child of y to be x, The x's parent is set to y * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / rotateLeft (beRotatedNode) {/ / right from x node y const RightNode = beRotatedNode. RightNode // the rightNode of the x node is changed, RightNode = rightNode. LeftNode // if the leftNode of y has a value, x will be the parent of the leftNode of yif(rightNode leftNode) {rightNode. LeftNode. ParentNode = beRotatedNode} / / will be assigned to y x's parent node's parent rightNode. ParentNode = Berotatednode. parentNode // if the parentNode of x existsif(berotatedNode. parentNode) {// If the x node is the left node of its parentif (beRotatedNode === beRotatedNode.parentNode.leftNode) {
beRotatedNode.parentNode.leftNode = rightNode
} else {
beRotatedNode.parentNode.rightNode = rightNode
}
} else{// If the parent of x is empty, then the root is this.root = rightNode} // 3. RightNode. LeftNode = beRotatedNode beRotatedNode. ParentNode = rightNode}Copy the code2.3.2, right
The right-handed operation is the opposite of the left-handed operation and still has animation:
The specific will not be described, the code is as follows:
/ * * * * * * * * * * * * * right on red and black tree node y for operation * * * * * * * * * * * * * * * * * * / / * * right-lateral diagram: Right-handed * p p * / / * y x * / \ / \ * x ry -----> lx y * / \ / \ * lx rx rx ry * Right-handed does three things: * 1. Assign the right child of x to the left child of y, and assign y to the parent of the right child of X (when the right child of x is non-null) * 2. Assign y's parent p(non-null) to x's parent, and update P's child to x(left or right) * 3. BeRotatedNode const leftNode = beRotatedNode. LeftNode // change the leftNode of y, Berotatednode. leftNode = leftnode. rightNode // if the rightNode of x has a value, then y will be the parent of the rightNode of xif(leftNode rightNode) {leftNode. RightNode. ParentNode = beRotatedNode} / / will be assigned to the x y parent node's parent leftNode. ParentNode = Berotatednode. parentNode // If y's parent existsif(berotatedNode. parentNode) {// If y is the left node of its parentif (beRotatedNode === beRotatedNode.parentNode.leftNode) {
beRotatedNode.parentNode.leftNode = leftNode
} else {
beRotatedNode.parentNode.rightNode = leftNode
}
} else{// If the parent node of x is empty, the root node is this.root = leftNode} // 3. Set the leftNode of x to y and the parentNode of y to x leftnode. rightNode = beRotatedNode beRotatedNode. ParentNode = leftNode}Copy the code3. Red-black tree insertion
Now, before we get into insertion, let’s agree on a few terms so we don’t get confused when we read the code together. The diagram below:
The names of all nodes are clearly marked, and subsequent insert and delete operations are based on these names.
Nodes are first inserted in a binary search tree and colored in red. If the color is black, it will violate nature 5 and is inconvenient to adjust; If the bar is red, it may violate property 2 or 4, and can be restored to its red-black tree properties by relatively simple operations.
What are the steps required to insert a node into a red-black tree? First, instantiate a new node, and then use the red-black tree as a binary lookup tree to find the appropriate location to insert the node. Finally, the tree is modified to become a red-black tree again through a series of operations such as “rotation and recolor”.
Detailed description is as follows:
3.1. Step 1
Instantiate a new node as follows: const node = new node (data)
3.2. Step 2
Think of the red-black tree as a binary search tree to find a suitable location for node insertion. The logic of this step search is actually very simple, summarized as follows:
- Based on the value of the node, traverse from the root node to find the parent node suitable for insertion
- Associate the inserted node with the parent node
The implementation code is as follows:
__insert(node) {
let root = this.root
let parent = null
letCompareRes // 2. Find the appropriate location of the insert node and establish a connection with its parent nodewhile(root ! == null) {parent = root compareRes = node.data - root.data // If the inserted node is larger than the current parent node, then continue to look for the right node of the parent nodeif (compareRes > 0) {
root = root.rightNode
} else if (compareRes < 0) {
root = root.leftNode
} else {
returnParentNode = parent parentNode = parent parentNode = parent parentNode = parentNodeif (parent) {
if (compareRes < 0) {
parent.leftNode = node
} else {
parent.rightNode = node
}
} elseThis.__insert_color(this. Root, node)return null
}
Copy the code3.3. Step 3
Through a series of operations such as rotation or coloring, it becomes a red black tree again.
If it is the first time, since the original tree is empty, it will only violate feature 2 of the red-black tree, so just black out the root node. If the parent of the inserted node is black, that doesn’t violate the red-black tree, nothing needs to be done;
However, when we encounter three situations (collectively referred to as Scenario 3), we begin to change color and rotate:
-
The parent node and its uncle node of the inserted node are red.
-
The parent node of the insert node is red, the uncle node is black, and the insert node is the right child node of its parent node.
-
The parent node of the insert node is red, the uncle node is black, and the insert node is the left child of the parent node.
As a corollary to this scenario, remember that if the inserted parent is red, it cannot be root, so the inserted parent always has a grandparent.
Scenario 3.1. The uncle node exists and is red
From red-black tree property 4, the grandparent must be black, because you can’t have two connected red nodes at the same time. Then the number of red and black layers to be inserted into the subtree is: black, red and red. Obviously the easiest way to do this is to change it to: red black red.
So the treatment is:
Set the parent node and uncle node to black set the grandfather node to red set the grandfather node to the current insertion node and continue to adjust the red-black treeCopy the codeScenario 3.2 the uncle node does not exist or is black, and the parent of the inserted node is the left child of the grandfather node
Purely for insertion, uncle nodes are either red or leaf Nil. Because if the uncle is black and the parent is red, then the child tree that the uncle is in has more black nodes than the child tree that the parent is in, which doesn’t satisfy the red-black tree property 5. The same is true of the subsequent scenarios, and I won’t elaborate any more.
As we said before, when you need to rotate, you have to have more or fewer nodes on one side of the tree, and you have to rent or lend them to the other side. If you insert more nodes, you can just rent the nodes to the other subtree.
Scenario 3.2.1 the insert node is the left child of its parent
Two red nodes on the left, none on the right, so one on each side is just fine, and because it’s red, it certainly won’t upset the balance of the tree. So the treatment is:
I'm going to make the parent black and the grandparent red and I'm going to rotate the grandparent rightCopy the codeScenario 3.2.2. The insert node is the right child of its parent
This scenario can obviously be rotated to normalize the problem to the situation in section 3.2.1, so the treatment is as follows:
Left-spin the parent node, set the parent node as the insertion node, and continue processing after normalization to the situation in Section 3.2.1Copy the codeScenario 3.3, the uncle node does not exist or is black, and the inserted parent node is the right child of the grandfather node
This scenario corresponds to scenario 3.2, but the direction is reversed, and the conclusion is directly given without too much explanation.
Scenario 3.3.1. The insert node is the right child of its parent
Treatment:
I'm going to make the parent black and the grandparent red and I'm going to rotate the grandparent leftCopy the codeScenario 3.3.2. The insert node is the right child of its parent
Treatment:
Rotate the parent node to the right, set the parent node as the insertion node, and continue processing after normalization to section 3.3.1Copy the codeTo sum up, the code implemented is as follows, with comments that correspond to all of the above:
__insert_color(root, node) {
let parent = node.parentNode
letGparent, uncle // Neither case 1 nor case 2 will enter thiswhile// Only the third case is entered, that is, the parent exists and the parent is redwhile(parent ! RbColor === RED) {gparent = parentNode // If the parent node is the left node of the grandfather nodeif(parent === gparent.leftNode) {uncle = gparent.rightNode //case3.1 Case: If the uncle node exists and its color is redif(uncle && uncle. RbColor === RED) {// 1, set the uncle node, the parent node, the grandfather node to BLACK and RED uncle. RbColor = BLACK parent Gparent. RbColor = RED // 2, set the parent node to the current nodecontinue} / /case3.2.2 If the uncle node does not exist or the uncle node is black and the inserted node is to the right of the parent node // because this situation will eventually be normalized tocase3.2.1, so it needs to be executed firstif(parent. RightNode === node) {// Rotate this.rotateleft (parent) // after rotation, you need to reset uncle = parent parent = node node = uncle} // The above condition will be normalized to the last conditioncase3.2.1: The uncle node does not exist or the uncle node is black, RbColor = BLACK gparent.rbColor = RED // 2 This.rotateright (gparent) // Update the parent node parent = node.parentNode}elseUncle = gparent. LeftNode // Uncle = gparentcase3.1 Case: If the uncle node exists and its color is redif(uncle && uncle. RbColor === RED) {// 1, set the uncle node, the parent node, the grandfather node to BLACK and RED uncle. RbColor = BLACK parent Gparent. RbColor = RED // 2, set the parent node to the current nodecontinue} / /case3.3.2 If the uncle node does not exist or the uncle node is black and the inserted node is to the right of the parent node // because this situation will eventually be normalized tocase3.3.1, so it needs to be executed firstif(parent. LeftNode === node) {// Rotate this.rotateright (parent) // after rotation, reset uncle = parent parent = node node = uncle} // One of the above cases will be normalized to the last casecase3.3.1: The uncle node does not exist or the uncle node is black, RbColor = BLACK gparent.rbColor = RED // 2 Parent = node.parentNode}} this.root. RbColor = BLACK}Copy the codeDelete red black tree
Deletes a node in a red-black tree. The operations to be performed are as follows: First, the red-black tree is regarded as a binary search tree, and the node is deleted from the binary search tree; The tree is then modified to become a red-black tree again through a series of “rotations and recolors”. Detailed description is as follows:
Step 1: Treat the red-black tree as a binary lookup tree and remove the nodes. This is the same as “deleting deleted nodes in a regular binary lookup tree”. There are 3 cases:
(1) The deleted node has no son, that is, it is a leaf node. Then, simply delete the node.
② The deleted node has only one son. Then, simply delete the node and replace it with its only child node.
③ The deleted node has two sons. So, first find its successor node (that is, the smallest node larger than the deleted node); In this case, the successor node acts as a surrogate and is deleted after the contents of the successor node are copied to the deleted node. This neatly transforms the problem into a case of “remove the successor node”, so let’s consider the successor node. In the case that the “deleted node” has two non-empty children, its successors cannot be twin non-empty. Since the successor of the node cannot be both twins, it means that the successor of the node has either no son or only one son. If there is no son, proceed as “situation ①”; If there is only one son, proceed as “case ②”.
This leads us to the following corollary: deleting a node can be regarded as deleting a replacement node, and the replacement node always ends up at the end of the tree
The schematic diagram is as follows:
Step 2: Modify the tree to become a red black tree again by “rotating and recoloring”.
This is because removing nodes in Step 1 May violate the properties of red-black trees. So it needs to be “rotated and recoloured” to correct the tree and make it a red-black tree again.
4.1. Step 1
Based on the situation listed above, deal with three cases. The implementation code is as follows:
__remove(node) {
letReplaceNode = node // If the left and right nodes of the deleted node are not emptyif(node.leftNode && node.rightNode) {// Find the successor node of the deleted node (the smallest node larger than the deleted node) as the replacement nodelet replaceNode = node.rightNode
while(replaceNode.leftNode) { replaceNode = replaceNode.leftNode } node.data = replaceNode.data } const parent = ParentNode const color = replacenode. rbColor / / if the removed node node, then here is replaced node, and replace the node left node is certainly does not exist, only the right node or null child = const replaceNode. RightNode | | replaceNode. LeftNodeif (child) {
child.parentNode = parent
}
if (parent) {
if (parent.leftNode === replaceNode) {
parent.leftNode = child
} else {
parent.rightNode = child
}
} else {
this.root = child
}
if (color === BLACK) {
this.__remove_color(child, parent)
}
replaceNode = null
}
Copy the codeIf the node that happened to be deleted is black, then we begin our red-black tree reconstruction
4.2. Step 2
The reconstruction of red-black tree requires reconstruction only when the replacement node is black, so ignore scenario 1(the replacement node is red node) and directly say scenario 2:
Scenario 2.1. The replacement node is the left child of its parent
Scenario 2.1.1. The sibling of the replacement node is a red node
Treatment:
Set the sibling to black and the parent to red and left-rotate the parent to normalize to scene 2.1.2.3
Scenario 2.1.2. The sibling of the replacement node is black
This scenario is divided into different scenarios according to the child nodes of the sibling node
Scenario 2.1.2.1. The right child of the sibling of the replacement node is red, and the left child is any color
I’m going to set the color of the sibling to be the color of the parent and the parent to be black and the right sibling to be black and I’m going to rotate the parent to the left
Scenario 2.1.2.2. The right child of the sibling of the replacement node is black and the left child is red
Set the sibling node to red, set the left node of the sibling node to black, and perform dextral rotation for the sibling node, which is normalized to scene 2.1.2.1 for processing
Scenario 2.1.2.3. The children of the sibling of the replacement node are all black
Set the sibling node to red and delete the parent node as the new replacement node
Scenario 2.2. The replacement node is the right child of its parent
Scenario 2.2.1. The sibling of the replacement node is a red node
Set the sibling node to black and the parent node to red to right-rotate the parent node and normalize to scene 2.2.2.3
Scenario 2.2.2. The sibling of the replacement node is black
Scenario 2.2.2.1. The left child of the sibling of the replacement node is red, and the right child is any color
I’m going to set the color of the sibling to be the color of the parent and I’m going to set the parent to be black and I’m going to set the left of the sibling to be black and I’m going to rotate the parent
Scenario 2.2.2.2. The left child of the sibling of the replacement node is black and the right child is red
Set the sibling to red, set the right node of the sibling node to black, and rotate the sibling node left to normalize to scene 2.2.2.1
Scenario 2.2.2.3 The children of the sibling of the replacement node are all black nodes
Set the sibling node to red and delete the parent node as the new replacement node
The complete implementation code is as follows:
__remove_color(node, parent) {// node represents the node to be corrected, i.e. the children of the successor node (since the successor node has been removed).let brother
while((node === null || node.rbColor === BLACK) && node ! // Scenario 2.1, the replacement node is the left child of its parentif(node == parent.leftNode) {brother = parent.rightNode // Fetch sibling // Scenario 2.1.1, the sibling of the replacement node is a red nodeif(brother. RbColor === RED) {brother. RbColor = BLACK parent. RbColor = RED this.rotateleft (parent) // Normalize to scene 2.1.2.3 Brother = parent.rightnode} // Scenario 2.1.2, the sibling of the replacement node is black // Scenario 2.1.2.3, the child of the sibling of the replacement node is blackif ((brother.leftNode === null || brother.leftNode.rbColor === BLACK) && (brother.rightNode === null || brother.rightNode.rbColor === BLACK)) {
brother.rbColor = RED
node = parent
parent = node.parentNode
} else{// Scenario 2.1.2.2. The right child of the sibling of the replacement node is black, and the left child is redif (brother.rightNode === null || brother.rightNode.rbColor === BLACK) {
if(brother. LeftNode) {brother. Leftnode. rbColor = BLACK} brother This.rotateright (brother) brother = parent.rightNode} Brother. RbColor = parent. RbColor parent. RbColor = BLACKif (brother.rightNode) {
brother.rightNode.rbColor = BLACK
}
this.rotateLeft(parent)
node = this.root
break}}else{// Scenario 2.2, the replacement node is the right child of its parent, brother = parent. LeftNode // Scenario 2.2.1, the replacement node's brother is redif(brother. RbColor === RED) {brother. RbColor = BLACK parent. RbColor = RED Brother = parent.leftnode} // Scenario 2.2.2, the sibling of the replacement node is black // Scenario 2.2.2.3, the child of the sibling of the replacement node is blackif ((brother.leftNode === null || brother.leftNode.rbColor === BLACK) && (brother.rightNode === null || brother.rightNode.rbColor === BLACK)) {
brother.rbColor = RED
node = parent
parent = node.parentNode
} elseScenario 2.2.2.2 The left child of the sibling of the replacement node is black and the right child is redif (brother.leftNode === null || brother.leftNode.rbColor === BLACK) {
if(brother. RightNode) {brother. RightNode. RbColor = BLACK} brother. RbColor = RED / / 2.2.2.1 normalized to the scene after the left-handed This.rotateleft (brother) brother = parent.leftnode} // Scenario 2.2.2.1, the left child of the brother of the replacement node is red, RbColor = parent. RbColor parent. RbColor = BLACKif (brother.leftNode) {
brother.leftNode.rbColor = BLACK
}
this.rotateRight(parent)
node = this.root
break}}}if (node) {
node.rbColor = BLACK
}
}
Copy the codereference
- 30 pictures to help you understand red black trees from top to bottom
- Red black tree (2) C language implementation