环境和版本
简介
前置知识
- 红黑树的5个性质
- 红黑树的左旋和右旋
属性
buildFromSorted
putAll方法
Entry节点
put方法
fixAfterInsertion自平衡 TODO
remove方法
获得首尾的元素
containsValue方法
clear方法
获取迭代器
查找范围的元素 TODO
参考和推荐文章

环境和版本

Mac M1
IDEA 2021
Zulu Open JDK

简介
与HashMap相比，TreeMap是一个可以比较元素大小的Map集合。会对传入的Key进行排序。
不同于HashMap的哈希映射，TreeMap底层实现了树结构，其就是红黑树。也即是说，整个TreeMap就是一颗红黑树
我们在讲解HashMap之前，先学习的手写红黑树，哪个红黑树实现没有删除方法，但是TreeMap就是一个完整的红黑树操作了

前置知识

红黑树的5个性质
性质1：每个节点要么是红色，要么是黑色。
性质2：根节点是黑色
性质3：每个叶子节点是黑色
性质4：每个红色节点的子节点一定是黑色
性质5：任意一个节点到每个子节点的路径都包含数量相同的黑节点，俗称黑高
从性质5可以推出：如果一个节点存在黑子节点，那么该节点肯定有两个子节点

红黑树的左旋和右旋
参见HashMap那篇

属性
```java // 比较器 private final Comparator<? super K> comparator;

// 根节点 private transient Entry root;

// 元素大小 private transient int size = 0;

// 修改次数 private transient int modCount = 0;

<a name="J9QsG"></a>
# 构造函数
```java
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) {
    }
}

buildFromSorted

private void buildFromSorted(int size, Iterator<?> it,
                             java.io.ObjectInputStream str,
                             V defaultVal)
    throws  java.io.IOException, ClassNotFoundException {
    // 设置key-value键值对的数量
    this.size = size;
    // computeRedLevel 计算树的高度
    // 构建红黑树，返回根节点
    root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
                           it, str, defaultVal);
}
// 计算高度
private static int computeRedLevel(int sz) {
    int level = 0;
    for (int m = sz - 1; m >= 0; m = m / 2 - 1)
        level++;
    return level;
}
// buildFromSorted
// 
private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
                                         int redLevel,
                                         Iterator<?> it,
                                         java.io.ObjectInputStream str,
                                         V defaultVal)
    throws  java.io.IOException, ClassNotFoundException {
    // 递归结束
    if (hi < lo) return null;
    // 计算中间值
    int mid = (lo + hi) >>> 1;
    // 创建左子树
    Entry<K,V> left  = null;
    if (lo < mid)
        // 递归左子树
        left = buildFromSorted(level+1, lo, mid - 1, redLevel,
                               it, str, defaultVal);
    // extract key and/or value from iterator or stream
    // 获得key-value键值对
    K key;
    V value;
    // 使用it迭代器，获取下一个值
    if (it != null) {
        if (defaultVal==null) {
            // 下一个 entry 节点
            Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
            key = (K)entry.getKey();
            value = (V)entry.getValue();
        } else {
            key = (K)it.next();
            value = defaultVal;
        }
    } else { // use stream
        // 处理Stream 流的情况
        key = (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
    // 如果到树的最大高度，则设置为红节点
    if (level == redLevel)
        middle.color = RED;
    // 如果左子树非空，则进行设置
    if (left != null) {
        // 当前节点，设置左子树
        middle.left = left;
        // 左子树设置父亲节点
        left.parent = middle;
    }
    // 创建右节点
    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;
}

putAll方法

public void putAll(Map<? extends K, ? extends V> map) {
    int mapSize = map.size();
    // 满足如下条件 调用 buildFromSorted 处理
    // TreeMap 大小为0
    // mapSize 非0
    // 是 SortedMap
    if (size==0 && mapSize!=0 && map instanceof SortedMap) {
        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);
}

Entry节点


private static final boolean RED   = false;
private static final boolean BLACK = true;
static final class Entry<K,V> implements Map.Entry<K,V> {
    // 节点 k
    K key;
    // 节点 v
    V value;
    // 左孩子节点
    Entry<K,V> left;
    // 右孩子节点
    Entry<K,V> right;
    // 父节点
    Entry<K,V> parent;
    // 颜色
    boolean color = BLACK;
    /**
         * Make a new cell with given key, value, and parent, and with
         * {@code null} child links, and BLACK color.
         */
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
    /**
         * Returns the key.
         *
         * @return the key
         */
    public K getKey() {
        return key;
    }
    /**
         * Returns the value associated with the key.
         *
         * @return the value associated with the key
         */
    public V getValue() {
        return value;
    }
    /**
         * Replaces the value currently associated with the key with the given
         * value.
         *
         * @return the value associated with the key before this method was
         *         called
         */
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }
    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
    }
    public int hashCode() {
        int keyHash = (key==null ? 0 : key.hashCode());
        int valueHash = (value==null ? 0 : value.hashCode());
        return keyHash ^ valueHash;
    }
    public String toString() {
        return key + "=" + value;
    }
}

