Java TreeMap红黑树原理，源码解析

红黑树简介

红黑树是一种自平衡排序二叉树，树中每个节点的值，都大于或等于在它的左子树中的所有节点的值，并且小于或等于在它的右子树中的所有节点的值，这确保红黑树运行时可以快速地在树中查找和定位的所需节点。

对于 TreeMap 而言，由于它底层采用一棵“红黑树”来保存集合中的 Entry，这意味这 TreeMap 添加元素、取出元素的性能都比 HashMap 低：当 TreeMap 添加元素时，需要通过循环找到新增 Entry 的插入位置，因此比较耗性能；当从 TreeMap 中取出元素时，需要通过循环才能找到合适的 Entry，也比较耗性能。但 TreeMap、TreeSet 比 HashMap、HashSet 的优势在于：TreeMap 中的所有 Entry 总是按 key 根据指定排序规则保持有序状态，TreeSet 中所有元素总是根据指定排序规则保持有序状态。

为了理解 TreeMap 的底层实现，必须先介绍排序二叉树和红黑树这两种数据结构。其中红黑树又是一种特殊的排序二叉树。

排序二叉树是一种特殊结构的二叉树，可以非常方便地对树中所有节点进行排序和检索。

排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
它的左、右子树也分别为排序二叉树。

图 1 显示了一棵排序二叉树：

对排序二叉树，若按中序遍历就可以得到由小到大的有序序列。如图 1 所示二叉树，中序遍历得：

{2，3，4，8，9，9，10，13，15，18}

创建排序二叉树的步骤，也就是不断地向排序二叉树添加节点的过程，向排序二叉树添加节点的步骤如下：

以根节点当前节点开始搜索。
拿新节点的值和当前节点的值比较。
如果新节点的值更大，则以当前节点的右子节点作为新的当前节点；如果新节点的值更小，则以当前节点的左子节点作为新的当前节点。
重复 2、3 两个步骤，直到搜索到合适的叶子节点为止。
将新节点添加为第 4 步找到的叶子节点的子节点；如果新节点更大，则添加为右子节点；否则添加为左子节点。

TreeMap的红黑树

数据结构

1 红黑树的节点颜色--红色

private static final boolean RED = false;

2 红黑树的节点颜色--黑色

private static final boolean BLACK = true;

3 “红黑树的节点”对应的类。

static final class Entry<K,V> implements Map.Entry<K,V> { ... }

Entry包含了6个部分内容：key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)
Entry节点根据key进行排序，Entry节点包含的内容为value。

TreeMap添加节点源码

我们来分析 TreeMap 添加节点（TreeMap 中使用 Entry 内部类代表节点）的实现，TreeMap 集合的 put(K key, V value) 方法实现了将 Entry 放入排序二叉树中，下面是该方法的源代码：

public V put(K key, V value) 
 { 
    // 先以 t 保存链表的 root 节点
    Entry<K,V> t = root; 
    // 如果 t==null，表明是一个空链表，即该 TreeMap 里没有任何 Entry 
    if (t == null) 
    { 
        // 将新的 key-value 创建一个 Entry，并将该 Entry 作为 root 
        root = new Entry<K,V>(key, value, null); 
        // 设置该 Map 集合的 size 为 1，代表包含一个 Entry 
        size = 1; 
        // 记录修改次数为 1 
        modCount++; 
        return null; 
    } 
    int cmp; 
    Entry<K,V> parent; 
    Comparator<? super K> cpr = comparator; 
    // 如果比较器 cpr 不为 null，即表明采用定制排序
    if (cpr != null) 
    { 
        do { 
            // 使用 parent 上次循环后的 t 所引用的 Entry 
            parent = t; 
            // 拿新插入 key 和 t 的 key 进行比较
            cmp = cpr.compare(key, t.key); 
            // 如果新插入的 key 小于 t 的 key，t 等于 t 的左边节点
            if (cmp < 0) 
                t = t.left; 
            // 如果新插入的 key 大于 t 的 key，t 等于 t 的右边节点
            else if (cmp > 0) 
                t = t.right; 
            // 如果两个 key 相等，新的 value 覆盖原有的 value，
            // 并返回原有的 value 
            else 
                return t.setValue(value); 
        } while (t != null); 
    } 
    else 
    { 
        if (key == null) 
            throw new NullPointerException(); 
        Comparable<? super K> k = (Comparable<? super K>) key; 
        do { 
            // 使用 parent 上次循环后的 t 所引用的 Entry 
            parent = t; 
            // 拿新插入 key 和 t 的 key 进行比较
            cmp = k.compareTo(t.key); 
            // 如果新插入的 key 小于 t 的 key，t 等于 t 的左边节点
            if (cmp < 0) 
                t = t.left; 
            // 如果新插入的 key 大于 t 的 key，t 等于 t 的右边节点
            else if (cmp > 0) 
                t = t.right; 
            // 如果两个 key 相等，新的 value 覆盖原有的 value，
            // 并返回原有的 value 
            else 
                return t.setValue(value); 
        } while (t != null); 
    } 
    // 将新插入的节点作为 parent 节点的子节点
    Entry<K,V> e = new Entry<K,V>(key, value, parent); 
    // 如果新插入 key 小于 parent 的 key，则 e 作为 parent 的左子节点
    if (cmp < 0) 
        parent.left = e; 
    // 如果新插入 key 小于 parent 的 key，则 e 作为 parent 的右子节点
    else 
        parent.right = e; 
    // 修复红黑树
    fixAfterInsertion(e);                               // ①
    size++; 
    modCount++; 
    return null; 
 }

