TreeMap

1.TreeMap结构

基于红黑树（Red-Black tree）的 NavigableMap 实现。
特点：迭代有序，TreeMap的key和value值不允许为Null，TreeMap的key必须实现Comparable(自然排序)或者指定Comparator(定制化排序)
关于循环删除，增强for循环删除会修改modCount++，导致fail-fast，所以会报错ConcurrentModificationException
迭代器循环删除节点后并没有对modCount修改，所以迭代器支持删除

2.TreeMap内部结构

/** 成员变量信息 */
// 构造器取值，该值决定排序使用自然顺序还是Comparator定制化排序
private final Comparator<? super K> comparator;
// 红黑树根节点
private transient Entry<K,V> root;
// 长度
private transient int size = 0;
// fail-fast机制
private transient int modCount = 0;
// TreeMap的红黑树节点对应的集合，entryset迭代
private transient EntrySet entrySet;
// TreeMap键的KeySet集合，keyset迭代
private transient KeySet<K> navigableKeySet;
// TreeMap键值对的倒序 待研究
private transient NavigableMap<K,V> descendingMap;
// 节点颜色
private static final boolean RED   = false;
private static final boolean BLACK = true;

/** 内部类信息 */
// 内部类 实现红黑树
static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
    }
}

2.TreeMap构造器

    // 默认构造，使用Comparable自然排序
    public TreeMap() {
        comparator = null;
    }
    // 指定comparator，定制排序(如按某个类的某字段排序)
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
    // 同默认构造，使用Comparable自然排序
    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) {
        }
    }

3.查找(get方法)

遍历红黑树，从根节点开始，遍历方式同红黑树，key小于根节点key则往左节点查，key大于根节点key则往右节点查

  public V get(Object key) {
        TreeMap.Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }

    final TreeMap.Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        TreeMap.Entry<K,V> p = root;
        //红黑树不为空则遍历
        //二叉查找树遍历逻辑 key小于根节点key则往左节点查，key大于根节点key则往右节点查，
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }

4.新增(put方法)

遍历红黑树，寻找插入节点 -> 绑定新节点与父节点关系 -> 修复红黑树

  public V put(K key, V value) {
      TreeMap.Entry<K,V> t = root;
      // 根节点为 null，将新节点设为根节点
      if (t == null) {
          compare(key, key); // type (and possibly null) check

          root = new TreeMap.Entry<>(key, value, null);
          size = 1;
          modCount++;
          return null;
      }
      int cmp;
      TreeMap.Entry<K,V> parent;
      // split comparator and comparable paths
      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赋值为最小父节点
              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);
      }
      // 新节点信息 parent最小父节点，绑定新节点与父节点信息
      TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent);
      // 绑定父节点的子节点信息=新节点
      if (cmp < 0)
          parent.left = e;
      else
          parent.right = e;
      //修复红黑树性质，调节颜色，结构，根节点等
      fixAfterInsertion(e);
      size++;
      modCount++;
      return null;
  }

5.删除(remove方法)

根据删除节点的子节点数目判断删除方法，通过后继节点替换，完成隔p链接，部分情况需要修复节点

public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    // p有两个子节点
    if (p.left != null && p.right != null) {
        // 找到后继节点
        Entry<K,V> s = successor(p);
        // 将p赋值并指向其后继节点
        p.key = s.key;
        p.value = s.value;
        // 将p引用为后继节点
        p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    // 注意当p有两个子节点时，p为后继节点， p的子节点为新的替换节点
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    // 删除节点存在一个子节点(左或右)，用父节点直接链接删除节点的子节点（替换节点）
    if (replacement != null) {
        // 将替换节点(子节点或后继节点)的父节点与p的父节点连线，隔p连线
        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;

        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null;

        // 删除黑色需要调整红黑树
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { 
        // 删除的是根节点，且树中有且仅有一个节点
        root = null;
    } else { 
        // 删除的节点没有孩子节点
        
        // p是黑色，则需要进行调整
        if (p.color == BLACK)
            fixAfterDeletion(p);

        // 将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;
        }
    }
}