put方法

public V put(K key, V value) {
    // 根节点 赋给t
    Entry<K,V> t = root;
    // 如果没有根节点
    // 使用key-value创建根节点
    if (t == null) {
        // 比较
        compare(key, key); // type (and possibly null) check
        // 使用key-value创建根节点
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    // 遍历红黑树
    // key 比父节点小还是大
    int cmp;
    // 父节点
    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 {
        // key 不能为空 因为要用到比较器
        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
    Entry<K,V> e = new Entry<>(key, value, parent);
    // 如果 cmp 小于0
    // 设置到父节点的左孩子
    if (cmp < 0)
        parent.left = e;
    else
        // 设置到父节点的右节点
        parent.right = e;
    // 插入后进行自平衡
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

fixAfterInsertion自平衡 TODO

有点懵逼，等我手写红黑树之后再来啃

或者参见底部参考文章 ```java private void fixAfterInsertion(Entry 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; }

<a name="jwGrd"></a>
# get方法
```java
public V get(Object key) {
    // 获取 entry
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

final 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;
    Entry<K,V> p = root;
    // 迭代
    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;
}
final Entry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
    K k = (K) key;
    Comparator<? super K> cpr = comparator;
    // 迭代，二叉树插座
    if (cpr != null) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

remove方法

删除方法比较复杂，这里会使用一棵树来进行测试

情况1：无子节点。直接删除父节点对其的指向即可。例如叶子节点5、11、14、18
情况2：只有左子节点。将删除节点的父节点，指向删除节点的左子节点。例如说，节点 20 。可以通过将节点 15 的右子节点指向节点 19
情况3：只有右子节点。和情况二的处理方式一致。将删除节点的父节点，指向删除节点的右子节点
情况4：有左子节点+右子节点。这种比较复杂，因为无法使用子节点替换删除的节点。删除15为例
- 先查找15的右子树的最小值，找到节点是17
- 将将17设置到15上。因为节点17是右子树的最小值，能够满足比节点15的左子树都大，比右子树都小，这样问题就变成删除节点17
- 删除节点17的过程，满足情况3。将节点19的左子节点指向节点18即可。 ```java public V remove(Object key) { // 获取 entry Entry p = getEntry(key); if (p == null) return null;
  
  V oldValue = p.value; deleteEntry(p); return oldValue; }

private void deleteEntry(Entry p) { modCount++; size—;

// If strictly internal, copy successor's element to p and then make p
// point to successor.
// 要删除的节点既有左子节点也有右子节点
if (p.left != null && p.right != null) {
    // 获得右子树的最小值
    Entry<K,V> s = successor(p);
    // 修改 p 的 key-value 为 s 的 key-value 键值对
    p.key = s.key;
    p.value = s.value;
    // 设置 p 指向 s 此时，就变成删除 s 节点了。
    p = s;
} // p has 2 children

// Start fixup at replacement node, if it exists.
// 获得替换节点
Entry<K,V> replacement = (p.left != null ? p.left : p.right);

// 有子节点的情况
if (replacement != null) {
    // Link replacement to parent
    // 替换节点的父节点，指向 p 的父节点
    replacement.parent = p.parent;
    if (p.parent == null)
        // 如果 p 的父节点为空，则说明 p 是根节点，直接 root 设置为替换节点
        root = replacement;
    else if (p == p.parent.left)
        // 如果 p 是父节点的左子节点，则 p 的父子节的左子节指向替换节点
        p.parent.left  = replacement;
    else
        // 如果 p 是父节点的右子节点，则 p 的父子节的右子节指向替换节点
        p.parent.right = replacement;

    // Null out links so they are OK to use by fixAfterDeletion.
    // 置空 p 的所有指向
    p.left = p.right = p.parent = null;

    // Fix replacement
    // 如果 p 的颜色是黑色，则执行自平衡
    if (p.color == BLACK)
        fixAfterDeletion(replacement);
    //如果 p 没有父节点，说明删除的是根节点，直接置空 root 即可
} else if (p.parent == null) { // return if we are the only node.
    root = null;
    // 如果删除的没有左子树，又没有右子树
} else { //  No children. Use self as phantom replacement and unlink.
    // 如果 p 的颜色是黑色，则执行自平衡
    if (p.color == BLACK)
        fixAfterDeletion(p);
    // 删除 p 和其父节点的相互指向
    if (p.parent != null) {
        // 如果 p 是父节点的左子节点，则置空父节点的左子节点
        if (p == p.parent.left)
            p.parent.left = null;
        // 如果 p 是父节点的右子节点，则置空父节点的右子节点
        else if (p == p.parent.right)
            p.parent.right = null;
        // 置空 p 对父节点的指向
        p.parent = null;
    }
}

}

static TreeMap.Entry successor(Entry t) { // 如果 t 为空，则返回 null if (t == null) return null; // 如果 t 的右子树非空，则取右子树的最小值 else if (t.right != null) { // 先取出根节点 Entry p = t.right; // 再取该根节点的做子树的最小值，即不断遍历左节点 while (p.left != null) p = p.left; return p; } else { // 如果 t 的右子树为空

    // 先获得 t 的父节点
    Entry<K,V> p = t.parent;
    // 不断向上遍历父节点，直到子节点 ch 不是父节点 p 的右子节点
    Entry<K,V> ch = t;
    // 继续遍历的条件，必须是子节点 ch 是父节点 p 的右子节点
    while (p != null && ch == p.right) {
        ch = p;
        p = p.parent;
    }
    return p;
}

}

<a name="KG6vT"></a>
# 查找接近的元素

- 在 NavigableMap 中，定义了四个查找接近的元素
- lowerEntry(K key) 方法，小于 key 的节点
- floorEntry(K key) 方法，小于等于 key 的节点
- higherEntry(K key) 方法，大于 key 的节点
- ceilingEntry(K key) 方法，大于等于 key 的节点
```java
// 是加强版的二叉树查找，在找不到 key 的情况下，找到比 key 大且最接近的节点
public Map.Entry<K,V> ceilingEntry(K key) {
    return exportEntry(getCeilingEntry(key));
}

static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
    return (e == null) ? null :
    new AbstractMap.SimpleImmutableEntry<>(e);
}

final Entry<K,V> getCeilingEntry(K key) {
    Entry<K,V> p = root;
    // 循环二叉查找遍历红黑树
    while (p != null) {
        int cmp = compare(key, p.key);
        // 当前节点比 key 大，则遍历左子树，这样缩小节点的值
        if (cmp < 0) {
            // 如果有左子树，则遍历左子树
            if (p.left != null)
                p = p.left;
            else
                // 直接返回该节点
                return p;
        } else if (cmp > 0) {
            // 当前节点比 key 小，则遍历右子树，这样放大节点的值
            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;
            }
        } else
            // 相等，直接返回 p
            return p;
    }
    return null;
}


public Map.Entry<K,V> higherEntry(K key) {
    return exportEntry(getHigherEntry(key));
}
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;
}