上面程序中代码就是实现“排序二叉树”的关键算法，每当程序希望添加新节点时：系统总是从树的根节点开始比较 —— 即将根节点当成当前节点，如果新增节点大于当前节点、并且当前节点的右子节点存在，则以右子节点作为当前节点；如果新增节点小于当前节点、并且当前节点的左子节点存在，则以左子节点作为当前节点；如果新增节点等于当前节点，则用新增节点覆盖当前节点，并结束循环 —— 直到找到某个节点的左、右子节点不存在，将新节点添加该节点的子节点 —— 如果新节点比该节点大，则添加为右子节点；如果新节点比该节点小，则添加为左子节点。

TreeMap删除节点源码

private void deleteEntry(Entry<K,V> p) 
 { 
    modCount++; 
    size--; 
    // 如果被删除节点的左子树、右子树都不为空
    if (p.left != null && p.right != null) 
    { 
        // 用 p 节点的中序后继节点代替 p 节点
        Entry<K,V> s = successor (p); 
        p.key = s.key; 
        p.value = s.value; 
        p = s; 
    } 
    // 如果 p 节点的左节点存在，replacement 代表左节点；否则代表右节点。
    Entry<K,V> replacement = (p.left != null ? p.left : p.right); 
    if (replacement != null) 
    { 
        replacement.parent = p.parent; 
        // 如果 p 没有父节点，则 replacemment 变成父节点
        if (p.parent == null) 
            root = replacement; 
        // 如果 p 节点是其父节点的左子节点
        else if (p == p.parent.left) 
            p.parent.left  = replacement; 
        // 如果 p 节点是其父节点的右子节点
        else 
            p.parent.right = replacement; 
        p.left = p.right = p.parent = null; 
        // 修复红黑树
        if (p.color == BLACK) 
            fixAfterDeletion(replacement);       // ①
    } 
    // 如果 p 节点没有父节点
    else if (p.parent == null) 
    { 
        root = null; 
    } 
    else 
    { 
        if (p.color == BLACK) 
            // 修复红黑树
            fixAfterDeletion(p);                 // ②
        if (p.parent != null) 
        { 
            // 如果 p 是其父节点的左子节点
            if (p == p.parent.left) 
                p.parent.left = null; 
            // 如果 p 是其父节点的右子节点
            else if (p == p.parent.right) 
                p.parent.right = null; 
            p.parent = null; 
        } 
    } 
 }

TreeMap 删除节点采用下图所示右边的情形进行维护——也就是用被删除节点的右子树中最小节点与被删节点交换的方式进行维护。

当程序从排序二叉树中删除一个节点之后，为了让它依然保持为排序二叉树，程序必须对该排序二叉树进行维护。维护可分为如下几种情况：
（1）被删除的节点是叶子节点，则只需将它从其父节点中删除即可。
（2）被删除节点 p 只有左子树，将 p 的左子树 pL 添加成 p 的父节点的左子树即可；被删除节点 p 只有右子树，将 p 的右子树 pR 添加成 p 的父节点的右子树即可。
（3）若被删除节点 p 的左、右子树均非空，有两种做法：
1. 将 pL 设为 p 的父节点 q 的左或右子节点（取决于 p 是其父节点 q 的左、右子节点），将 pR 设为 p 节点的中序前趋节点 s 的右子节点（s 是 pL 最右下的节点，也就是 pL 子树中最大的节点）。
2. 以 p 节点的中序前趋或后继替代 p 所指节点，然后再从原排序二叉树中删去中序前趋或后继节点即可。（也就是用大于 p 的最小节点或小于 p 的最大节点代替 p 节点即可）。

Java红黑树总结

1：每个节点要么是红色，要么是黑色。
2：根节点永远是黑色的。
3：所有的叶节点都是空节点（即 null），并且是黑色的。
4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点）
5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。