5.1查前驱后继

    /**
     * 后继节点：大于当前节点值并且值最小的节点
     */
    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 {
            // 这里如果不理解，简单画张结点图就可以很清晰
            // 没有右子树的情况，首先分析下，其左子树都是比当前结点小的，所以不用考虑左子树有没有的情况
            // 再思考下，1、如果当前结点为父节点的左子结点，那么最小值就是父节点
            // 2、如果当前结点为父节点的右子结点，往父节点思考，从父节点一直往上找，
            // 直到找到某结点为其父节点的左孩子时，这个父节点就是后继节点
            Entry<K,V> p = t.parent;
            Entry<K,V> ch = t;
            // 父节点不为空，且当前结点为右子结点，则父节点为后继
            while (p != null && ch == p.right) {
                ch = p;
                // 注意 这里返回的是parent
                p = p.parent;
            }
            return p;
        }
    }

    /**
     * 前继节点：小于当前节点值并且值最大的节点
     */
    static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
        if (t == null)
            return null;
        else if (t.left != null) {
            Entry<K,V> p = t.left;
            while (p.right != null)
                p = p.right;
            return p;
        } else {
            // 这里如果不理解，简单画张结点图就可以很清晰
            // 没有左子树的情况，首先分析下，其右子树都是比当前结点大的，所以不用考虑右子树有没有的情况
            // 再思考下，1、如果当前结点为父节点的右子结点，那么最大值就是父节点
            // 2、如果当前结点为父节点的左子结点，往父节点思考，从父节点一直往上找，
            // 直到找到某结点为其父节点的右孩子时，这个父节点就是前继节点
            Entry<K,V> p = t.parent;
            Entry<K,V> ch = t;
            // 父节点不为空，且当前结点为左子结点，则父节点为前驱节点
            while (p != null && ch == p.left) {
                ch = p;
                // 注意 这里返回的是parent
                p = p.parent;
            }
            return p;
        }
    }

6.遍历

关于循环删除，增强for循环删除会修改modCount++，导致fail-fast，所以会报错ConcurrentModificationException
迭代器循环删除节点后并没有对modCount修改，所以迭代器支持删除

    // treeMap.entrySet() 遍历迭代器
    final class EntryIterator extends TreeMap.PrivateEntryIterator<Map.Entry<K,V>> {
        EntryIterator(TreeMap.Entry<K,V> first) {
            super(first);
        }
        public Map.Entry<K,V> next() {
            return nextEntry();
        }
    }

    // treeMap.values() 遍历迭代器
    final class ValueIterator extends TreeMap.PrivateEntryIterator<V> {
        ValueIterator(TreeMap.Entry<K,V> first) {
            super(first);
        }
        public V next() {
            return nextEntry().value;
        }
    }

    // treeMap.keySet() 遍历迭代器
    final class KeyIterator extends TreeMap.PrivateEntryIterator<K> {
        KeyIterator(TreeMap.Entry<K,V> first) {
            super(first);
        }
        public K next() {
            // 正序
            return nextEntry().key;
        }
    }

    // treeMap.descendingKeySet() 倒序遍历迭代器
    final class DescendingKeyIterator extends TreeMap.PrivateEntryIterator<K> {
        DescendingKeyIterator(TreeMap.Entry<K,V> first) {
            super(first);
        }
        public K next() {
            // 倒序
            return prevEntry().key;
        }
        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            deleteEntry(lastReturned);
            lastReturned = null;
            expectedModCount = modCount;
        }
    }

    abstract class PrivateEntryIterator<T> implements Iterator<T> {
        TreeMap.Entry<K,V> next;
        // 当前遍历的最后一个节点
        TreeMap.Entry<K,V> lastReturned;
        int expectedModCount;

        PrivateEntryIterator(TreeMap.Entry<K,V> first) {
            expectedModCount = modCount;
            lastReturned = null;
            next = first;
        }

        public final boolean hasNext() {
            return next != null;
        }

        final TreeMap.Entry<K,V> nextEntry() {
            TreeMap.Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            // fail-fast
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // 寻找e的后继节点
            next = successor(e);
            lastReturned = e;
            return e;
        }

        // DescendingKeyIterator 倒序遍历迭代器调用
        final TreeMap.Entry<K,V> prevEntry() {
            TreeMap.Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            // fail-fast
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // 寻找e的前继节点
            next = predecessor(e);
            lastReturned = e;
            return e;
        }

        // 这里删除节点后并没有对modCount修改，所以迭代器支持删除
        // 而增强for循环删除会modCount++，与构造器生成的modCount不等，则会删除异常
        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            // fail-fast
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // deleted entries are replaced by their successors
            if (lastReturned.left != null && lastReturned.right != null)
                // 删除当前结点，将当前结点值赋值给下一节点，防止遍历出问题
                next = lastReturned;
            // 删除节点，更给结点关系
            deleteEntry(lastReturned);
            // 重新赋值expectedModCount
            expectedModCount = modCount;
            lastReturned = null;
        }
    }