TreeMap is an implementation of the Map interface that is based on a red-black tree. TreeMap, however, does not directly implement the Map interface. Depending on which constructor is used, TreeMap sorts based on the natural order of its keys or the Comparator provided when creating the map. TreeMap’s internal operations on elements are O(logn). Although TreeMap is not superior in accessing elements, its internal elements are sorted, and it provides desirable results when it is necessary to find elements and output them sequentially.
An overview,
TreeMap provides a guaranteed log(n) time cost for the following cases:
containsKey
get
put
remove
The algorithm is an adaptation of the algorithm in Cormen, Leiserson, and Rivest’s “Introduction to the Algorithm”.
The TreeMap implementation is not synchronized and must be synchronized externally if multiple threads are accessing a TreeMap at the same time and if at least one thread has structurally modified the map. (A structural change is any operation that adds or removes one or more mappings; Merely changing the value associated with a key that the instance already contains is not a structural change. This is usually done by synchronizing objects that naturally encapsulate mappings.
If there is no such object, should use the Collections. “packaging” map synchronizedSortedMap method. It is best to do this at creation time to prevent accidental unsynchronized access to the map:
SortedMap m = Collections.synchronizedSortedMap(newTreeMap(...) );Copy the codeAll iterators returned by collection view methods of this class are fail-fast; If the iterator created, in any way modify the mapping in the structure, in addition to the iterator own the remove method, will throw ConcurrentModificationException iterator. Thus, in the face of concurrent modification, iterators fail quickly and cleanly, rather than risk arbitrary, uncertain behavior at some indeterminate time in the future.
Note that the fail-fast behavior of iterators cannot be guaranteed because, in general, it is impossible to make any hard guarantees in the case of asynchronous concurrent modifications. Fail – fast iterator to best throw ConcurrentModificationException. Therefore, it would be a mistake to write a program that relies on the correctness of this exception: the fail-fast behavior of an iterator should only be used to detect bugs.
All map.entry pairs returned by methods in this class and their views represent snapshots at the time the mapping was generated. They do not support the entry.setValue method (though note that you can use PUT to change the mapping in the associated map).
This class is a member of the Java Collections framework.
Second, inheritance structure
public class TreeMap<K.V>
extends AbstractMap<K.V>
implements NavigableMap<K.V>, Cloneable.java.io.Serializable
Copy the codeTreeMap also inherits AbstractMap abstract classes, which are the backbone implementation of the Map interface. NavigableMap, Cloneable and Serializable interfaces are also implemented.
NavigableMap interface:
public interface NavigableMap<K.V> extends SortedMap<K.V>
Copy the codeYou can see that the NavigableMap interface actually inherits the SortedMap interface:
public interface SortedMap<K.V> extends Map<K.V>
Copy the codeFinally, the SortedMap interface inherits the Map interface.
NavigableMap interface, by its name, means navigation. SortedMap, which extends the navigation method, returns the closest match for a given search target. (such as lowerEntry, floorEntry, ceilingEntry, higherEntry etc.)
The SortedMap interface is pretty straightforward, a Map that provides the overall ordering of its keys for sorting.
Implement Cloneable and Serializable interfaces, corresponding to clone and serialization operations, respectively.
Third, detailed design
AbstractMap In the previous article “How does AbstractMap exist as a backbone implementation of the Map interface?” Has carried out a detailed analysis, the following is not specific analysis.
3.1 SortedMap
SortedMap A Map that provides the overall ordering of its keys for sorting. Next look at what interface methods are provided for the implementer to implement.
Sortedmaps are sorted according to the comparable natural ordering of their keys, or by the comparators that are usually provided when a SortedMap is created. This order is reflected when traversing the collection view of the sorted map (returned by the entrySet, keySet, and VALUES methods).
The code below contains comments that illustrate the purpose of these methods.
public interface SortedMap<K.V> extends Map<K.V> {
/** * returns the comparator used to sort the keys in this map; * Returns NULL if this map uses a comparable natural ordering of its keys. * /
Comparator<? super K> comparator();
/** * Returns a partial view of the map with keys ranging from fromKey (inclusive) to toKey (not included) * (null mapping if fromKey and toKey are equal). * Changes in the returned map will be reflected in that map and vice versa. * The returned map supports all optional map operations supported by the map. * * When you try to insert a key outside its scope, the returned map will throw IllegalArgumentException. * /
SortedMap<K,V> subMap(K fromKey, K toKey);
/** * Returns a partial view of this map with keys strictly smaller than toKey (not included). * Changes in the returned map will be reflected in that map and vice versa. * The returned map supports all optional map operations supported by the map. * * When you try to insert a key outside its scope, the returned map will throw IllegalArgumentException. * /
SortedMap<K,V> headMap(K toKey);
/** * Returns a partial view of this map with a key greater than or equal to fromKey (included). * Changes in the returned map will be reflected in that map and vice versa. * The returned map supports all optional map operations supported by the map. * * When you try to insert a key outside its scope, the returned map will throw IllegalArgumentException. * /
SortedMap<K,V> tailMap(K fromKey);
/** * returns the first (lowest) key currently in this mapping. * /
K firstKey(a);
/** * returns the current last (highest) key in this mapping. * /
K lastKey(a);
/** * Returns the Set view that contains the key in this map. Iterators to set return keys in ascending order. * * The set is supported by the map, so changes to the map are reflected in the set and vice versa. * If a map is modified while iterating over a set (except through the iterator's own remove operation), * the result of the iteration is indeterminate. * This set supports element deletion, removing the corresponding mapping from the map. Remove, set. remove, removeAll, retainAll, and clear. * It does not support add or addAll operations. * /
Set<K> keySet(a);
/** * Returns the Collection view of the values contained in this map. Iterators to the collection return values in ascending order for the corresponding key. * * The collection is supported by the map, so changes to the map are reflected in the collection and vice versa. * If the map is modified while iterating over a collection (except through the iterator's own remove operation), * the result of the iteration is indeterminate. * This collection supports element deletion, removing the corresponding mapping from the map. Remove, collection. remove, removeAll, retainAll, and clear. * It does not support add or addAll operations. * /
Collection<V> values(a);
/** * Returns the Set view that contains the map in this map. The iterator to set returns entries in ascending key order. * * The set is supported by the map, so changes to the map are reflected in the set and vice versa. * If map * is modified while iterating over a set (except through the iterator's own remove operation or the setValue operation on the mapping entry returned by the iterator), * the result of the iteration is undefined. * This set supports element deletion, removing the corresponding mapping from the map. Remove, set. remove, removeAll, retainAll, and clear. * It does not support add or addAll operations. * /
Set<Map.Entry<K, V>> entrySet();
}
Copy the code3.2 NavigableMap
NavigableMap is a SortedMap that extends the Map interface of the navigation method, returning the closest match to the specified search target.
public interface NavigableMap<K.V> extends SortedMap<K.V> {
/** * returns the maximum key-value mapping strictly smaller than the given key; If no such key exists, null is returned. * /
Map.Entry<K,V> lowerEntry(K key);
/** * returns the maximum key that is strictly smaller than the given key; If no such key exists, null is returned. * /
K lowerKey(K key);
/** * returns the key-value mapping of the maximum key-association less than or equal to the given key, or null if there is no such key. * /
Map.Entry<K,V> floorEntry(K key);
/** * returns the maximum key less than or equal to the given key; If no such key exists, null is returned. * /
K floorKey(K key);
/** * returns the key-value mapping of the smallest key association greater than or equal to the given key, or null if there is no such key. * /
Map.Entry<K,V> ceilingEntry(K key);
/** * returns the smallest key greater than or equal to the given key; If no such key exists, null is returned. * /
K ceilingKey(K key);
/** * returns the key-value mapping that is at least greater than the minimum key association for the given key; If no such key exists, null is returned. * /
Map.Entry<K,V> higherEntry(K key);
/** * returns the minimum key that is strictly greater than the given key; If no such key exists, null is returned. * /
K higherKey(K key);
/** * returns the key-value map of the smallest key association in this map; If the mapping is empty, null is returned. * /
Map.Entry<K,V> firstEntry(a);
/** * returns the key-value map of the largest key-association in this map, or NULL if the map is empty. * /
Map.Entry<K,V> lastEntry(a);
/** * Removes and returns the key-value map associated with the smallest key in this map, or null if the map is empty. * /
Map.Entry<K,V> pollFirstEntry(a);
/** * Removes and returns the key-value map associated with the largest key in this map, or null if the map is empty. * /
Map.Entry<K,V> pollLastEntry(a);
/** * descend, descend, descend, descend, descend, descend, descend, descend, descend * * Returns a reverse view of the mappings contained in this mapping. * The descending map is supported by the map, so changes to the map are reflected in the descending map and vice versa. * If the map is modified when iterating over the collection view of the map * (except through the iterator's own remove operation), the result of the iteration is indeterminate. * /
NavigableMap<K,V> descendingMap(a);
/** * Returns the NavigableSet view of the keys contained in this map. * The iterator to set returns the key in ascending order. * * This set is supported by a map, so changes to the map are reflected in the set and vice versa. * If the mapping is modified when iterating over a set (except through the iterator's own remove operation), the result of the iteration is indeterminate. Remove, set. remove, removeAll, retainAll, and clear. * It does not support add or addAll operations. * /
NavigableSet<K> navigableKeySet(a);
/** * Returns the NavigableSet view of the reverse order of the keys contained in this map. * Iterators to set return keys in descending order. * * This set is supported by a map, so changes to the map are reflected in the set and vice versa. * If the mapping is modified when iterating over a set (except through the iterator's own remove operation), the result of the iteration is indeterminate. Remove, set. remove, removeAll, retainAll, and clear. * It does not support add or addAll operations. * /
NavigableSet<K> descendingKeySet(a);
/** * Returns a partial view of this map with keys ranging fromKey to toKey. * If fromKey and toKey are equal, the mapping returned is empty unless both fromInclusive and toInclusive are true. * The returned map is supported by this map, so changes in the returned map are reflected in this map and vice versa. * The returned map supports all optional map operations supported by the map. The map returned by * * will throw IllegalArgumentException to try to insert a key outside its scope, * or to construct a submap whose endpoints are outside its scope. * /
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive);
/** * Returns a partial view of this map whose key is less than (or equal to, if inclusive is true) toKey. * * The returned map is supported by this map, so changes in the returned map are reflected in this map and vice versa. * The returned map supports all optional map operations supported by the map. The map returned by * * will throw IllegalArgumentException to try to insert a key outside its scope, * or to construct a submap whose endpoints are outside its scope. * /
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
/** * Returns a partial view of this map whose key is greater than (or equal to, if inclusive is true) fromKey. * * The returned map is supported by this map, so changes in the returned map are reflected in this map and vice versa. * The returned map supports all optional map operations supported by the map. The map returned by * * will throw IllegalArgumentException to try to insert a key outside its scope, * or to construct a submap whose endpoints are outside its scope. * /
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
SubMap (fromKey, true, toKey, false) */
SortedMap<K,V> subMap(K fromKey, K toKey);
/** * equivalent to headMap(toKey, false) */
SortedMap<K,V> headMap(K toKey);
/** * equivalent to tailMap(fromKey, true) */
SortedMap<K,V> tailMap(K fromKey);
}
Copy the code3.3 TreeMap
Let’s look at the implementation of TreeMap, starting with the constructor.
3.3.1 Constructors
Here is the constructor source, there are four constructors. There are two constructs, no arguments, with Comparator inputs, and initialized from other maps.
public TreeMap(a) {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
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) {
}
}
Copy the code1. The no-argument constructor is set to null, indicating that the map is organized by natural sorting.
2. With the Comparator’s input parameter constructor, it is obvious that maps are organized in a custom Comparator way;
3.Map input parameter constructor, which sets the comparator to NULL and is converted by putAll.
If a map does not implement SortedMap, call super.putAll(map) directly. This actually calls putAll function in AbstractMap, which traverses the map and inserts it into TreeMap. If the map implements the SortedMap interface and the map size is not equal to 0 (mapSize! =0), and the map’s comparator is null, the number of modifications (modCount) is increased, and the buildFromSorted function is called.
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
if (size==0&& mapSize! =0 && map instanceofSortedMap) { Comparator<? > c = ((SortedMap<? ,? >)map).comparator();if(c == comparator || (c ! =null && c.equals(comparator))) {
++modCount;
try {
buildFromSorted(mapSize, map.entrySet().iterator(),
null.null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return; }}super.putAll(map);
}
Copy the code4.SortedMap input parameter constructor. This function first sets the comparator to the corresponding comparator of SortedMap and then calls buildFromSorted directly.
Now it’s time to demystify the buildFromSorted function.
3.3.2 rainfall distribution on 10-12 buildFromSorted function
This function is called in both constructors. According to the source detailed comments to understand first.
Create a tree based on sorted data linear time. You can accept keys and/or values from iterators or streams. This leads to too many parameters, but it seems better than the alternative. The four formats accepted by this method are:
1) Iterators to map. Entries (it! DefaultVal == null)
2) Key iterators (it! = null, defaultVal ! = null)
3) Streams of alternately serialized keys and values (it == NULL, defaultVal == NULL)
4) Serialize the key stream (it == null, defaultVal! = null)
Assume that the TreeMap comparator is set up before calling this method.
S I ze size size—- The number of keys (or key-value pairs) to be read from an iterator or stream
I t it it—- If it is non-empty, a new entry is created by reading the entry from the iterator or the key
S tr STR STR —- If not empty, a new entry is created from the key and the value may be read from the stream in serialized form. Either it or STR should be a non-null value
D efa U L T Va L defaultVal defaultVal—- If non-empty, this default value is used for each value in the mapping. If empty, each value is read from an iterator or stream as described above
private void buildFromSorted(intsize, Iterator<? > it, java.io.ObjectInputStream str, V defaultVal)
throws java.io.IOException, ClassNotFoundException {
this.size = size;
root = buildFromSorted(0.0, size-1, computeRedLevel(size),
it, str, defaultVal);
}
Copy the codeWhat is actually called internally is an overloaded version of the buildFromSorted function.
Recursive “helper methods” that do the actual work of the previous method. Parameters with the same name have the same definition. Other parameters are recorded below. Assume that the TreeMap comparator and size fields are set before calling this method (it ignores both fields).
L E V E L Level Level Of the current tree. The initial call should be 0;
L o lo lo The index of the first element of this subtree. The initial value should be 0;
H I hi hi The index of the last element of the subtree. The initial value should be size-1;
R e D L E V E L redLevel The redLevel should be red. For a tree of this size, it must equal computer level.
Let’s look at the computerized level method. This function is used to find the level at which all nodes are assigned BLACK, which can be interpreted as calculating the level of red nodes (it is used to calculate the number of levels in a complete binary tree).
private static int computeRedLevel(int sz) {
int level = 0;
for (int m = sz - 1; m >= 0; m = m / 2 - 1)
level++;
return level;
}
Copy the code
If the index of the root node is 0, then the index of the last node of the tree of height 2 is 2, and the index of the last node of height 3 is 6, which satisfies m = (m + 1) * 2. If we reverse m, m = m / 2-1. So what is the use of calculating this height? As shown in the figure above, if a tree has nine nodes, then when constructing a red-black tree, as long as the nodes of the first three layers are set to black and the nodes of the fourth layer are set to red, the finished tree is a red-black tree.
@SuppressWarnings("unchecked")
private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
intredLevel, Iterator<? > it, java.io.ObjectInputStream str, V defaultVal)
throws java.io.IOException, ClassNotFoundException {
/* * the root is the middle element. * To do this, we must first recursively construct the entire left subtree to get all its elements. * And then we can go to the right subtree. The * * LO and HI parameters are the minimum and maximum indexes to be extracted from the iterator or stream of the current subtree. * They are not actually indexed, we just do them sequentially to ensure that the items are extracted in the appropriate order. * /
if (hi < lo) return null;
// To move 1 to the right is essentially dividing by 2
int mid = (lo + hi) >>> 1;
Entry<K,V> left = null;
// Recursively build the left subtree
if (lo < mid)
left = buildFromSorted(level+1, lo, mid - 1, redLevel,
it, str, defaultVal);
// Extract keys and/or values from iterators or streams
K key;
V value;
if(it ! =null) {
if (defaultVal==null) { Map.Entry<? ,? > entry = (Map.Entry<? ,? >)it.next(); key = (K)entry.getKey(); value = (V)entry.getValue(); }else{ key = (K)it.next(); value = defaultVal; }}else { / / use the streamkey = (K) str.readObject(); value = (defaultVal ! =null ? defaultVal : (V) str.readObject());
}
Entry<K,V> middle = new Entry<>(key, value, null);
// color nodes in non-full bottommost level red These nodes are red if the current number of recursive layers is equal to the red level
if (level == redLevel)
middle.color = RED;
if(left ! =null) {
middle.left = left;
left.parent = middle;
}
// Recursively build the 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 middle;
}
Copy the code3.3.3 put method
The put method naturally acts as an “increment” in the add, delete, and update loop, essentially adding nodes to the red-black tree. We know that adding a node to a red-black tree (and eventually inserting a new node at the bottom) can cause the tree to be out of balance and therefore need to be rebalanced.
public V put(K key, V value) {
Entry<K,V> t = root;
// If the root node is empty, the map is empty, so use the current key and value to form a node and assign a value to the root node
if (t == null) {
compare(key, key); // Type (possibly empty) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// If else insertion insertion insertion insertion insertion insertion insertion insertion insertion insertion insertion
Comparator<? super K> cpr = comparator;
if(cpr ! =null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while(t ! =null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while(t ! =null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
Copy the code3.3.4 fixAfterInsertion method
The fixAfterInsertion method is initialized to solve insertion imbalances.
/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
while(x ! =null&& x ! = root && x.parent.color == RED) {if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(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 == rightOf(parentOf(x))) { x = parentOf(x); rotateLeft(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); }}else {
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;
}
Copy the codeLook at the implementation code above, the core adjustment process is included in the while loop, and the if else structure contains four cases, which are analyzed in detail below. By the way, one more thing before the analysis, let’s talk about some simple functions involved in it.
1. ParentOf —- Obtain the complex node of the node
2. LeftOf —- Obtains the left child node of the node
3. RightOf —- obtains the right child node of the node
4. SetColor —- Set the node color
5. ColorOf —- Obtain the node color
6. RotateLeft – left-handed
7. RotateRight – right
First we set the inserted x x x node to red. Next we check whether its parent node is also red. If so, the red-black tree balance is broken and needs to be adjusted in four cases.
Is a
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
Copy the code
Insert the 11
11 < 13, so the left subtree lookup from the root node can be analyzed in conjunction with the put method code above
Insert 11 into the left child of node 12, satisfying the condition of case 1 in the code:
1. It is a red node
2. The parent node is a red node
3. The uncle node (the right child of the grandfather node) is the red node
Adjust the parent node and the uncle node to black, and the grandfather node to red, so that the number of black nodes from the root node to the bottom leaf node is the same.
As a final step, the root node is dyed black because the nature of the red-black tree dictates that it is black.
root.color = BLACK;
Copy the code
Case 2
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
Copy the codeX == rightOf(parentOf(x)) (parentOf(x))) does not meet the criteria.
The next two pictures are dextral
Adjust the node color after right-handed rotation
This is slightly different from the order of execution in the code, the color can be adjusted after or before.
We see that if the fragment satisfies the previous if structure, it will rotate left first. Is actually inserted when as the right child!
The next two pictures are sinistral, and after sinistral we see that it becomes the familiar structure again, and then we need to adjust it to the right.
Is three
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));
Copy the codeIn the first two cases y, y, y is the right child. Now let’s look at y, y, and y is the left child. ParentOf (x) == leftOf(parentOf(x))) == rightOf(parentOf(x)))
Here again, you need to set the root node to black.
root.color = BLACK;
Copy the code
Is four
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
Copy the codeSo this is the last case, and just like in case three, we’re going to ignore the if structure. The code again sets the color of the parent node of x x x to black, the parent node to red, and the parent node to left-rotate.
And then if you think about the dextral case in the if structure, if x, x, x are inserted as the left child that satisfies this condition.
The following two images are right-handed. After right-handed rotation, return to the familiar structure above, add left-handed rotation and color adjustment and you’re done.
Color == RED in the while loop. If the condition is not met, no adjustment is required. Why?
If the parent node is black, the addition of red leaf nodes does not affect the balance (the number of black nodes passing from the following node to the new current node does not change).
3.3.5 the remove method
The method of adding nodes is analyzed in detail above, and the method of deleting nodes is analyzed next.
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
Copy the codeThe above code is very short. First, we call getEntry to get the corresponding node and determine whether it is NULL. If it is null, we return null directly. So the main thing is actually the deleteEntry method.
/** * delete node p and rebalance the tree. * /
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// If strictly internal, the successor element is copied to p, and then p points to the successor.
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 the repair on the replacement node (if present).Entry<K,V> replacement = (p.left ! =null ? p.left : p.right);
if(replacement ! =null) {
// Assign the parent of p to the parent pointer of the replacement node
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// Set the pointer to P to null for the fixAfterDeletion function to use
p.left = p.right = p.parent = null;
// Repair the replacement node
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { Return if we are the only node.
root = null;
} else { // No children. Use self as phantom replacement and unlink.
if (p.color == BLACK)
fixAfterDeletion(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; }}}Copy the codeThe preceding code encountered the functions first, the concrete implementation of which was analysed.
/** * returns the successor of the specified Entry; If not, null is returned. * /
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if(t.right ! =null) {
Entry<K,V> p = t.right;
while(p.left ! =null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while(p ! =null && ch == p.right) {
ch = p;
p = p.parent;
}
returnp; }}Copy the codeThe so-called successor node refers to finding the first node larger than the current node and ranking after the current node in middle-order traversal, which can be divided into three cases.
1. If the current node is NULL, null is returned.
2. If the current node has a right child, the smallest node in the subtree below the right child must be the lowest left leaf node of the subtree.
If the child to the right of the current node is null, then we need to find its parent node. The premise is that the current node must be in the left child tree. Is the successor node that meets the requirements.
Looking at the deleteEntry method, if neither the left child nor the right child of P is null, then copy the successor element to P and point P to the successor. Next look at the if else structure of the following code to correct the deletion of the node.
Is a
The p node has a non-null child node, in which case replacement is equal to the child node whose p node is not NULL.
1. Replacement is equal to the left child of the p node
First, the parent node of p node is assigned to the parent node pointer of replacement. When p == P. parent.right = replacement, Then, the Pointers of p node (left, right, and parent) were set to NULL. If the color of P was black, the fixAfterDeletion function was called to repair the deletion on the replacement node.
2. Replacement is equal to the right child of the p node
Similarly, the parent node of p node is assigned to the parent node pointer of replacement. When p == P. prent. left, p. prent. left = replacement, Then, the Pointers of p node (left, right, and parent) were set to NULL. If the color of P was black, the fixAfterDeletion function was called to repair the deletion on the replacement node.
No matter replacement is equal to the left or right child of p node, if the parent node of P is NULL, then p node must be the previous root node and the previous root node is deleted, so the replacement node needs to be promoted to the root node. Then, the Pointers of p node (left, right, and parent) were all set to NULL. Finally, the color of P must be black. Call the fixAfterDeletion function to repair the deletion on the replacement node.
Case 2
The children of the p node are all NULL, in which case replacement is equal to NULL.
1. If the parent node of P is NULL, it indicates that P is the root node, and all the child nodes of P are NULL, so p node is the only node in the red-black tree. If root node is deleted, the value root = NULL is directly assigned, which means that the red-black tree is empty.
2. The parent node of P is not NULL
(1) If the color of P is black, deleting a black node may cause imbalance (missing black nodes), so call fixAfterDeletion§ to rebalance.
(2) If the color of P is red, deleting a red node will not affect the number of black nodes on this path, so there is no need to call fixAfterDeletion§.
In both cases (1) and (2) above, we need to break and p links
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;
}
Copy the codeIf p is the left child node, set P. parent.left to null; Similarly, if p is the right child node, set p.parent.right to null; Finally, set P. parent to null.
Is three
None of the child nodes of the p node is NULL. In this case, the successor node of P needs to be found first. Replace the current node to be deleted with a successor node, and the following code executes as in cases 1 and 2.
if(p.left ! =null&& p.right ! =null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
}
Copy the codeLet’s look at a simple deletion case where node 12 is removed from the tree. First of all, the left and right children of the 12 nodes exist, so we look for the successor node, find that the successor node is 20, replace the 12 nodes with 20, and finally disconnect the previous link of the successor node.
3.3.6 fixAfterDeletion method
This method is used to fix the imbalance caused by deleting a node, and is called at two points in deleteEntry. We can see that there are a lot of if and else cases in this method, so let’s label each of the eight cases.
private void fixAfterDeletion(Entry<K,V> x) {
while(x ! = root && colorOf(x) == BLACK) {if (x == leftOf(parentOf(x))) {
Entry<K,V> sib = rightOf(parentOf(x));
if (colorOf(sib) == RED) { / / a
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) { / / 2
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) { / / is three
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
/ / is foursetColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; }}else { // Symmetric
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) { / / is five
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) { / / is six
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) { / / is seven
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
/ / is eight
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
Copy the codeIs a
When x is a black left node and sib is a red sibling node, you need the sibling node to go from red to black, the parent node to red, and you rotate left around the parent node, the structure of the left-spin tree changes, and then you reassign sib, and sib points to the sibling node of X.
After a series of actions, it doesn’t end, it might end up in case 2, or case 3 and case 4.
Case 2
If node X, its sibling node sib, and the left and right child nodes of siB are all black, change siB from black to red, point X to the parent node of the current X, and set node X to black.
Is three
If the left child node of SIB is red, set the left child node of SIB to black and the right child node of SIB to red, rotate the left child node of SIB around siB, and then point the sib to the brother node of X. Let’s go to case 4.
Is four
Node x, x brothers sib is black, and the sib about child node is red, left or right child node to child nodes is black, now need to set the color of the sib node into the same color and x’s parent p, set the x’s parent is black color, set the sib right child’s color is black, left-handed parent x p, Then assign x to root.
The last four cases are symmetric, so let’s seeIs eight
If we delete 50, what happens?
The left and right child nodes of the node 50 are not null. First, find the subsequent node (100) and replace 50 with 100. P points to 100. Because the left and right child nodes of the successor node 100 are null and its color is black, fixAfterDeletion is then called.
The SIB node, which is 30, only works in this case. Set the color of 30 to red, the 100 node after replacing 50 to black, and the left child (20) of 30 to black. Replace 50 with 100 nodes as the pivot right.
Finally, the previous successor node is disconnected.
References:
1. www.cs.usfca.edu/~galles/vis…
2. www.cnblogs.com/liahon/p/11…