Tips:
- Red black tree is the search binary tree variant, can first understand AVLTree
- According to multiple sources, many people say that 2-3 trees and 2-3-4 trees are helpful for understanding red-black trees. (I haven’t had a deep understanding, but if you are interested, you can search relevant information by yourself, or wait for me to cheat the dead again.)
Red-black is the equivalent of a two-three-four tree. In other words, for every 2-3-4 tree, there exists at least one red-black tree whose data elements are in the same order. Insertions and deletions in a 2-3-4 tree are also equivalent to color flips and rotations in a red-black tree. This makes 2-3-4 trees an important tool for understanding the logic behind red-black trees, which is why many textbooks that introduce algorithms introduce 2-3-4 trees before red-black trees, even though 2-3-4 trees are not often used in practice. (wiki) - Different from AVL trees, red-black trees do not have the characteristics of some AVL trees, for example, the height difference between the left and right nodes of each node is less than 1
- As for why the new node must be red, I have not found a reasonable explanation (at present, it is only understood that red can avoid some cases that need to be repaired), and the reason may be found in the two-three-four tree
The demo code mainly refers to TreeMap
The nature of the
- Nodes are red or black.
- The roots are black.
- All leaves are black (leaves are NIL nodes).
- Each red node must have two black children. (There cannot be two consecutive red nodes on all paths from each leaf to the root.)
- All simple paths from any node to each of its leaves contain the same number of black nodes.
Node color repair
Rotation can be referred to AVLTree, but attention should be paid to the definition of left rotation and right rotation introduced in AVLTree. In this paper, left rotation is determined by direction, while left rotation is determined by subtree position above.
insert
Wikipedia lists several cases in detail, and HERE I will directly carry, and a little personal understanding, readers when reading, please wear “glasses” to avoid being misled by my bug.
- Properties one and three are always the same.
- Property 4 is only threatened when adding red nodes, redrawing black nodes to red, or doing rotations.
- Property 5 is only threatened when adding black nodes, repainting red nodes to black, or doing rotations.
Except for the first point, the other two points are very abstract. If you only rely on this to try to understand, you need to manually simulate the insertion of red-black trees. Below I will illustrate the problems encountered by plugging in 5 cases listed by wiki.
Note:Insert new nodes, must be leaf nodes (before the tree adjustment repair, readers can try manually, I will give a simple example)
Insert: 1,5,2,7,4,6,9,3
Case 1: The new node N is at the root of the tree and has no parent node. In this case, let’s redraw it in black to satisfy property two. Because it increases the number of black nodes by one per path, property 5 matches.
This means that the new node is the root of the tree, so we only need to ensure that the root of property 2 is black
Copy the codeCase 2: The parent P of the new node is black, so property 4 is not invalidated (the new node is red). In this case, the tree is still valid. Property 5 is also not threatened, although the new node N has two black leaf child nodes. But since the new node N is red, the path through each of its children has the same number of black nodes as the path through the black leaf it replaces, so it still satisfies this property.
Because the inserted nodes are red, they do not break the property.
Copy the codeCase 3: if the parent node P U both are red, and uncle node (the newly inserted node N as P left child node or right child nodes are 3, right here only show N as P left child), we can take them two redraw node G to red to black and paint grandfather (used to keep nature. 5). Now our new node N has a black parent P. Because any path through parent P or uncle U must go through grandfather G, the number of black nodes on these paths does not change. However, the red grandparent G could be the root, which violates property 2, or the parent G could be red, which violates property 4. To solve this problem, we recursively perform the entire process of case 1 on the grandparent G. (Use G as a newly added node to check various scenarios)
Note:In the remaining cases, we assume that the parent P is the left child of its parent G. If it is a right child, the left and right in case 4 and case 5 should be switched.
Case 4: The parent node P is red and the uncle node U is black or missing, and the new node N is the right child of its parent node P and the parent node P is the left child of its parent node. In this case, we do a left rotation to swap the roles of the new node and its parent; Next, we deal with the former parent P in case 5 to solve the still-invalid property 4. Note that this change causes some paths to pass through the new node N (such as leaf 1 in the figure) or not through node P (such as leaf 3 in the figure) that they did not pass before, but since both nodes are red, property 5 still holds.
Case 5: The parent node P is red and the uncle node U is black or missing. The new node N is the left child of its parent node, and the parent node P is the left child of its parent node G. In this case, we do a right rotation for the grandparent G; In the tree generated by the rotation, the previous parent P is now the parent of the new node N and the previous grandfather G. We know that the previous grandparent G is black, otherwise the parent P cannot be red (if both P and G are red it violates property 4, so G must be black). We switch the color of the previous parent node P and grandfather node G, and the resulting tree satisfies property 4. Property 5 also remains satisfied, because all paths through any of these three nodes used to go through the grandparent G, and now they all go through the previous parent P. In each case, this is the only black node among the three nodes.
delete
Node deletion We only need to consider that the deleted node has a child node or is itself a leaf node (a leaf node can also be regarded as having only one child node). Because the deleted node has two child nodes, the deletion scheme is to replace the precursor node (the left subtree is the largest) or the successor node (the right subtree is the smallest). Then remove the replacement node (the replacement node either has a single child node or a leaf node).
Case 1: Delete the red node, and the parent node and child node are black. It doesn’t break the property.
Case 2: Delete the black node and the child node is red. Child node promotion, color repair red to black, meet the nature of red-black tree.
Case 3 (4) : Delete the black node, the child node is also black (note the case of the twin node, delete the node to replace the node)
Case four is no longer listed separately
Note the examples in the deletionNo node 52
private void remove(Node<T> d) {
// The if judgment converts the binary case to a monad case
if (d.left ! = null && d.right ! = null) {
// The left and right nodes are not empty, and the node element to be deleted is assigned to the successor node element
// Note that node colors are not brought
Node<T> s = successor(d);
d.element = s.element;
// The pointer of the node to be deleted points to its successor node
d = s;
}
Node<T> replacement = (d.left ! = null ? d.left : d.right);
if (replacement ! = null) {
// At least one of the left and right nodes is not empty
replacement.parent = d.parent;
if (d.parent == null) {
// There are only two nodes in the tree,d is the root
root = replacement;
} else if (d == d.parent.left) {
// The node is the left node of the parent node
d.parent.left = replacement;
} else {
// The node to be deleted is the right node of the parent node
d.parent.right = replacement;
}
// Disconnect all links of the node to be deleted
// If the left and right nodes of the node to be deleted are not empty, d points to the subsequent node
d.left = d.right = d.parent = null;
// Fix replacement
// If the node to be deleted is red, you do not need to change the node color
if (d.color == BLACK) {
// At this point, the original node is deleted. Replacement is the new node
fixAfterDeletion(replacement);
}
} else if (null == d.parent) {
// The current tree has only the root node
root = null;
} else {
if (d.color == BLACK)
// The node to be deleted is leaf node
fixAfterDeletion(d);
if (d.parent ! = null) {
// If the node to be deleted is a leaf node
if (d == d.parent.left)
d.parent.left = null;
else if (d == d.parent.right)
d.parent.right = null;
d.parent = null;
}
}
}
// The node to be deleted has been deleted and replaced
private void fixAfterDeletion(Node<T> x) {
// Only nodes that are black need fixing
while (x ! = root && colorOf(x) == BLACK) {
/ / the left node
if (x == leftOf(parentOf(x))) {
Node<T> sib = rightOf(parentOf(x));
// Sibling is red, self is black, set to case 1
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
// The children of sibling nodes are black, set to case 2
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
// Only the right node of the sibling's children is black, set to case 3
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
// The right node of the sibling is red, set to case 4
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // symmetric
// Mirror symmetry
Node<T> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
Copy the code
Put it after the code in the hope that you can read the code first and then look at the process, so that it will be easier to understand
