关于java:TreeMap

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