TreeMap is a Map collection that can compare the size of elements. It will sort the size of the incoming key s. You can use the natural order of elements, or you can use a custom comparator in the collection to sort.
The tree structure is realized at the bottom of TreeMap, and a structure of red black tree is realized. TreeMap inherits from AbstractMap and implements map, Cloneable, navigablemap and serializable interfaces.
Obtain minimum and maximum:
Because his underlying principle is a red black tree, the minimum and maximum are actually the leftmost and rightmost.
Success method / predecessor method:
The successor method is used to find subsequent nodes of this node. The predecessor method is used to find the precursor node.
See reprint blog for details: TreeMap method success / predecessor diagram_ dengjili's column - CSDN blog
Left and right rotation methods of trees:
fixAfterInsertion method:
Each time a node is inserted, it will call a method of red black tree balance by default
/** 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;
}The corresponding fixAfterDeletion method
It is a method called when deleting nodes to maintain the balance of red and black trees.
/** From CLR */
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) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
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(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // symmetric
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;
}
}
}
setColor(x, BLACK);
}Common methods:
public Map.Entry ceilingEntry(K key)
Returns the element whose specified Key is greater than or equal to the minimum value. If not, null is returned
public K ceilingKey(K key)
Returns the Key whose specified Key is greater than or equal to the minimum value. If not, null is returned
public Comparator super K> comparator()
If the default comparator is used, null is returned. If other comparators are used, the hash code value of the comparator is returned
public NavigableSet descendingKeySet()
Returns all keys of the set in reverse order
public NavigableMap descendingMap()
Return the set in reverse order
public Map.Entry firstEntry()
Returns the element with the smallest Key in the collection
public K firstKey()
Returns the key of the smallest key in the set
public Map.Entry floorEntry(K key)
In contrast to the ceilingEntry() method, it returns an element that is less than or equal to the maximum key of the key
public K floorKey(K key)
Returns the key with the largest key less than or equal to the key
public SortedMap headMap(K toKey)
Returns all elements whose Key is less than toKey
public NavigableMap headMap(K toKey, boolean inclusive)
When inclusive is true, all elements whose Key is less than or equal to toKey are returned
public Map.Entry higherEntry(K key)
Returns all elements whose key is greater than the key
public K higherKey(K key)
Returns all keys whose key is greater than the key
public Map.Entry lastEntry()
Returns the element with the largest Key
public K lastKey()
Returns the largest Key
public Map.Entry lowerEntry(K key)
Returns the largest element smaller than the key
public K lowerKey(K key)
Returns a key smaller than the maximum key
public Map.Entry pollFirstEntry()
Delete the smallest key element
public Map.Entry pollLastEntry()
Delete the element with the largest Key
public NavigableMap subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
Intercept the elements from fromKey to toKey in the set. If false, they will be intercepted
public NavigableMap tailMap(K fromKey, boolean inclusive)
When inclusive is true, intercept all elements whose Key is greater than or equal to fromKey; otherwise, intercept all elements whose Key is greater than fromKey