Introduction to the
Red-black trees are AVL (self-balanced binary search tree, named after its inventors Adelson-Velskii and Landis) and have the following properties:
- The color of each node is red or black
- The root node is black
- If a node is red, its children must be black
- Each path from a node to a null reference must contain the same number of black nodes
Instructions for
- Sinistral: The process of making a node the left child of one’s right child
- Dextral: The process of making a node the right child of one’s left child
insert
When a new element is inserted, its color must be red; if it is black, it will violate condition 4. When inserting a new node, if its parent node is black, the insertion is complete. If the parent node is red, condition 3 is violated, and color changes and tree rotation are required to make the tree satisfy all four conditions.
We agree that X is the newly inserted node, P is its parent node, U is its uncle node (the sibling of the parent node), and G is its grandfather node (the parent node). When U is null, its color is black. Let’s discuss the following cases:
- When U is black (or null), X and P are red, G is black, and X is the left son. At this point, we need to perform a single rotation between P and G (i.e. right rotation of G node), and set the root node of the new tree to black, in order to prevent the original great-grandparent node from being red, the process is as follows:
Its mirror image operates similarly, except that it rotates to the left of G, as follows:
- When U is black (or null), X and P are red, G is black, and X is the right son. Two rotations are required to adjust the tree structure, first left-handed for P, which becomes case 1, and then right-handed for G, as follows:
Its mirror image rotates first to the right of P and then to the left of G as follows:
- When U node is red, only U and P nodes need to be set to black and G node to red, because condition 4 is violated after U and P are set to black, and G needs to be set to red to correct. If G happens to be the root node, condition 2 is violated and G needs to be set to black to correct it. The process is as follows:
delete
In fact, deletion of red-black trees can eventually be transformed into deletion of leaf nodes (without child nodes), which can be discussed in the following situations:
- If you need to be deleted node has two children, according to the nature of the binary search tree, we need to find its subsequent nodes (the biggest node in the left subtree or right subtree is the youngest of nodes), with a subsequent node value to replace the value of the deleted node, and then remove the subsequent node, if subsequent nodes have children, it can only have one child the nature of the tree (BST), So this becomes case 2.
- If the deleted node has only one child, and because of the nature of red-black trees, there is only one possibility, the deleted node is black, and its child node is red and has no child nodes, we can replace the value of the deleted node with the value of the child node, and then delete the child node.
- The deleted node is a leaf node.
Next, we discuss in need of repair, as long as when actual deleted node is black, will destroy the properties of 4, we only need to repair of a tree, we can be divided into 4 kinds of circumstances (do not include the mirror) to discuss, we agreed to be deleted node for X, its parent for P, brother nodes for B, brother node’s left child as the BL, The right child is BR:
- If B is red (there is no doubt that P, BL and BR are definitely black), we dye P red and B black, and left-rotate P so that it satisfies case 2, the process is as follows:
- If B is black and both BL/BR are black (or both are null), then we can rebalance by simply changing the color of B to red and P to black as follows (X will be deleted, so the tree is fixed at this point) :
- If B is black and BL is red, we can dye B red, dye BL black, and rotate B right to satisfy case 4, the process is as follows:
- If B is black and BR is red, we can dye P and BR black, B red, and rotate P left to balance as follows:
implementation
Implemented in Java, there are corresponding comments in the code, so the code is not analyzed separately.
/ * * *@author rookie-tx
*/
public class RedBlackTree<E extends Comparable<E>> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private TreeNode<E> root;
public RedBlackTree(a) {}public boolean contains(E element) {
TreeNode<E> temp = root;
while(temp ! =null) {
int compareResult = temp.element.compareTo(element);
if (compareResult > 0) {
temp = temp.left;
} else if (compareResult < 0) {
temp = temp.right;
} else {
return true; }}return false;
}
/** * rotate left ** /
private void rotateLeft(TreeNode<E> node) {
if (node == null) {
return;
}
// Make the left subtree of the right subtree the right subtree of the current node
TreeNode<E> r = node.right;
node.right = r.left;
if(r.left ! =null) {
r.left.parent = node;
}
// The left subtree of the right subtree becomes the current node
TreeNode<E> p = node.parent;
r.left = node;
node.parent = r;
r.parent = p;
if (p == null) {
root = r;
} else if (node == p.left) {
p.left = r;
} else{ p.right = r; }}/** ** right rotation ** /
private void rotateRight(TreeNode<E> node) {
if (node == null) {
return;
}
TreeNode<E> l = node.left;
node.left = l.right;
if(l.right ! =null) {
l.right.parent = node;
}
TreeNode<E> p = node.parent;
l.right = node;
l.parent = p;
node.parent = l;
if (p == null) {
root = l;
} else if (p.left == node){
p.left = l;
} else{ p.right = l; }}public boolean add(E element) {
if (element == null) {
throw new NullPointerException();
}
TreeNode<E> newNode = new TreeNode<>(element, RED);
return add(newNode);
}
private boolean add(TreeNode<E> newNode) {
if (root == null) {
root = newNode;
root.color = BLACK;
} else {
TreeNode<E> parent = root;
while (true) {
int compareResult = newNode.element.compareTo(parent.element);
if (compareResult > 0) {
if(parent.right ! =null) {
parent = parent.right;
} else {
parent.right = newNode;
break; }}else if (compareResult < 0) {
if(parent.left ! =null) {
parent = parent.left;
} else {
parent.left = newNode;
break; }}else {
return false;
}
}
newNode.parent = parent;
// If the parent node is red, it needs to be balanced
if(parent.color == RED) { balanceInsertion(newNode); }}return true;
}
/** * Fixed insert, need to rebalance only if the parent node is red * case 1, uncle node is also red * case 2, is the left child of the parent node, uncle node is black or has no uncle node ** /
private void balanceInsertion(TreeNode<E> x) {
// The parent, grandfather, and uncle nodes of newNode
TreeNode<E> p, g, u;
while(x ! =null&& x ! = root && x.parent.color == RED) { p = x.parent; g = p.parent;if(g ! =null && p == g.left) {
u = g.right;
if (u == null || u.color == BLACK) {
// CASE 3
if (x == p.right) {
x = p;
rotateLeft(x);
p = x.parent;
}
//CASE 2
p.color = BLACK;
g.color = RED;
rotateRight(g);
} else {
// CASE 1u.color = BLACK; p.color = BLACK; g.color = RED; x = g; }}/ / the mirror
else if(g ! =null && p == g.right) {
u = g.left;
if (u == null || u.color == BLACK) {
// CASE 3
if (x == p.left) {
x = p;
rotateRight(x);
p = x.parent;
}
// CASE 2
p.color = BLACK;
g.color = RED;
rotateLeft(g);
} else {
// CASE 1u.color = BLACK; p.color = BLACK; g.color = RED; x = g; }}}// In CASE 1, root needs to be dyed red
root.color = BLACK;
}
public boolean delete(E element) {
TreeNode<E> currentNode = root;
while(currentNode ! =null) {
int compareResult = currentNode.element.compareTo(element);
if (compareResult > 0) {
currentNode = currentNode.left;
} else if (compareResult < 0) {
currentNode = currentNode.right;
} else {
if(currentNode.left ! =null&& currentNode.right ! =null) {
TreeNode<E> successor = currentNode.right;
while(successor.left ! =null) {
successor = successor.left;
}
currentNode.element = successor.element;
currentNode = successor;
}
if(currentNode.left ! =null) {
currentNode.element = currentNode.left.element;
currentNode = currentNode.left;
} else if(currentNode.right ! =null) {
currentNode.element = currentNode.right.element;
currentNode = currentNode.right;
}
// Only the root node
if (currentNode.parent == null) {
root = null;
return true;
}
if (currentNode.color == BLACK) {
balanceDeletion(currentNode);
}
if (currentNode == currentNode.parent.left) {
currentNode.parent.left = null;
} else {
currentNode.parent.right = null;
}
currentNode.parent = null;
return true; }}return true;
}
/** * 修复 delete * case 1, sibling node is red * case 2, sibling node is black, sibling node's child is black * case 3, sibling node's left child is red, right child is black * case 4, sibling node's left child is black, The right child of the sibling node is red and the left child is any color * */
private void balanceDeletion(TreeNode<E> x) {
TreeNode<E> p, b;
while(x ! = root && x.color == BLACK) { p = x.parent;if (x == p.left) {
b = p.right;
// CASE 1
if(b ! =null && b.color == RED) {
b.color = BLACK;
p.color = RED;
rotateLeft(p);
b = p.right;
}
// CASE 2
if(b ! =null && (b.left == null || b.left.color == BLACK) &&
(b.right == null || b.right.color == BLACK)) {
b.color = RED;
x = p;
} else {
// CASE 3
if(b ! =null&& b.left ! =null && b.left.color == RED) {
b.color = RED;
b.left.color = BLACK;
rotateRight(b);
b = p.right;
}
// CASE 4
p.color = BLACK;
if(b ! =null) {
b.color = RED;
if(b.right ! =null) { b.right.color = BLACK; } } rotateLeft(p); x = root; }}else {
b = p.left;
// CASE 1
if(b ! =null && b.color == RED) {
b.color = BLACK;
p.color = RED;
rotateRight(p);
b = p.left;
}
// CASE 2
if(b ! =null && (b.left == null || b.left.color == BLACK) &&
(b.right == null || b.right.color == BLACK)) {
b.color = RED;
x = p;
} else {
// CASE 3
if(b ! =null&& b.right ! =null && b.right.color == RED) {
b.color = RED;
b.right.color = BLACK;
rotateLeft(b);
b = p.left;
}
// CASE 4
p.color = BLACK;
if(b ! =null) {
b.color = RED;
if(b.left ! =null) { b.left.color = BLACK; } } rotateRight(p); x = root; }}}if(x ! =null) { x.color = BLACK; }}static class TreeNode<E extends Comparable<E>> {
E element;
TreeNode<E> left;
TreeNode<E> right;
TreeNode<E> parent;
boolean color;
TreeNode(E element, boolean color) {
this.element = element;
this.color = color; }}}Copy the codeThe code is crudely written… It is recommended that you look at the implementation of TreeMap in the JDK.