类及成员

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    // 比较器对象
    private final Comparator<? super K> comparator;

    // 根节点
    private transient Entry<K,V> root;

    // 集合大小
    private transient int size = 0;

    // 树结构被修改的次数
    private transient int modCount = 0;

    // 静态内部类用来表示节点类型
    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;     // 键
        V value;   // 值
        Entry<K,V> left;    // 指向左子树的引用（指针）
        Entry<K,V> right;   // 指向右子树的引用（指针）
        Entry<K,V> parent;  // 指向父节点的引用（指针）
        boolean color = BLACK; // 
    }
}

构造方法

public TreeMap() {   // 1,无参构造方法
        comparator = null; // 默认比较机制
    }

    public TreeMap(Comparator<? super K> comparator) { // 2，自定义比较器的构造方法
        this.comparator = comparator;
    }

    public TreeMap(Map<? extends K, ? extends V> m) {  // 3，构造已知Map对象为TreeMap
        comparator = null; // 默认比较机制
        putAll(m);
    }

    public TreeMap(SortedMap<K, ? extends V> m) { // 4，构造已知的SortedMap对象为TreeMap
        comparator = m.comparator(); // 使用已知对象的构造器
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }

put方法

public V put(K key, V value) {
        Entry<K,V> t = root;  // 获取根节点

        // 如果根节点为空，则该元素置为根节点 
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;    // 集合大小为1
            modCount++;  // 结构修改次数自增
            return null;
        }

        int cmp;
        Entry<K,V> parent;
        Comparator<? super K> cpr = comparator;  // 比较器对象

        // 如果比较器对象不为空，也就是自定义了比较器
        if (cpr != null) {   
            do { // 循环比较并确定元素应插入的位置(也就是找到该元素的父节点)
                parent = t;  // t就是root

                // 调用比较器对象的compare()方法，该方法返回一个整数
                cmp = cpr.compare(key, t.key); 
                if (cmp < 0)      // 待插入元素的key"小于"当前位置元素的key，则查询左子树
                    t = t.left;
                else if (cmp > 0) // 待插入元素的key"大于"当前位置元素的key，则查询右子树
                    t = t.right;
                else              // "相等"则替换其value。
                    return t.setValue(value);
            } while (t != null);
        }

        // 如果比较器对象为空，使用默认的比较机制
        else {
            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)       // 待插入元素的key"小于"当前位置元素的key，则查询左子树
                    t = t.left;
                else if (cmp > 0)  // 待插入元素的key"大于"当前位置元素的key，则查询右子树
                    t = t.right;
                else               // "相等"则替换其value。
                    return t.setValue(value);
            } while (t != null);
        }

        Entry<K,V> e = new Entry<>(key, value, parent);  // 根据key找到父节点后新建一个节点
        if (cmp < 0)  // 根据比较的结果来确定放在左子树还是右子树
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;      // 集合大小+1
        modCount++;  // 集合结构被修改次数+1
        return null;
    }

get操作

public V get(Object key) {
     Entry<k,v> p = getEntry(key);
     return (p==null ? null : p.value);
}</k,v>
//get(Object key)通过key获取对应的value，它通过调用getEntry(Object key)获取节点，若节点为null则返回null，否则返回节点的value值。下面是getEntry(Object key)的内容，来看它是怎么寻找节点的。

final Entry<k,v> getEntry(Object key) {
    // 如果有比较器，返回getEntryUsingComparator(Object key)的结果
    if (comparator != null)
        return getEntryUsingComparator(key);
    // 查找的key为null，抛出NullPointerException
    if (key == null)
        throw new NullPointerException();
    // 如果没有比较器，而是实现了可比较接口
    Comparable<!--? super K--> k = (Comparable<!--? super K-->) key;
    // 获取根节点
    Entry<k,v> p = root;
    // 对树进行遍历查找节点
    while (p != null) {
        // 把key和当前节点的key进行比较
        int cmp = k.compareTo(p.key);
        // key小于当前节点的key
        if (cmp < 0)
            // p “移动”到左节点上
            p = p.left;
        // key大于当前节点的key
        else if (cmp > 0)
            // p “移动”到右节点上
p = p.right;
        // key值相等则当前节点就是要找的节点
        else
            // 返回找到的节点
            return p;
        }
    // 没找到则返回null
    return null;
}</k,v></k,v>

