public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{...}TreeMap 的接口几继承树中，有两个不同凡响的接口：NavigableMap、SortedMap。SortedMap 接口示意它的 key 是有序不能反复的，反对获取头尾 Key-Value 元素，或者更具 key 指定范畴获取子集合等。插入的 key 必须实现 Comparable 或者提供额定的 Comparator，所以 key 不容许为 null，然而 value 能够。NavigablMap 接口继承了 Sorted Map 接口。
如果 key 没有实现 Comparable 或者 Comparator，那么编译的时候会抛出异样。
import java.util.TreeMap;
public class TreeMapDemo {public static void main(String[] args) {TreeMap<Person,Integer> tree = new TreeMap<>();
tree.put(new Person(1,"张三"), 1);
}
}
class Person{
private int age;
private String name;
getter/setter/constructor/toString
}output:
Exception in thread "main" java.lang.ClassCastException: class Person cannot be cast to class java.lang.Comparable (Person is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
at java.base/java.util.TreeMap.compare(TreeMap.java:1291)
at java.base/java.util.TreeMap.put(TreeMap.java:536)
at TreeMapDemo.main(TreeMapDemo.java:6)重写 compareTo 办法：
@Override
public int compareTo(Person o) {
// TODO Auto-generated method stub
return this.getAge() - o.getAge();
}put 办法
public V put(K key, V value) {
// 把 root 节点给 t
Entry<K,V> t = root;
// 如果根节点是 null，那么这棵树是空树，新增的节点就是根节点。if (t == null) {compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
// 结构器放入的比拟器
Comparator<? super K> cpr = comparator;
// 比拟器不为空，那么就优先应用比拟器来进行比拟
if (cpr != null) {
// 比拟 key 值，找到指标地位
do {
// 将以后节点给 parent
parent = t;
// 将比拟后果给 cmp
cmp = cpr.compare(key, t.key);
// 判断插入的 key 和以后节点（t）的大小
if (cmp < 0)
// 如果比以后节点小，当将前节点指向为左子树的根节点
t = t.left;
else if (cmp > 0)
t = t.right;
else
// 如果 key 相等，就将以后的 value 复制替换掉原来的 value
return t.setValue(value);
} while (t != null);
}
// 比拟器为 null 的状况下，应用 Comparable 接口的 compareTo 办法来比拟
else {
// 插入 key 为 null，抛异样
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 对象，并把 parent 对象放入
Entry<K,V> e = new Entry<>(key, value, parent);
// 插入节点
if (cmp < 0)
// 小于 parent，插入左子树
parent.left = e;
else
// 插入右子树
parent.right = e;
// 调整红黑树结构，使其合乎规定
fixAfterInsertion(e);
size++;
modCount++;
return null;
} 不须要调整：
须要调整的状况：
/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
// 默认插入新节点的色彩是红色
x.color = RED;
// 须要进行调整的条件
// 父亲节点色彩为红色
while (x != null && x != root && x.parent.color == RED) {
/* 分状况进行调整
x 示意以后节点，p 示意 parent 节点，u 示意 uncle 节点，g 示意 grandfather 节点
o (g)
/ \
o(p) o(u)
o(x)
*/
// 如上图
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
// y 就是 uncle 节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
// 如果 uncle 节点是红色
if (colorOf(y) == RED) {
// 从新染色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
// uncle 节点是彩色
// 判断以后节点的地位 如图：/*
o (g)
/ \
o(p) o(u)
\
o(x)
*/
if (x == rightOf(parentOf(x))) {x = parentOf(x);
// 左旋
rotateLeft(x);
}
// 从新染色
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {....// 原理雷同}
}
root.color = BLACK;
}private void rotateLeft(Entry<K,V> p) {
// 如果参数节点不是 NIL 节点
if (p != null) {
// 获取 p 节点的右子节点
Entry<K,V> r = p.right;
// 将 r 的左子树设置为 p 的右子树
p.right = r.left;
//，则将 p 设置为 r 左子树的父亲
if (r.left != null)
r.left.parent = p;
// 将 p 的父亲设置为 r 的父亲
r.parent = p.parent;
// 如果 p 的父亲是 null
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
// 将 p 设置为 r 的左子树，将 r 设置为 p 的父亲
r.left = p;
p.parent = r;
}
}