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,

  1. 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
  2. Comparable if there is a comparator, and comparable if there is no comparable key

Succeeded () finds the next node

  1. incontainsValue()Succeeded from the first node
  2. inforEach()Succeeded from the first node
  3. replaceAll()Antecedent goes through assigning new values from the first node
  4. remove()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, withDescendingMapSame, just the opposite implementation