“This article has participated in the call for good writing activities, click to view: the back end, the big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!” Last article introduced the red black tree insert operation, this article to introduce you to the red black tree delete operation.
Red black tree deletes nodes
In fact, the deletion of nodes in red-black trees can be divided into two steps:
- Delete the node first (this step is the same as normal binary tree deletion)
- And then adjust
1. Delete the node
To delete this node, we need to find this node first. Finding the node is ordinary binary search, and the specific code is as follows
private RBNode getNode(K key){
RBNode node = this.root;
while(node ! =null) {int cmp = key.compareTo((K) node.key);
if(cmp < 0) {// in the left subtree
node = node.left;
}else if(cmp >0) {/ / right subtree
node = node.right;
}else{
returnnode; }}return null;
}
Copy the codeWhen sorting out the deletion operations of red-black tree nodes, we need to first understand the equivalence relationship between red-black tree deletion and 2-3-4 tree deletion, so that it will be easier to understand the core theory: the essence of red-black tree deletion is to delete the leaf nodes of 2-3-4 trees
Case 2: the nodes that are not case 1 will be deleted. According to the deletion rules we introduced earlier, the corresponding precursor and successor nodes will be found, so the final deletion is still the leaf node
The code to delete the node first is:
/** * Delete node *@param key
* @return* /
public V remove(K key){
// Find this node first
RBNode node = getNode(key);
if(node == null) {return null;
}
// The value is saved and deleted
V oldValue = (V) node.value;
deleteNode(node);
return oldValue;
}
/** ** drop node * 3 cases * 1. Drop leaf node * 2. If the deleted node has a child node, use the child node to replace * 3. If the deleted node has two child nodes to the right, it is necessary to find a precursor node or a successor node to replace * when * can be converted to 1 or 2@param node
*/
private void deleteNode(RBNode node){
// 3. Node has two child nodes
if(node.left ! =null&& node.right ! =null) {// Find the successor of the node to be deleted
RBNode successor = successor(node);
// Then overwrite the information about the node to be deleted with the information about the successor node
node.key = successor.key;
node.value = successor.value;
// Then the node we want to delete becomes the successor node
node = successor;
}
// 2. Delete the case where there is a child nodeRBNode replacement = node.left ! =null ? node.left : node.right;
if(replacement ! =null) {// The surrogate's parent pointer points to the parent node of the original node
replacement.parent = node.parent;
if(node.parent == null) {// Node is the root node
root = replacement;
}else if(node == node.parent.left){
// Bidirectional binding
node.parent.left = replacement;
}else{
node.parent.right = replacement;
}
// Set the left and right child Pointers and parent Pointers to null nodes for GC
node.left = node.right = node.parent = null;
// Adjust the balance after the replacement
if(node.color == BLACK){
// fixAfterRemove(replacement)}}else if(node.parent == null) {// The root node is to be deleted
root = null;
}else{
// 1. The node is a leaf node replacement is null
/ / to adjust first
if(node.color == BLACK){
// fixAfterRemove(node)
}
/ / delete again
if(node.parent ! =null) {if(node == node.parent.left){
node.parent.left = null;
}else{
node.parent.right = null;
}
node = null; }}}Copy the codeThen you need to adjust the balance of the red-black tree.
2. Balance adjustment after deletion
Modifying operations for deleting a node:
1. Case 1: If it can be handled by itself, the corresponding leaf nodes are 3 and 4 nodes
2. Situation two: they can’t manage by themselves, so they need to borrow from their brother, but the brother won’t borrow from their father. The father will come down, and then the brother will find someone to take the place of his father
This is the case where siblings are 3 or 4 nodes
Find sibling nodes
Perform the following adjustment first, color first, then left rotation
Borrow from brother nodes
3. Situation 3: Borrow money from your brother, but your brother doesn’t have it.
The sibling node is 2 nodes and the parent node of the current node is a red node
Sibling nodes are two nodes, and the parent node of the current node is a black node
After analyzing the deleted 3 cases, we can remove the adjustment code
/** * 2-3-4 tree deletion operations: * 1. Situation two: they can't handle it by themselves, so they need to borrow from their brother, but the brother won't borrow from their father. The father will come down, and then the brother will find someone to take the place of his father. Situation three: borrow from brother, brother also have no *@param x
*/
private void fixAfterRemove(RBNode x){
// Case 2, 3
while(x ! = root && colorOf(x) == BLACK){// This situation needs to be adjusted
// x is the case of the left child
if(x == leftOf(parentOf(x))){
// find sibling nodes
RBNode rNode = rightOf(parentOf(x));
// Check whether the sibling node is a true sibling
if(colorOf(rNode) == RED){ // The 3-nodes of a 2-3-4 tree switch colors and then rotate left once
setColor(rNode,BLACK);
setColor(parentOf(x),RED);
leftRotate(parentOf(x)); // Turn left once
rNode = rightOf(parentOf(x)); // Find the true sibling node
}
// Situation 3: Can I borrow it from my brother
if(colorOf(leftOf(rNode)) == BLACK && colorOf(rightOf(rNode)) == BLACK){
// The situation is complicated
setColor(rNode,RED);
x=parentOf(x); // Recurse up
}else{
// Situation 2 Ask a brother for help
// Sibling nodes are either 3 or 4 nodes
if(colorOf(rightOf(rNode)) == BLACK){
// If the right child is empty, the left child is definitely not empty
// Sibling nodes are rotated left and right first
setColor(rNode,RED);
setColor(leftOf(rNode),BLACK);
rightRotate(rNode);
// Readjust the location of the uncle node
rNode = rightOf(parentOf(x));
}
// Whether the color changing sibling nodes are 3 nodes or 4 nodes are rotated once
setColor(rNode, colorOf(parentOf(x)));
setColor(parentOf(x),BLACK);
setColor(rightOf(rNode),BLACK);
/ / left
leftRotate(parentOf(x));
x = root; // End the loop recursion for case 3}}else{
// find sibling nodes
RBNode rNode = leftOf(parentOf(x));
// Check whether the sibling node is a true sibling
if(colorOf(rNode) == RED){ // The 3-nodes of a 2-3-4 tree switch colors and then rotate left once
setColor(rNode,BLACK);
setColor(parentOf(x),RED);
rightRotate(parentOf(x)); // Turn left once
rNode = leftOf(parentOf(x)); // Find the true sibling node
}
// Situation 3: Can I borrow it from my brother
if(colorOf(rightOf(rNode)) == BLACK && colorOf(leftOf(rNode)) == BLACK){
// The situation is complicated
setColor(rNode,RED);
x=parentOf(x); // Recurse up
}else{
// Situation 2 Ask a brother for help
// Sibling nodes are either 3 or 4 nodes
if(colorOf(leftOf(rNode)) == BLACK){
// If the right child is empty, the left child is definitely not empty
// Sibling nodes are rotated left and right first
setColor(rNode,RED);
setColor(leftOf(rNode),BLACK);
leftRotate(rNode);
// Readjust the location of the uncle node
rNode = leftOf(parentOf(x));
}
// Whether the color changing sibling nodes are 3 nodes or 4 nodes are rotated once
setColor(rNode, colorOf(parentOf(x)));
setColor(parentOf(x),BLACK);
setColor(leftOf(rNode),BLACK);
/ / left
rightRotate(parentOf(x));
x = root; // End the loop recursion for case 3}}}// Case 1: The replacement nodes are red, directly dyed black in case 3 to compensate for the black nodes removed, so that the red-black tree is still balanced
setColor(x,BLACK);
}
Copy the code~ well, here, I believe we should be more clear about the various operations of red black tree, if you are helpful, welcome to like attention and collection oh!! V_V