删除操作

public V remove(Object key) {
    // 通过getEntry(Object key)获取节点 getEntry(Object key)方法已经在上面介绍过了
    Entry<k, v=""> p = getEntry(key);
 
    // 指定key的节点不存在，返回null
    if (p == null)
        return null;
 
    V oldValue = p.value;  // 获取节点的value
 
    deleteEntry(p); // 删除节点
 
    return oldValue; // 返回节点的内容
}</k,>

private void deleteEntry(Entry<k,v> p) {
// 记录树结构的修改次数
modCount++;
// 记录树中节点的个数
    size--;
 
// p有左右两个孩子的情况  标记①
if (p.left != null && p.right != null) {
        // 获取继承者节点（有两个孩子的情况下，继承者肯定是右孩子或右孩子的最左子孙）
        Entry<k,v> s = successor (p);
        // 使用继承者s替换要被删除的节点p，将继承者的key和value复制到p节点，之后将p指向继承者
        p.key = s.key;
        p.value = s.value;
        p = s;
    } 
 
// Start fixup at replacement node, if it exists.
// 开始修复被移除节点处的树结构
// 如果p有左孩子，取左孩子，否则取右孩子    标记②
    Entry<k,v> replacement = (p.left != null ? p.left : p.right);
    if (replacement != null) {
        // Link replacement to parent
        replacement.parent = p.parent;
        // p节点没有父节点，即p节点是根节点
        if (p.parent == null)
            // 将根节点替换为replacement节点
            root = replacement;
        // p是其父节点的左孩子
        else if (p == p.parent.left)
            // 将p的父节点的left引用指向replacement
            // 这步操作实现了删除p的父节点到p节点的引用
            p.parent.left  = replacement;
        else
            // 如果p是其父节点的右孩子，将父节点的right引用指向replacement
            p.parent.right = replacement;
        // 解除p节点到其左右孩子和父节点的引用
        p.left = p.right = p.parent = null;
        if (p.color == BLACK)
            // 在删除节点后修复红黑树的颜色分配
            fixAfterDeletion(replacement);
} else if (p.parent == null) { 
/* 进入这块代码则说明p节点就是根节点（这块比较难理解，如果标记①处p有左右孩子，则找到的继承节点s是p的一个祖先节点或右孩子或右孩子的最左子孙节点，他们要么有孩子节点，要么有父节点，所以如果进入这块代码，则说明标记①除的p节点没有左右两个孩子。没有左右孩子，则有没有孩子、有一个右孩子、有一个左孩子三种情况，三种情况中只有没有孩子的情况会使标记②的if判断不通过，所以p节点只能是没有孩子，加上这里的判断，p没有父节点，所以p是一个独立节点，也是树种的唯一节点……有点难理解，只能解释到这里了，读者只能结合注释慢慢体会了），所以将根节点设置为null即实现了对该节点的删除 */
        root = null;
} else { /* 标记②的if判断没有通过说明被删除节点没有孩子，或它有两个孩子但它的继承者没有孩子。如果是被删除节点没有孩子，说明p是个叶子节点，则不需要找继承者，直接删除该节点。如果是有两个孩子，那么继承者肯定是右孩子或右孩子的最左子孙 */
        if (p.color == BLACK)
            // 调整树结构
            fixAfterDeletion(p);
        // 这个判断也一定会通过，因为p.parent如果不是null则在上面的else if块中已经被处理
        if (p.parent != null) {
            // p是一个左孩子
            if (p == p.parent.left)
                // 删除父节点对p的引用
                p.parent.left = null;
            else if (p == p.parent.right)// p是一个右孩子
                // 删除父节点对p的引用
                p.parent.right = null;
            // 删除p节点对父节点的引用
            p.parent = null;
        }
    }
}</k,v></k,v></k,v>

clear方法

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

containKey方法

public boolean containsValue(Object value) {
    // 通过e = successor(e)实现对树的遍历
    for (Entry<k,v> e = getFirstEntry(); e != null; e = successor(e))
    // 判断节点值是否和value相等
        if (valEquals(value, e.value))
            return true;
    // 默认返回false
    return false;
}</k,v>

获取Entry

final Entry<k,v> getFirstEntry() {
    Entry<k,v> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}</k,v></k,v>

final Entry<k,v> getLastEntry() {
    Entry<k,v> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}</k,v></k,v>