This is the 14th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021
The statement
- At the end of this paper, the insertion and deletion algorithms of red-black trees will be implemented using Java language, so this paper describes red-black trees from the perspective of Java, for example, leaf nodes will be represented by NULL instead of nil.
- The red-black tree is actually a self-balanced binary search tree. If you do not know binary search tree, you can read the article “Java implementation of binary search tree Introduction”. The following content assumes that you already know binary search tree, so you will no longer focus on the characteristics of binary search tree.
The definition of a red-black tree
Advantages of red-black trees over binary search trees
The red-black tree itself is a binary search tree.
Binary search trees are unbalanced and degenerate into linked lists when they are unbalanced, in the worst case, O(n).
The red-black tree is each node in a binary search tree painted black or red (through a sign to describe), through the way of meet certain rules to make the tree balance (is not very perfect balance), it can make the tree insert and delete query operations even in the worst case, can also be done in O (log n) time (n is the number of nodes in the tree).
The history of red-black tree naming
This is a quote from Wikipedia, translated as follows:
In A 1978 paper, “A Dichromatic Framework for Balanced Trees,” Leonidas J. Guibas and Robert Sedgewick obtained red-black Trees from symmetric binary B Trees. The color “red” was chosen because it was the best color produced by the color laser printer available to the author while working at Xerox PARC. Guibas’ other response was that trees could be drawn with red and black pens.
Additional rules that differ from binary search trees
Red-black tree The following new rules are added to the rules based on binary search trees:
- Each node is either red or black (there are only two colors, black or red)
- The root node is always black (sometimes you can ignore this rule because the root node can easily change from red to black, not necessarily from black to red)
- All leaf nodes are black (null in Java language for leaf nodes)
- The children of the red node must all be black (that is, two consecutive red nodes are not allowed on the same path)
- The path from any node to each leaf node in the subtree contains the same number of black nodes (the number of black nodes on the path from any node to its descendant leaf nodes is referred to as black heights, that is, the black heights of any node must be the same).
Example of a red-black tree
Below is an example of a red-black tree, it’s the result of sequence traversal is: 1,6,8,11,13,15,17,22,25,27, in this paper, the algorithm to the example described around it.
Red black tree operation
This paper mainly introduces the operation of red black tree insertion and deletion, red black tree is actually a special case of binary search tree, if the query class operation can be achieved by referring to binary search tree. Insert and delete operations will violate the red-black rules and destroy the balance of the tree, requiring related left or right rotation operations to maintain the balance of the tree. Restoring the property rules of red-black trees requires O(log n) or O(1) color changes and no more than 3 tree rotations. Despite the complexity of insert and delete operations, their time complexity is order (log n).
Declare the following tags to represent the node to be operated on:
- N: current node
- P: indicates the parent node of the current node
- U: brother node (uncle node) of the parent node (UL: left uncle, UR: right uncle)
- S: sibling of the current operating node (SL: left sibling, SR: right sibling)
- G: indicates the parent node of the parent node of the current operation node
insert
The method of insertion is similar to that of binary search tree, but the new nodes are marked red (first to satisfy rule 5, black height is consistent) and can be rotated later to satisfy other rules. If you add a leaf node, the leaf node in the red-black tree is null, so replace the leaf node and add two leaf nodes under that node.
Insert cases need to be handled in the following ways:
- Insert node N is the root node
- The parent P of node N is black
- The parent node P and uncle node U of node N are red
- The parent node P of node N is red, but the uncle node U is black
The following is an illustration:
1. N is the root node
Set the color to black and do nothing else
2. The parent node of N is black
N is marked red and can be inserted directly without violating the red-black rule.
3. The parent node P and uncle node U of node N are red
If N is red, and rule 4 is violated after insertion, the same path cannot have two consecutive red nodes, set P and U to black and set G to red. Then, if G is found to be the root node, G is set to black, otherwise, G is treated as N and recursively called (possibly rotated) to rearrange the structure of the tree to meet the rules of red-black trees.
4. The parent node P of node N is red, but the uncle node U is black
There are two cases:
4.1 P is red and U is black. In addition, N is the right child node of P, and P is the left child node of G, as shown in the following figure:
A left-handed operation can be understood as follows: Replace the position of P node with N node (N node becomes P node), P node becomes the left child node of N node, and the original left child node of N node becomes the right child node of P node, as shown in the figure below:
The rotated node is then treated as case 4.2.
Actually, the way to think about it, if you look at the figure above, is that G, P, N are not on the same line, they are on the same line by left-rotation and then you go down. So, if it is another case (other than 4.2), where P is the right child of G and N is the left child of P, we can do right rotation first, so that G, P and N are in a straight line, then we can do 4.2.
4.2 P is red and U is black. In addition, N is the left child node of P, and P is the left child node of G, as shown below:
In this case, a dextral and dextral operation is performed for G: G is taken as the right child node of P, and the original right child node of P becomes the left child node of G. Then, the color of P and G is switched. As shown below (to assign a red node from the left subtree to the right subtree) :
These cases are handled (sometimes recursively) to adjust the structure of the tree to meet the rules of red-black trees.
delete
Deletion is more complicated than insertion, but it can also be similar to the deletion operation of binary search tree (if the left and right nodes of the deleted node are not empty nodes (that is, they are not leaf nodes), find the forward or successor nodes of the node to be deleted to replace them for deletion). Then the tree structure can be adjusted by rotation to meet the rules of red-black tree.
If you use is replaced by the predecessor of delete node, is the predecessor of node should be removed, the lion’s share of the left subtree nodes, in addition to be sure, the former more nodes, up to a left child node (the reason is very simple, if it has the right child nodes, it isn’t the left subtree is one of the largest node but its right child nodes). Similarly, the successor node should be the smallest node in the right subtree of the deleted node, and the successor node has at most one right child node.
This article is clear on the use of forward node. During deletion, the forward node is used to replace the deleted node, so the forward node is regarded as N. If the deleted node has at most one non-empty leaf node, it is better to treat the deleted node as a replacement node N, which is easier to analyze.
After the deletion of node N, the tree structure should be adjusted in the following cases:
1. N is the root node (replaced node, so there cannot be two non-empty leaf nodes)
In this case, just delete N. Since N is a replacement node, it means that N has at most one red non-empty leaf node. If N’s children are all empty, delete them, and if there’s a red leaf, cover it with a red leaf.
2. N is the red node
We just do the same thing we did in case 1.
3. N is a black node
This kind of circumstance is more complicated, because the node N is black, remove all path after missing a black node, destroyed the rule 5, this time will need to adjust the structure of the tree to meet the rules, such as ask the parents borrow a black brothers node, this time depends on its parents have black brothers node to borrow, That leaves several more cases to deal with. Note that this process may be a recursively invoked project until node N is not the root node and ends in black.
3.1 N is the left child node, and the sibling node S of N is red
The diagram below:
At this point, set P to red, set U to black, and rotate left with the P node:
In fact, the above operation is because there is a black node missing from the path p-N1, so WE can borrow one of them, and at the same time, we can not affect the number of black nodes in the right subtree of P, but we can not finish the calculation, we need to go down.
3.2 N is the left child node, S is black, and both child nodes of S are black
In this case, the sibling S can be set to red, because if N is lost as a black node, its sibling will also lose a black to be consistent, but all paths from P will lose a black. Don’t worry, if it comes from case one, then P is red, end the recursive call and set P to black to satisfy rule 5.
If P is not red, then recursive call processing continues.
3.3 N is the left child node, S is black and one of the children of S is red
There are two cases where the red child is the left child and the red child is the right child.
If it is case 1, we adjust the red left child node to case 2, as shown in the figure below. Since it is red, the original black height is not affected:
In the figure above, the S node is right-handed and the colors of S and N3 are switched. After such processing, the red node is the right child node. Now only the right child node is red as shown in the following figure:
At this time, the left subtree of P lacks a black node due to the deletion of the N node. In this case, the left subtree should rotate with P node and set P to black to lend a black node to the left subtree. So that less right subtree (P a node (because now borrow left subtree when P is black node, and the color of the original P don’t know), so the set S the color of the node to P, but this might lead to less a black node on the right, then to set the SR to black to supplement the node S missing black. That completes the adjustment, ending the recursive call.
The diagram below:
3.4 N is the right child node, and the sibling node S of N is red
3.5 N is the right child node, S is black, and both children of S are black
3.6 N is the right child node, S is black, and one of the children of S is red
For 3.4, 3.5, 3.6 are actually the reverse of 3.1, 3.2, 3.3, not specified.
In fact, according to my personal understanding, in order to maintain the rules of the tree, there are only two complex operations needed when inserting and deleting a red-black tree:
- When you insert, you see two red nodes, you rotate them around, and you put one of the red nodes somewhere else
- When deleting, delete a black node, then borrow one from parents and brothers.
The source code
import java.util.ArrayList;
import java.util.List;
public class RedBlackTree<T extends Comparable> {
private static final boolean RED = false;
private static final boolean BLACK = true;
private Node root;
public RedBlackTree(a) {
root = null;
}
public RedBlackTree(T t) {
this.root = new Node(t, null.null.null);
}
/** * add data */
public void add(T e) {
// If the root node is empty, the root node is set to black by default
if (root == null) {
this.root = new RedBlackTree.Node(e);
} else {
// The root node is not empty
RedBlackTree.Node current = root;
RedBlackTree.Node parent = null;
int cmp = 0;
do {
// Binary search tree search method to find the appropriate node
parent = current;
cmp = e.compareTo(current.data);
if (cmp > 0) {
current = current.right;
} else{ current = current.left; }}while(current ! =null);
RedBlackTree.Node newNode = new RedBlackTree.Node(e, parent, null.null);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
// Add a new black node, which must violate the black height consistency rule of red black treefixAfterInsertion(newNode); }}/** * Fix red-black tree ** after insertion@paramX Inserted node */
private void fixAfterInsertion(Node x) {
// Consider the following situations:
// 1. X is definitely not the root node. The root node does not need to be adjusted
// The parent node of x is the root node, so you only need to set x to red, which does not violate the red-black tree rules
// 3. So the emphasis adjustment does not need to consider 1 and 2
// The parent and uncle nodes of 4. X are both red. In this case, we only need to set uncle and parent nodes of X to black, and grandfather nodes to red
// Then, set the grandfather node to x recursively
// The 5. X node is black, so it needs to be rotated
// Set the new node to red
x.color = RED;
while(x ! =null&& x ! = root && x.parent.color == RED) {// The parent of x is the left child of the grandfather of x
if (parentOf(x).isLeftChild()) {
// The uncle node of x is the right child node
Node uncle = rightOf(grandfatherOf(x));
if (colorOf(uncle) == RED) {
// Uncle and parent are both red, as in case 4 of the above comment
setColor(parentOf(x), BLACK);
setColor(uncle, BLACK);
setColor(grandfatherOf(x), RED);
x = grandfatherOf(x);
} else {
// x is the right child of the parent
if (x.isRightChild()) {
x = parentOf(x);
// The parent of x and x are not on the same "straight path". Rotate the parent of x left to make it look like a straight pathrotateLeft(x); } setColor(parentOf(x), BLACK); setColor(grandfatherOf(x), RED); rotateRight(grandfatherOf(x)); }}else { // The parent of x is the right
// The uncle node of x
Node uncle = leftOf(grandfatherOf(x));
if (colorOf(uncle) == RED) {
// Uncle and parent are both red, as in case 4 of the above comment
setColor(parentOf(x), BLACK);
setColor(uncle, BLACK);
setColor(grandfatherOf(x), RED);
x = grandfatherOf(x);
} else {
// x is the left node
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
// The parent of x and x are not on the same "straight path". Rotate the parent of x to make it look like a straight pathrotateRight(x); } setColor(parentOf(x), BLACK); setColor(grandfatherOf(x), RED); rotateLeft(grandfatherOf(x)); }}}// The root node is always black
root.color = BLACK;
}
private void rotateLeft(Node p) {
if(p ! =null) {
Node r = p.right;
Node q = r.left;
p.right = q;
if(q ! =null) {
q.parent = p;
}
r.parent = p.parent;
if (p.parent == null) {
root = r;
} else if (p == p.parent.left) {
p.parent.left = r;
} else{ p.parent.right = r; } r.left = p; p.parent = r; }}private void rotateRight(Node p) {
if(p ! =null) {
Node l = p.left;
Node q = l.right;
p.left = q;
if(q ! =null) {
q.parent = p;
}
l.parent = p.parent;
if (p.parent == null) {
root = l;
} else if (p == p.parent.left) {
p.parent.left = l;
} else{ p.parent.right = l; } l.right = p; p.parent = l; }}private Node parentOf(Node p) {
return p == null ? null : p.parent;
}
private Node grandfatherOf(Node p) {
return parentOf(parentOf(p));
}
private Node leftOf(Node p) {
return p == null ? null : p.left;
}
private Node rightOf(Node p) {
return p == null ? null : p.right;
}
private boolean colorOf(Node p) {
returnp ! =null ? p.color : BLACK;
}
private void setColor(Node p, boolean c) {
if(p ! =null) { p.color = c; }}public Node getNode(T e) {
Node p = root;
while(p ! =null) {
int cmp = e.compareTo(p.data);
if (cmp < 0) {
p = p.left;
} else if (cmp > 0) {
p = p.right;
} else {
returnp; }}return null;
}
/** * remove a node */
public void remove(T e) {
Node target = getNode(e);
if (target == null) {
return;
}
// If both children of the node to be removed exist, find its forward node to replace it
if(target.left ! =null&& target.right ! =null) {
Node node = target.left;
while(node.right ! =null) {
node = node.right;
}
// Overwrite the data on the node to be deleted
target.data = node.data;
// Operate on surrogate nodestarget = node; } Node relacement = target.left ! =null ? target.left : target.right;
// If target has a child node, it needs to be adjusted, but if target is found above, it needs to be adjusted.
// Then target has at most one left child node
if(relacement ! =null) {
relacement.parent = target.parent;
if (target.isRoot()) {
root = relacement;
} else if (target.isLeftChild()) {
target.parent.left = relacement;
} else {
target.parent.right = relacement;
}
/ / delete the target
target.left = target.right = target.parent = null;
if (colorOf(target) == BLACK) {
// A black node is removed and the red-black tree needs to be fixed to meet the black-height consistency rulefixAfterDeletion(relacement); }}else if (target.isRoot()) {
root = null;
} else {
// target has no non-empty child nodes
// Delete a black node, need to fix the red black tree to meet the black height consistent rule, not red
if (colorOf(target) == BLACK) {
fixAfterDeletion(target);
}
/ / delete the target
if (target.isLeftChild()) {
target.parent.left = null;
} else {
target.parent.right = null;
}
target.parent = null; }}public void fixAfterDeletion(Node x) {
// Continue processing until x is the root node or x is red in color
while(x ! = root && colorOf(x) == BLACK) {if (x.isLeftChild()) {
// s is a sibling of x
Node sib = rightOf(parentOf(x));
if (colorOf(sib) == RED) {
// Because the x path will be missing a black, so it needs to borrow one from its parents to help
setColor(sib, BLACK);
// If sib is red, its parent node must be black, otherwise it violates the rule that red-black trees cannot have two consecutive red nodes
setColor(parentOf(sib), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
// Both children of siB are black
if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
// Sib is set to red because there will be one less black node in the subtree of x and one less black node in the subtree of its sibling
setColor(sib, RED);
// Make x point to its parent. If x's parent is red, end the loop and set it to black. The missing black node is replaced
// If it is not red, continue to adjust
x = parentOf(x);
} else {
// Only one of siB's children is black
// Put the red child right on the right child, because there is one less black node on the x side, so we need to borrow a black node
// Finally siB side missing a black, set the red to black fill
if(colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib), BLACK); setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(x), BLACK); rotateLeft(parentOf(x)); x = root; }}else {
// If x is the right child, it is the other way around
Node sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
// Both children of siB are black
if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
// Sib is set to red because there will be one less black node in the subtree of x and one less black node in the subtree of its sibling
setColor(sib, RED);
// Make x point to its parent. If x's parent is red, end the loop and set it to black. The missing black node is replaced
// If it is not red, continue to adjust
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(x), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
// middle order traversal
public List<Node> inIterator(Node node) {
List<Node> nodes = new ArrayList<Node>();
if(node.left ! =null) {
nodes.addAll(inIterator(node.left));
}
nodes.add(node);
if(node.right ! =null) {
nodes.addAll(inIterator(node.right));
}
return nodes;
}
public List<Node> inIterator(a) {
returnroot ! =null ? inIterator(root) : new ArrayList<Node>(0);
}
private static class Node {
Object data;
Node parent;
Node left;
Node right;
boolean color = BLACK;
public Node(Object data) {
this.data = data;
}
public Node(Object data, Node parent, Node left, Node right) {
this.data = data;
this.parent = parent;
this.left = left;
this.right = right;
}
public boolean isLeftChild(a) {
return this= =this.parent.left;
}
public boolean isRightChild(a) {
return this= =this.parent.right;
}
public boolean isRoot(a) {
return this.parent == null;
}
@Override
public String toString(a) {
return data.toString();
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj.getClass() == Node.class) {
Node target = (Node) obj;
return data.equals(target.data) && left == target.left && right == target.right && parent == target.parent && color == target.color;
}
return false; }}public static void main(String[] args) {
RedBlackTree<Integer> tree = new RedBlackTree<Integer>();
/ / traverse the result should be: 1,6,8,11,13,15,17,22,25,27
Integer[] integers = {6.15.25.8.17.22.11.1.13.27};
for (Integer i :
integers) {
tree.add(i);
System.out.println(tree.inIterator());
}
for(Integer i : integers) { tree.remove(i); System.out.println(tree.inIterator()); }}}Copy the codeReferences:
Red — Black Tree – Wikipedia
Crazy Java: 16 Lessons to Break Basic Programmer Skills