public Map.Entry<K,V> ceilingEntry(K key) {
    return exportEntry(getCeilingEntry(key));
}

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 {
                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 p;
    }
    return null;
}

final Entry<K,V> getLowerEntry(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 (p.left != null) {
                p = p.left;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}
// 所有查找的思路一致，就不写注释了


// 在一些场景下，我们并不需要返回 Entry 节点，只需要返回符合条件的 key 即可。所以有了对应的如下四个方法
public K lowerKey(K key) {
    return keyOrNull(getLowerEntry(key));
}

public K floorKey(K key) {
    return keyOrNull(getFloorEntry(key));
}

public K ceilingKey(K key) {
    return keyOrNull(getCeilingEntry(key));
}

public K higherKey(K key) {
    return keyOrNull(getHigherEntry(key));
}

static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
    return (e == null) ? null : e.key;
}

获得首尾的元素

// firstEntry
public Map.Entry<K,V> firstEntry() {
    return exportEntry(getFirstEntry());
}

final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    // 循环，不断遍历到左子节点，直到没有左子节点
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}

public Map.Entry<K,V> pollFirstEntry() {
    //  获得首个 Entry 节点
    Entry<K,V> p = getFirstEntry();
    Map.Entry<K,V> result = exportEntry(p);
    if (p != null)
        // 如果存在，则进行删除。
        deleteEntry(p);
    return result;
}

