TreeMap
The internal structure of TreeMap is a red black tree, and the efficiency of searching, adding and deleting is log(n); And the elements stored inside are all ordered. In order to make the elements in TreeMap orderly, a method that can compare the elements stored inside TreeMap must be provided; TreeMap provides two ways to help TreeMap compare internally stored elements;
Method 1: when creating TreeMap, pass in a Comparator in the construction method
Method 2: let the key of the element stored in TreeMap implement the Comparable interface.
Inheritance structure of TreeMap
- AbstractMap implements some basic methods in Map, reducing the workload of Map implementation classes.
- NavigableMap provides some methods to return the elements in TreeMap that are closest to a given key value.
- Serializable serialization interface, object persistence method.
- The clonable tag interface indicates that the object can be clone d.
field
// The comparator used to determine the order of elements in the TreeMap. If it is null, the CompareTo method of the stored key is called. private final Comparator<? super K> comparator; // Root root node private transient Entry<K,V> root; // Number of elements in TreeMap private transient int size = 0; // The number of times the TreeMap was modified. private transient int modCount = 0;
Construction method
//Create an empty tree
public TreeMap() {
comparator = null;
}
// Create an empty tree with a comparator, and add elements to this TreeMap will determine the order according to this comparator. If it is null, the CompareTo method of the stored key is called.
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
// According to the incoming Map m, construct a new map containing all the elements in M
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
// Construct a new map containing all the elements in m according to the incoming SortedMap m because m is the ordered map,
//Therefore, when copying elements to a new map, it is unnecessary to repeatedly confirm the order of elements. It can improve the efficiency of creating a new map
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
common method
containsValue
Overall idea: start from the leftmost node and traverse the whole red black tree by constantly searching for subsequent nodes. If the specified value is not found in traversing the whole red black tree, false will be returned.
// Determine whether the TreeMap has the same value as value
public boolean containsValue(Object value) {
// Traverse the whole tree from the leftmost element. If the value of a key value pair in the tree is equal to the value, it returns true.
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
if (valEquals(value, e.value))
return true;
return false;
}
// Returns the first key value pair in the tree, that is, the leftmost key value pair
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root; //Start with root
if (p != null)
while (p.left != null) //All the way to the left
p = p.left;
return p;
}
// Returns the successor node of the specified node
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null) //If t is null, there is no subsequent node and null is returned.
return null;
else if (t.right != null) { // If the node t has a right subtree, then the successor node of t is the leftmost element of the right subtree.
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {// If the node t has no right subtree,
// 1. If t is the left child node of the parent node, directly return the parent node
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
// 2. If t is the right child node of the parent node, it needs to go up all the time. Until ch is the left child node of the parent node.
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
// Judge whether O1 and O2 are equal
static final boolean valEquals(Object o1, Object o2) {
// The null judgment operation is added to prevent the occurrence of null pointer exceptions. O1 and O2 return true for null at the same time.
return (o1==null ? o2==null : o1.equals(o2));
}
get
Overall idea: TreeMap relies on the Comparator's compare method or the compareTo method in the key implementation Comparable interface to determine the location of elements.
TreeMap takes precedence over the Comparator's compare method. If there is no Comparator, the compareTo method of key is used to find elements.
// Get element value by key
public V get(Object key) {
Entry<K,V> p = getEntry(key);
// If p equals null, null is returned; otherwise, the element value is returned.
return (p==null ? null : p.value);
}
// Get element by key
final Entry<K,V> getEntry(Object key) {
// If the comparator is not empty, call getEntryUsingComparator, and use the comparator to determine the element position. Otherwise, the compareTo method of the key is used.
if (comparator != null)
return getEntryUsingComparator(key);
// If the key is empty, a null pointer exception is thrown
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
// Cast the key to the Comparable type. If the key k does not implement the Comparable interface, an exception will be thrown.
Comparable<? super K> k = (Comparable<? super K>) key;
// Start from root node
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)// If CMP > 0, the target key is on the left side of the current node
p = p.left;
else if (cmp > 0)// If CMP > 0, the target key is on the right side of the current node.
p = p.right;
else // If cmp=0, the current node is the node to be found
return p;
}
return null;
}
// Use comparator to find element position
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)// If CMP > 0, the target key is on the right side of the current node.
p = p.left;
else if (cmp > 0)// If CMP > 0, the target key is on the right side of the current node.
p = p.right;
else // If cmp=0, the current node is the node to be found
return p;
}
}
return null; //mei'zhao'd
}
put
The overall idea is: if the root node is empty, put the new node directly on the root node.
If the root node is not empty, call different comparison methods according to the presence or absence of comparators to find the parent node position of the inserted node. Finally, insert a new node.
// Store key value pairs in TreeMap
public V put(K key, V value) {
Entry<K,V> t = root; //Start from the root node and find the location where the key value pair is stored.
if (t == null) {
// Check whether key s can be compared.
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null); // If the root node is null, directly assign the newly created node to root
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
// If there is a comparator, the comparator is used for comparison; if there is no comparator, the compareTo method is used for comparison.
if (cpr != null) {
// Loop to find the parent node position of the checked in element
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0) // If CMP < 0, the target key is on the left side of the current node.
t = t.left;
else if (cmp > 0) // If CMP > 0, the target key is on the right side of the current node.
t = t.right;
else // If cmp=0, the key of the current node is the target key. The target key already exists in the TreeMap. You only need to update the value of the current node.
return t.setValue(value);
} while (t != null);
}
else { // Compare using the compareTo method of key
if (key == null) // Empty key cannot appear
throw new NullPointerException();
@SuppressWarnings("unchecked")
// Cast the key to the Comparable type. If the key does not implement the Comparable interface, an error will be reported
Comparable<? super K> k = (Comparable<? super K>) key;
// Loop through and search for the parent node position of the inserted element
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0) // If CMP < 0, the target key is on the left side of the current node.
t = t.left;
else if (cmp > 0) // If CMP > 0, the target key is on the right side of the current node.
t = t.right;
else // If cmp=0, the key of the current node is the target key. The target key already exists in the TreeMap. You only need to update the value of the current node.
return t.setValue(value);
} while (t != null);
}
// Create a new node based on key and value
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0) // If CMP < 0, connect the new node to the left of the parent node
parent.left = e;
else // If CMP > 0, connect the new node to the right of the parent node
parent.right = e;
// Repair the red black tree after inserting a new node
fixAfterInsertion(e);
// Number of elements + 1
size++;
// Operand + 1;
modCount++;
// If it is an insert element, it returns null; if it is a replacement element, it returns the replaced value
return null;
}
putAll
Overall idea: Based on the characteristics of ordered maps, the buildFromSorted method is provided in the TreeMap, which is used to add multiple elements from an ordered sorted map to the TreeMap. However, the TreeMap must be an empty tree.
If the TreeMap is an empty tree, call the buildFromSorted method. The buildFromSorted method is more efficient. Otherwise, call the putAll method in AbstractMap. The putAll method in AbstractMap is to call the put method repeatedly, which is inefficient.
The buildFromSorted method creates a red black tree by recursion. Each recursion will create a node in the middle of the specified range. And recursively creates the left subtree and the right subtree again.
The buildFromSorted method also colors all the elements at the bottom layer red, and other nodes are black. The purpose of this is to prevent the elements at the last layer from being full, resulting in black height imbalance.
// Add all the elements in the parameter map to this TreeMap
public void putAll(Map<? extends K, ? extends V> map) {
// Number of elements in parameter map
int mapSize = map.size();
// buildFromSorted is a method specially designed for adding elements from SortedMap to this TreeMap. It is more efficient than the putAll method in AbstractMap.
// This TreeMap must be an empty tree, and the parameter map must be a subclass of SortedMap before the buildFromSorted method can be called. Otherwise, the putAll method in AbstractMap is called
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator<?> c = ((SortedMap<?,?>)map).comparator();
// If there is a Comparator in the parameter map, the comparators in this TreeMap must be the same as those in the parameter map, or both are empty. Otherwise, the add operation cannot be performed.
if (c == comparator || (c != null && c.equals(comparator))) {
// Operands++
++modCount;
try {
// Parameters: mapSize map size, map. Entryset() Iterator() iterator of map.
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
// Using the putAll method in AbstractMap means calling the put method repeatedly
super.putAll(map);
}
// The method of adding elements to this collection from SortedMap.
private void buildFromSorted(int size, Iterator<?> it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
// Modify the number of elements of this TreeMap.
this.size = size;
// The method of constructing the red black tree will be described later.
root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
it, str, defaultVal);
}
// It is calculated that the red black tree composed of sz elements has several layers, and the last layer of the created red black tree is all dyed red.
private static int computeRedLevel(int sz) {
int level = 0;
for (int m = sz - 1; m >= 0; m = m / 2 - 1)
level++;
return level;
}
/**
* int level: The currently constructed node is the layer of the red black tree.
* int lo, int hi A subtree is constructed from the position of the subscript lo~hi of the map.
* int redLevel The layer where the red node is located.
* Itertor<?> it map Iterator for.
* java.io.ObjectInputStream str Object output stream.
* V defaultVal Default:
* Construction Strategy:
* It takes the middle element in the iterator as the root node and returns it. And recursively creates a left subtree and a right subtree.
*/
private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
int redLevel,
Iterator<?> it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
// Returns null if the high subscript is greater than the low subscript.
if (hi < lo) return null
// Calculates the subscript of the intermediate element. Unsigned right shift, equivalent to dividing by 2;
int mid = (lo + hi) >>> 1
Entry<K,V> left = null;
// Recursively create left subtree
if (lo < mid)
left = buildFromSorted(level+1, lo, mid - 1, redLevel,
it, str, defaultVal
// extract key and/or value from iterator or stream
K key;
V value;
// If the iterator is not empty, the iterator is used to obtain the key value pair; if the iterator is empty, the object output stream is used to obtain the key value pair
if (it != null) {
// Judge whether the parameter defaultVal is empty. If it is empty, use the value of the key value pair in the iterator. If it is not empty, use defaultVal as the value of the newly created node.
if (defaultVal==null) {
// The iterator gets the key value pair object
Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
key = (K)entry.getKey();
value = (V)entry.getValue();
} else {
key = (K)it.next();
// Use the default value as the value of the new node
value = defaultVal;
}
} else { // use stream
// Gets an object from the object input stream.
key = (K) str.readObject();
value = (defaultVal != null ? defaultVal : (V) str.readObject());
}
// Create a node.
Entry<K,V> middle = new Entry<>(key, value, null);
// color nodes in non-full bottommost level red
// Dye the bottom node red to keep the black height.
if (level == redLevel)
middle.color = RED;
// Connect left subtree
if (left != null) {
middle.left = left;
left.parent = middle;
// Recursively create right subtree
if (mid < hi) {
Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
it, str, defaultVal);
middle.right = right;
right.parent = middle;
// Return the nodes created recursively in this layer.
return middle;
}
remove
Overall idea: first call the getEntry method to determine whether the key value pair exists. If there is, the deleteEntry method is called again to delete. If the deleted node is not a leaf node, the successor node of the deleted node is found, the keys and values of the deleted node and the deleted node are exchanged, and the successor node is deleted instead of the deleted node.
//Remove the specified node and return the value of the removed node
public V remove(Object key) {
// First, determine whether the key exists in the TreeMap. If it does not exist, return null directly
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
// If it exists, delete the specified node directly and return the element value of the deleted node
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
//If the deleted node is not a leaf node, it looks for its successor node and exchanges the keys and values of the successor node and the deleted node.
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
// After the p node is deleted, replacement will replace the position of the p node. Replacement is the left or right child node of p
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
// If the replacement is not null, connect the replacement to the location of P. if the replacement is null, directly set the references connected to p to null.
if (replacement != null) {
// Modify the parent of the replacement
replacement.parent = p.parent;
// If the parent of p is null, it means that p is the root node, and directly assign replacement to root.
if (p.parent == null)
root = replacement;
// Modify the reference that originally points to p to point to replacement
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// Set all reference variables inside p to null.
p.left = p.right = p.parent = null;
// Red nodes do not need to be repaired. If they are black nodes, they need to be repaired
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // If p is the only element in TreeMap, simply set root=null.
root = null;
} else { // If p is a leaf node, repair it first and then delete the leaf node
// If p is black, the red black tree needs to be repaired.
if (p.color == BLACK)
fixAfterDeletion(p);
// All references to p
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
rotateLeft
Left rotation, right rotation and color change are the three basic operations for red black trees to maintain their properties.
In my last blog, I have sorted out the processing methods of red black tree insertion and deletion in different cases, and the processing methods are similar to those of the official source code. But the official source code is more concise and easy to understand; So let's learn again.
/**
* p p
* | |
* n y
* / \ ---> / \
* x y n ry
* / \ / \
* ly ry x ly
* Left hand operation
* 1. Connect the left child node ly of y to the right child node of n
* 2. Modify the parent node of ly to point to n
* 3. Connect n to the left child node position of y
* 4. Modify the parent of n to specify y
* 5. Modify the parent of y to point to the parent node of n
* 6. Modify p to point to n and point to y
*/
//Left-handed
private void rotateLeft(Entry<K,V> p) {
// The null pointer is determined to avoid null pointer.
if (p != null) {
// When r is the right child node of p, r will become the parent node of p. p will become the left child node of r.
Entry<K,V> r = p.right;
// Connect the left child node of r to the right child node of p.
p.right = r.left;
// At the same time, the parent node of the left node of r should be modified.
if (r.left != null)
r.left.parent = p;
// Modify the parent of r to the parent of p
r.parent = p.parent;
// If the parent of p is null, directly change the root to r.
if (p.parent == null)
root = r;
else if (p.parent.left == p) // If the parent of P is not null, modify the pointer of the parent node of the original p to point to p to point to r.
p.parent.left = r;
else
p.parent.right = r;
r.left = p; // p becomes the left child node of r
p.parent = r;
}
}
Rotatereight
/**
* p p
* | |
* n x
* / \ / \
* x y ---> lx n
* / \ / \
* lx rx rx y
*
*
* Right hand operation
* 1. Connect the right child node rx of x to the left child node of n
* 2. Modify the parent node of rx to point to n
* 3. Connect n to the right child node position of x
* 4. Modify the parent of n to specify x
* 5. Modify the parent of x to point to the parent node of n
* 6. Modify p to point to n and point to x
*/
private void rotateRight(Entry<K,V> p) {
// Judge null to avoid null pointer exception
if (p != null) {
// After L is the left child node of p, l will become the parent node of p and p will become the right child node of L.
Entry<K,V> l = p.left;
// Connect the right child node of l to the left child node of p.
p.left = l.right;
// At the same time, modify the parent pointer of the right child node of l.
if (l.right != null)
l.right.parent = p;
// Modify the parent of l to point to the parent of p.
l.parent = p.parent;
// If the parent of p is null, assign l to root directly
if (p.parent == null)
root = l;
else if (p.parent.right == p) // If the parent of P is not null, modify the pointer of the parent node of the original p to point to p to point to r.
p.parent.right = l;
else p.parent.left = l;
l.right = p; // p becomes the right child node of l.
p.parent = l;
}
}
fixAfterInsertion
Fix red black tree imbalance caused by node operation.
There are several problems caused by inserting nodes.
- If the root is empty, direct the root to the new node.
- The parent node is black, directly inserted, and has no effect.
- The key value already exists. Update the value of the key value pair.
- If the parent node is red, because the inserted node is red, red and red cannot be connected, it needs to be processed
4.1. Uncle node is red
Dye the father node and uncle node black. Grandpa's nodes are dyed red.
4.2. Uncle node is black or empty
4.2.1. The parent node is on the left side of the grandfather node, and the child node is on the left side of the parent node (LL double red)
Dye the father node black. Grandpa's nodes are dyed red. Right turn to Grandpa's node.
4.2.2. The parent node is on the left side of the grandfather node, and the child node is on the right side of the parent node (LR double red)
Turn left on the parent node and then turn – > 4.2.1
4.2.3. The parent node is on the right side of the grandfather node, and the child node is on the right side of the parent node (RR double red)
Dye the father node black. Grandpa's nodes are dyed red. It's left-handed to Grandpa's node.
4.2.4. The parent node is on the right side of the grandfather node, and the child node is on the left side of the parent node (RL double red)
Right turn the parent node and then turn – > 4.2.3
It can be seen that the first three cases can be solved at the node insertion stage. Only case 4 needs to be repaired
private void fixAfterInsertion(Entry<K,V> x) {
// The inserted nodes are all red by default.
x.color = RED;
// If the parent node of x is red, it needs to be repaired. If the repair overflows to the root node root, it needs to exit because it cannot continue to repair upwards.
while (x != null && x != root && x.parent.color == RED) {
// The parent node is the left child node of the grandfather node
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
// y is the uncle node of the inserted node.
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
// Uncle node is red 4.1
if (colorOf(y) == RED) {
// Dye the father node black
setColor(parentOf(x), BLACK);
// Uncle node dyed black
setColor(y, BLACK);
// Grandfather node dyed red
setColor(parentOf(parentOf(x)), RED);
// And then the grandfather node is treated as the inserted node to continue to repair upward.
x = parentOf(parentOf(x));
} else {
//4.2.2 the parent node is on the left side of the grandfather node, and the inserted node is on the right side of the parent node
if (x == rightOf(parentOf(x))) {
// Here, the parent node needs to be left rotated, but after left rotation, the original parent node becomes the left child node of the current node. So here, the parent node of the current node x is directly assigned to x, and then x is left rotated, and X is regarded as the inserted node. At this time, the situation changes to 4.2.1
x = parentOf(x);
rotateLeft(x);
}
// 4.2.1. The parent node is on the left side of the grandfather node, and the inserted node is on the left side of the parent node
// Dye the parent node black.
setColor(parentOf(x), BLACK);
// The grandfather node is dyed red
setColor(parentOf(parentOf(x)), RED);
// Turn right to the grandfather node
rotateRight(parentOf(parentOf(x)));
}
} else { // The parent node is the right child node of the grandfather node, and the operation is symmetrical with the above operation.
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
fixAfterDeletion
Fix the red black tree imbalance caused by deleting nodes.
The situation caused by deleting a node is as follows.
- The deleted node is red
This situation does not affect the nature of the red black tree and can be deleted directly - The deleted node is black
2.1. The sibling node is black, and the sibling node has red child nodes
2.1.1. The left child node of the sibling node is red
At this time, the right subtree of the parent node is empty, and the left subtree is ll (the brother node is on the left of the parent node, and the left child node of the brother node is on the left of the brother node),
Adjustment method: dye the color of the brother node to the color of the original parent node, then dye the left child node and the parent node of the brother node to black, and then rotate the parent node to the right.
In this way, the black height of this subtree is equal to the black height before deletion. Compared with the subtree before deletion, this subtree has one less red node.
2.1.2. The right child node of the sibling node is red
At this time, the right subtree of the parent node is empty, and the left subtree is lR (left right)
Carry out left rotation on the sibling node and exchange the colors of the sibling node and the right child node of the sibling node, which can be converted to the case of 2.1.1
2.2. The sibling node is black, and the sibling node has no child node
2.2.1. Parent node is red
Dye the parent node black and the brother node red
2.2.2. Parent node is black
In this case, the deleted node, the parent node, and the brother node are all black. After the deleted node is deleted, the black height cannot be maintained within the range of the parent node as the root node,
It is necessary to expand the scope of adjustment.
The specific operations are as follows: dye the sibling node red (subtract one from the black height of the subtree with the parent node as the root node), and then use the parent node as the deletion node to repair the red black tree.
2.3. The sibling node is red (the parent node must be black (property 4), and there must be black child nodes, otherwise the black height is unbalanced (property 5))
The father node is dyed red, the brother node is dyed black, and then the right rotation of the father node changes to other situations.
private void fixAfterDeletion(Entry<K,V> x) {
// If the deleted node is black, it needs to be repaired because the impact of black is high.
while (x != root && colorOf(x) == BLACK) {
// The deleted node x is the left child node of the parent node
if (x == leftOf(parentOf(x))) {
// sib is the brother node of the deleted node.
Entry<K,V> sib = rightOf(parentOf(x));
// 2.3. Brother node is red
if (colorOf(sib) == RED) {
// Dye the sibling nodes black.
setColor(sib, BLACK);
// The father node is dyed red
setColor(parentOf(x), RED);
// To the left of the father node
rotateLeft(parentOf(x));
// Update the sib of the sibling node and continue to repair it in other cases.
sib = rightOf(parentOf(x));
}
// 2.2. Brother nodes are black, and brother nodes have no child nodes. Empty nodes are also black nodes.
// 2.2.1 and 2.2.2 can be combined.
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
// Dye brother nodes red
setColor(sib, RED);
// Assign the parent node to x and continue to repair the red black tree
x = parentOf(x);
} else {
// 2.1.2. The sibling node is black, and the right child node of the sibling node is red
if (colorOf(rightOf(sib)) == BLACK) {
// Dye the left child node of the sibling node black.
setColor(leftOf(sib), BLACK);
// Sibling nodes are stained red.
setColor(sib, RED);
// This pair of sibling nodes is dextral.
rotateRight(sib);
// Update the sib of the sibling node, and the situation changes to 2.1.1
sib = rightOf(parentOf(x));
}
// 2.1.1. The sibling node is black, and the left child node of the sibling node is red
//Dye the color of the sibling node as the color of the parent node.
setColor(sib, colorOf(parentOf(x)));
// The father's node is dyed black.
setColor(parentOf(x), BLACK);
// Dye the sibling nodes black.
setColor(rightOf(sib), BLACK);
// Rotate left to parent node
rotateLeft(parentOf(x));
// End the loop.
x = root;
}
} else { // As above, it is symmetrical.
Entry<K,V> 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;
}
}
}
// Make sure the root node is black
setColor(x, BLACK);
}