概述

Java TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序，key大小的评判可以通过其本身的自然顺序(natural ordering)，也可以通过构造时传入的比较器(Comparator)。

TreeMap底层通过红黑树（Red-Black tree）实现，也就意味着containsKey()、get()、put()、remove()都有着log(n)的时间复杂度。其具体算法实现参照了《算法导论》。

出于性能原因，TreeMap是非同步的(not synchronized)，如果需要在多线程环境使用，需要程序员手动同步；
或者通过如下方式将TreeMap包装成(wrapped)同步的：

1
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍。
具体来说，红黑树是满足如下条件的二叉查找树(binary search tree)：

  1. 每个节点要么是红色，要么是黑色。
  2. 根节点必须是黑色
  3. 红色节点不能连续(也即是，红色节点的孩子和父亲都不能是红色)。
  4. 对于每个节点，从该点至null(树尾端)的任何路径，都含有相同个数的黑色节点。

在树的结构发生改变时(插入或者删除操作)，往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的约束条件。

左旋 & 右旋

当查找树的结构发生改变时，红黑树的约束条件可能被破坏，需要通过调整使得查找树重新满足红黑树的约束条件。

调整可以分为两类:
一类是颜色调整，即改变某个节点的颜色；
另一类是结构调整，即改变检索树的结构关系。结构调整过程包含两个基本操作: **左旋(Rotate Left)、右旋(RotateRight)**。

左旋

左旋的过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。

TreeMap中左旋代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//Rotate Left
private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

右旋

右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。

TreeMap中右旋代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//Rotate Right
private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

寻找节点后继