public K firstKey() {
    return key(getFirstEntry());
}

static <K> K key(Entry<K,?> e) {
    if (e==null)
        throw new NoSuchElementException();
    return e.key;
}
public Map.Entry<K,V> lastEntry() {
    return exportEntry(getLastEntry());
}

// 一直遍历右子树
final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}

// 移除最后的元素
public Map.Entry<K,V> pollLastEntry() {
    Entry<K,V> p = getLastEntry();
    Map.Entry<K,V> result = exportEntry(p);
    if (p != null)
        deleteEntry(p);
    return result;
}

containsValue方法

public boolean containsValue(Object value) {
    // // 获得首个 Entry 节点
    for (Entry<K,V> e = getFirstEntry(); 
         // 遍历到没有下一个节点
         e != null; 
         // 通过中序遍历，获得下一个节点
         e = successor(e))
        // 判断值是否相等
        if (valEquals(value, e.value))
            return true;
    return false;
}

clear方法

public void clear() {
    modCount++;
    size = 0;
    root = null;
}

获取迭代器

好多好多迭代器 ```java Iterator keyIterator() { return new KeyIterator(getFirstEntry()); // 获得的是首个元素 }

Iterator descendingKeyIterator() { return new DescendingKeyIterator(getLastEntry()); // 获得的是尾部元素 }

abstract class PrivateEntryIterator implements Iterator {

/**
 * 下一个节点
 */
Entry<K,V> next;
/**
 * 最后返回的节点
 */
Entry<K,V> lastReturned;
/**
 * 当前的修改次数
 */
int expectedModCount;

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

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

final Entry<K,V> nextEntry() { // 获得下一个 Entry 节点
    // 记录当前节点
    Entry<K,V> e = next;
    // 如果没有下一个，抛出 NoSuchElementException 异常
    if (e == null)
        throw new NoSuchElementException();
    // 如果发生了修改，抛出 ConcurrentModificationException 异常
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    // 获得 e 的后继节点，赋值给 next
    next = successor(e);
    // 记录最后返回的节点
    lastReturned = e;
    // 返回当前节点
    return e;
}

final Entry<K,V> prevEntry() { // 获得前一个 Entry 节点
    // 记录当前节点
    Entry<K,V> e = next;
    // 如果没有下一个，抛出 NoSuchElementException 异常
    if (e == null)
        throw new NoSuchElementException();
    // 如果发生了修改，抛出 ConcurrentModificationException 异常
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    // 获得 e 的前继节点，赋值给 next
    next = predecessor(e);
    // 记录最后返回的节点
    lastReturned = e;
    // 返回当前节点
    return e;
}

public void remove() { // 删除节点
    // 如果当前返回的节点不存在，则抛出 IllegalStateException 异常
    if (lastReturned == null)
        throw new IllegalStateException();
    // 如果发生了修改，抛出 ConcurrentModificationException 异常
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    // deleted entries are replaced by their successors
    // 在 lastReturned 左右节点都存在的时候，实际在 deleteEntry 方法中，是将后继节点替换到 lastReturned 中
    // 因此，next 需要指向 lastReturned
    if (lastReturned.left != null && lastReturned.right != null)
        next = lastReturned;
    // 删除节点
    deleteEntry(lastReturned);
    // 记录新的修改次数
    expectedModCount = modCount;
    // 置空 lastReturned
    lastReturned = null;
}

}

// 和 successor(Entry t) 方法，是一样的思路 static Entry predecessor(Entry t) { // 如果 t 为空，则返回 null if (t == null) return null; // 如果 t 的左子树非空，则取左子树的最大值 else if (t.left != null) { Entry p = t.left; while (p.right != null) p = p.right; return p; // 如果 t 的左子树为空 } else { // 先获得 t 的父节点 Entry p = t.parent; // 不断向上遍历父节点，直到子节点 ch 不是父节点 p 的左子节点 Entry ch = t; while (p != null // 还有父节点 && ch == p.left) { // 继续遍历的条件，必须是子节点 ch 是父节点 p 的左子节点 ch = p; p = p.parent; } return p; } }

// Key 正序 final class KeyIterator extends PrivateEntryIterator {

KeyIterator(Entry<K,V> first) {
    super(first);
}

// 实现 next 方法，实现正序
public K next() {
    return nextEntry().key;
}

} // Key 倒序迭代器 final class DescendingKeyIterator extends PrivateEntryIterator {

DescendingKeyIterator(Entry<K,V> first) {
    super(first);
}

// 实现 next 方法，实现倒序
public K next() {
    return prevEntry().key;
}

// 重写 remove 方法，因为在 deleteEntry 方法中，在 lastReturned 左右节点都存在的时候，是将后继节点替换到 lastReturned 中。
// 而这个逻辑，对于倒序遍历，没有影响。
public void remove() {
    // 如果当前返回的节点不存在，则抛出 IllegalStateException 异常
    if (lastReturned == null)
        throw new IllegalStateException();
    // 如果发生了修改，抛出 ConcurrentModificationException 异常
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    // 删除节点
    deleteEntry(lastReturned);
    // 置空 lastReturned
    lastReturned = null;
    // 记录新的修改次数
    expectedModCount = modCount;
}

}

// Entry 的正序迭代器。 final class EntryIterator extends PrivateEntryIterator> {

EntryIterator(Entry<K,V> first) {
    super(first);
}

// 实现 next 方法，实现正序
public Map.Entry<K,V> next() {
    return nextEntry();
}

}

// value 的正序迭代器 // TreeMap.java

final class ValueIterator extends PrivateEntryIterator {

ValueIterator(Entry<K,V> first) {
    super(first);
}

// 实现 next 方法，实现正序
public V next() {
    return nextEntry().value;
}

}

<a name="UOI6y"></a>
# 转换成集合
```java
// keySet 

