This is the third day of my participation in the August Text Challenge.More challenges in August
TreeMap
Introduction to the
TreeMap is a structure directly implemented by red-black tree. Sorting the comparison of Key values, it is obvious that:
The class of the key must implement the Comparable method. The ClassCastException must not be thrown, otherwise a Comprartor must be specified
2. Since TreeMap implements the Serializable interface, default or custom comparators should also implement this interface
Most importantly, it implements NavigableMap, which I understand as a navigation map, providing various operations to manipulate the Map view
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{}
Copy the code
A constructor
The four constructors are essentially compatators or not using the default
For unordered Map, putAll is called directly, and ordered SortedMap recursively calls buildFromSorted to improve efficiency
public TreeMap() {
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 code
But putAll still judged the instanceof SortedMap
Specific red-black tree operations are not described here
Remove (),put() is the most fundamental operation of red-black tree, get() is also a more intuitive implementation of binary search tree
Methods,
- The way you do things with trees is you have a lot of branches, you have to think about all the different things and then you convert them to code
- Comparable if there is a comparator, and comparable if there is no comparable key
Succeeded () finds the next node
- in
containsValue()
Succeeded from the first node - in
forEach()
Succeeded from the first node replaceAll()
Antecedent goes through assigning new values from the first noderemove()
Traverse to find Object delete
Static <K,V> treemap. Entry<K,V> t (Entry<K,V> t) {// First to be clear, the next node is a node larger than the current one, 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; // When the right node is empty and is the right node of the parent node, the next node is the parent of the current branch tree while (p! = null && ch == p.right) { ch = p; p = p.parent; } // If the right node is empty and is the left node of the parent node, the next node's parent of the current node returns p; }}Copy the code
GetCeilingEntry ()/getFloorEntry Gets the maximum/minimum value of [Low,key]/[key,high]. No NULL is returned
// The next node to find if the search tree failed final Entry<K,V> getCeilingEntry(K key) {Entry<K,V> p = root; while (p ! = null) { int cmp = compare(key, p.key); If (CMP < 0) {if (p.left! = null) p = p.left; else return p; } else if (CMP > 0) {// if (p.right! = null) { p = p.right; } else {// Here the same thing, bigger than the right-most leaf, the next one being the parent of the current subtree Entry<K,V> parent = P. parent; Entry<K,V> ch = p; while (parent ! = null && ch == parent.right) { ch = parent; parent = parent.parent; } return parent; }} else // Return the current node if it is equal. } return null; } final Entry<K,V> getFloorEntry(K key) {Entry<K,V> p = root; while (p ! = null) { int cmp = compare(key, p.key); If (CMP > 0) {if (p.right! = null) p = p.right; else return p; } else if (CMP < 0) {// if (p.left! = null) { p = p.left; } else { Entry<K,V> parent = p.parent; Entry<K,V> ch = p; // While (parent!) is smaller than the leftmost leaf and the next is the parent of the current child tree = null && ch == parent.left) { ch = parent; parent = parent.parent; } return parent; }} else // Return the current node if it is equal. } return null; }Copy the code
GetHigherEntry ()/getLowerEntry Retrieves the maximum or minimum value of [Low,key)/(key,high]. Null is not returned
It’s the same thing as getCeilingEntry except for equality, we don’t consider equality
final Entry<K,V> getHigherEntry(K key) { Entry<K,V> p = root; while (p ! = null) { int cmp = compare(key, p.key); if (cmp < 0) { if (p.left ! = null) p = p.left; else return p; } else { if (p.right ! = null) { p = p.right; } else { Entry<K,V> parent = p.parent; Entry<K,V> ch = p; while (parent ! = null && ch == parent.right) { ch = parent; parent = parent.parent; } return parent; } } } return null; }Copy the code
DescendingMap () to flip the map
The underlying implementation is provided by DescendingSubMap(), which is actually the same map, except that all operations, such as getFist (), are converted to getLast(), so operations with DescendingMap() still affect the original map
Similarly, operations on subMap() affect the original Map
static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> { private static final long serialVersionUID = 912986545866120460L; // m is the current Map,fromStart is true, lo is null, lo is the starting position, DescendingSubMap(TreeMap<K,V> m, Boolean fromStart, K lo, Boolean loInclusive, Boolean toEnd, K hi, boolean hiInclusive) { super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); }Copy the code
Treemap. Entry<K,V> subLowest() {return absHighest(); } TreeMap.Entry<K,V> subHighest() { return absLowest(); } TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); } TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); } TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); } TreeMap.Entry<K,V> subLower(K key) { return absHigher(key); }Copy the code
subMap()+headMap()+tailMap()
The normal map calls areAscendingSubMap
, withDescendingMap
Same, just the opposite implementation