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