/**
 * 正序的 KeySet 缓存对象
 */
private transient KeySet<K> navigableKeySet;

public Set<K> keySet() {
    return navigableKeySet();
}

public NavigableSet<K> navigableKeySet() {
    KeySet<K> nks = navigableKeySet;
    return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
}

/**
 * 倒序的 NavigableMap 缓存对象
 */
private transient NavigableMap<K,V> descendingMap;

public NavigableSet<K> descendingKeySet() {
    return descendingMap().navigableKeySet();
}

public NavigableMap<K, V> descendingMap() {
    NavigableMap<K, V> km = descendingMap;
    return (km != null) ? km :
    (descendingMap = new DescendingSubMap<>(this,
                                            true, null, true,
                                            true, null, true));
}

// values 方法
public Collection<V> values() {
    Collection<V> vs = values;
    if (vs == null) {
        vs = new Values();
        values = vs; // values 缓存，来自 AbstractMap 的属性
    }
    return vs;
}

// entrySet
/**
 * Entry 缓存集合
 */
private transient EntrySet entrySet;

public Set<Map.Entry<K,V>> entrySet() {
    EntrySet es = entrySet;
    return (es != null) ? es : (entrySet = new EntrySet());
}

查找范围的元素 TODO

自行查看源码，或者参见Java-Review中的讲解
平时用的很少

https://gitee.com/icanci/Java-Review/blob/master/Java%E5%9F%BA%E7%A1%80%E7%AF%87/Java-%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6-TreeMap.md#16-%E6%9F%A5%E6%89%BE%E8%8C%83%E5%9B%B4%E7%9A%84%E5%85%83%E7%B4%A0

参考和推荐文章

Java-Review：https://gitee.com/icanci/Java-Review
TreeMap源码解析：https://www.pdai.tech/md/java/collection/java-map-TreeMap&TreeSet.html

Base-Java

🎉 Map-TreeMap