从TreeMap到红黑树

Java中常用的TreeMap类是基于红黑树Red-Black Tree实现的，本文大量参考了CarpenterLee的《史上最清晰的红黑树讲解》。

红黑树简介

红黑树又称红-黑二叉树，它首先是一颗二叉树，它具体二叉树所有的特性。同时红黑树更是一棵 自平衡 的 二叉查找树 。

我们知道一颗基本的二叉排序树都需要满足一个基本性质————即 树中的任何节点的值大于它的左子节点，且小于它的右子节点 。按照这个基本性质使得树的检索效率大大提高。我们知道在生成二叉树的过程是非常容易失衡的，最坏的情况就是一边倒（只有右/左子树），这样势必会导致二叉树的检索效率大大降低（O(n)），所以为了维持二叉树的平衡，大牛们提出了各种实现的算法，如： AVL、SBT、 伸展树、TREAP、红黑树等等。

红黑树的特点

红黑树顾名思义就是节点是红色或者黑色的「平衡二叉树」（并不完全是），它通过颜色的约束来维持着二叉树的「平衡」。对于一棵有效的红黑树二叉树而言有如下规则：

1.每个节点要么是红色，要么是黑色。
2.根节点必须是黑色。
3.红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
4.对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的，是近似平衡的二叉搜索树。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的。所以红黑树是复杂而高效的，其检索效率 O(logn) ，最大深度为 2log(n+1)

红黑树有两个重要性质：

1、红节点的孩子节点不能是红节点；
2、从根到前端节点的任意一条路径上的黑节点数目一样多。

这两条性质确保该树的高度为 logN ，所以是平衡树。

与AVL的区别

1、红黑树放弃了追求完全平衡，追求大致平衡。对于AVL树，任何一个节点的两个子树高度差不会超过1；对于红黑树，则是不会相差两倍以上。在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多两次、删除最多三次旋转就能达到平衡，实现起来也更为简单。
2、平衡二叉树追求「绝对平衡」，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知（这个有争议）。
3、平衡二叉树适合用于插入与删除次数比较少，但查找多的情况。红黑树在二叉查找树的基础上增加了着色和相关的性质使得红黑树「相对平衡」，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(logn)。所以红黑树适用于搜索、插入、删除操作较多的情况。

下面引用知乎帖子信陵君魏无忌的回答：

红黑树中红节点的父亲和孩子必须是黑节点，且从根到叶子节点经过的黑节点个数相同，因此红黑树最小深度是路径上只有黑节点，最大深度是路径上红黑节点相互间隔，因此最大深度≤最小深度的两倍，最大深度是2*log2（n+1）。因此，红黑树的查询效率比avl树低，但是红黑树的删除效率比avl树高，更适合大量数据增加删除的场景，而且红黑树在增加删除数据的时候只需要常数次旋转操作，更适合数据持久化的场景。

关于二叉查找树和二叉平衡树请参考这篇博文。

红黑树的应用

红黑树的应用：

1、在C++的STL中，地图和集都是用红黑树实现的；
2、著名的Linux的进程调度完全公平调度程序，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间；
3、IO多路复用的 epoll 的的实现采用红黑树组织管理的 sockfd ，以支持快速的增删改查；
4、Nginx的中用红黑树管理定时器，因为红黑树是有序的，可以很快的得到距离当前最小的定时器；
5、Java中的 TreeMap 中的实现，如可以实现一致性哈希的环。
TreeMap基础

TreeMap 底层通过红黑树（Red-Black Tree）实现，也就意味着 containsKey()， get() ， put() ， remove() 都有着 log(n) 的时间复杂度。

TreeMap 的定义如下：

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap继承 AbstractMap ，实现 NavigableMap 、 Cloneable 、 Serializable 三个接口。

其中 AbstractMap 表明 TreeMap 为一个 Map 即支持 key-value 的集合， NavigableMap 则意味着它支持一系列的「导航」方法，具备 针对给定搜索目标返回最接近匹配项 的导航方法。

前文说到当查找树的结构发生改变时，红黑树的条件可能被破坏，需要通过调整使得查找树重新满足红黑树的条件。调整可以分为两类：

一类是颜色调整，即改变某个节点的颜色；
另一类是结构调整，即改变检索树的结构关系。

结构调整过程包含两个基本操作：左旋（RotateLeft）和右旋（RotateRight）。

基本结构

它包含了如下几个重要的属性：

    //比较器，因为TreeMap是有序的，通过Comparator接口我们可以对TreeMap的内部排序进行精密的控制
    private final Comparator<? super K> comparator;
    //TreeMap红-黑节点，为TreeMap的内部类
    private transient Entry<K,V> root = null;
    //容器大小
    private transient int size = 0;
    //TreeMap修改次数
    private transient int modCount = 0;
    //红黑树的节点颜色--红色
    private static final boolean RED = false;
    //红黑树的节点颜色--黑色
    private static final boolean BLACK = true;

对于叶子节点 Entry 是TreeMap的内部类，可见默认的颜色是黑色：

/**
 * Node in the Tree.  Doubles as a means to pass key-value pairs back to
 * user (see Map.Entry).
 */

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;

    /**
     * Make a new cell with given key, value, and parent, and with
     * {@code null} child links, and BLACK color.
     */
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
    .....

左旋

左旋的过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。 left_rotate

private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        // 获取P的右子节点
        Entry<K,V> r = p.right;
        // 将R的左子树设置为P的右子树
        p.right = r.left;
        // 若R的左子树不为空，则将P设置为R左子树的父亲
        if (r.left != null)
            r.left.parent = p;
        // 将P的父亲设置R的父亲
        r.parent = p.parent;
        // 如果P的父亲为空，则将R设置为跟节点
        if (p.parent == null)
            root = r;
        // 如果P为其父节点的左子树，则将R设置为P父节点左子树
        else if (p.parent.left == p)
            p.parent.left = r;
        // 否则R设置为P的父节点的右子树
        else
            p.parent.right = r;
        // 将P设置为R的左子树
        r.left = p;
        // 将R设置为P的父节点
        p.parent = r;
    }
}

左旋就是将节点的右支往左拉，右子节点变成父节点，并把晋升之后多余的左子节点出让给降级节点的右子节点

右旋

右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。

right_rotate TreeMap中右旋代码如下：

private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        // 将L设置为P的左子树
        Entry<K,V> l = p.left;
        // 将L的右子树设置为P的左子树
        p.left = l.right;
        // 若L的右子树不为空，则将P设置L的右子树的父节点
        if (l.right != null) 
            l.right.parent = p;
        // 将P的父节点设置为L的父节点
        l.parent = p.parent;
        // 如果P的父节点为空，则将L设置根节点
        if (p.parent == null)
            root = l;
        // 若P为其父节点的右子树，则将L设置为P的父节点的右子树
        else if (p.parent.right == p)
            p.parent.right = l;
        // 否则将L设置为P的父节点的左子树
        else 
            p.parent.left = l;
        // 将P设置为L的右子树
        l.right = p;
        // 将L设置为P的父节点
        p.parent = l;
    }
}

右旋就是反过来，将节点的左支往右拉，左子节点变成了父节点，并把晋升之后多余的右子节点出让给降级节点的左子节点。

着色

private static <K,V> void setColor(Entry<K,V> p, boolean c) {
    if (p != null)
        p.color = c;
}

TreeMap方法剖析

get方法

get(Object key) 方法根据指定的key值返回对应的value，该方法调用了 getEntry(Object key) 得到相应的entry，然后返回entry .value。因此 getEntry() 是算法的核心。算法思想是根据key的自然顺序或者比较器顺序对二叉查找树进行查找，直到找到满足 k.compareTo(p.key) == 0 的entry。 TreeMap.getEntry

具体代码如下：

//getEntry()方法
final Entry<K,V> getEntry(Object key) {
    ......
    if (key == null)//不允许key值为null
        throw new NullPointerException();
    Comparable<? super K> k = (Comparable<? super K>) key; // 使用元素的自然顺序
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0) // 向左找
            p = p.left;
        else if (cmp > 0) // 向右找
            p = p.right;
        else
            return p;
    }
    return null;
}

put方法

put(K key, V value) 方法是将指定的key-value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于 ` getEntry()` 方法；如果没有找到则会在红黑树中插入新的entry，如果插入之后破坏了红黑树的约束，还需要进行调整（旋转&改变某些节点的颜色）。

具体代码如下：

public V put(K key, V value) {
   // 用t表示二叉树的当前节点
    Entry<K,V> t = root;
    // t为null表示一个空树，即TreeMap中没有任何元素，直接插入
    if (t == null) {
        // 比较key值
        compare(key, key); // type (and possibly null) check
        // 将新的key-value键值对创建为一个Entry节点，并将该节点赋予给root
        root = new Entry<>(key, value, null);
        // 容器的size = 1，表示TreeMap集合中存在一个元素
        size = 1;
        // 修改次数 + 1
        modCount++;
        return null;
    }
    int cmp;     // cmp表示key排序的返回结果
    Entry<K,V> parent;   // 父节点，第一次赋值为root
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;    //指定的排序算法
    // 如果cpr不为空，则采用既定的排序算法进行创建TreeMap集合
    if (cpr != null) {
        do {
            parent = t;      // parent指向上次循环后的t
            // 用比较器比较新增节点的key和当前节点key的大小
            cmp = cpr.compare(key, t.key);
            // cmp返回值小于0，表示新增节点的key小于当前节点的key，则以当前节点的左子节点作为新的当前节点
            if (cmp < 0)
                t = t.left;
            // cmp返回值大于0，表示新增节点的key大于当前节点的key，则以当前节点的右子节点作为新的当前节点
            else if (cmp > 0)
                t = t.right;
            // cmp返回值等于0，表示两个key值相等，则新值覆盖旧值，并返回新值
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 如果cpr为空，则采用默认的排序算法进行创建TreeMap集合
    else {
        if (key == null)     //key值为空抛出异常
            throw new NullPointerException();
        // 下面处理过程和上面一样
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key); // 使用key自身的比较器完成比较
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    // t为null
    // 将新增节点当做parent的子节点
    Entry<K,V> e = new Entry<>(key, value, parent);
    // 如果新增节点的key小于parent的key，则当做左子节点
    if (cmp < 0)
        parent.left = e;
    // 如果新增节点的key大于parent的key，则当做右子节点
    else
        parent.right = e;
    
    // 上面已经完成了排序二叉树的的构建，将新增节点插入该树中的合适位置
    // 下面fixAfterInsertion()方法就是对这棵树进行调整、平衡
    fixAfterInsertion(e);
    // TreeMap元素数量 + 1
    size++;
    // TreeMap容器修改次数 + 1
    modCount++;
    return null;
}

上述代码的插入部分并不难理解：首先在红黑树上找到合适的位置，然后创建新的entry并插入（当然，新插入的节点一定是树的叶子）。难点是调整函数 fixAfterInsertion() ，前面已经说过，调整往往需要：1.改变某些节点的颜色；2.对某些节点进行旋转。

调整函数 fixAfterInsertion() 的具体代码如下，其中用到了上文中提到的 rotateLeft() 和 rotateRight() 函数。通过代码我们能够看到，情况2其实是落在情况3内的。情况4～情况6跟前三种情况是对称的，因此图解中并没有画出后三种情况，读者可以参考代码自行理解。

//红黑树调整函数fixAfterInsertion()
private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED; //新增节点的颜色为红色
    //循环 直到 x不是根节点，且x的父节点不为红色
    while (x != null && x != root && x.parent.color == RED) {
        // 如果X的父节点（P）是其父节点的父节点（G）的左节点
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            // 获取X的叔节点(U)
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) { // 如果y为null，则视为BLACK
                setColor(parentOf(x), BLACK);              // 情况1
                setColor(y, BLACK);                        // 情况1
                setColor(parentOf(parentOf(x)), RED);      // 情况1
                x = parentOf(parentOf(x));                 // 情况1
                // 因为父亲和叔父都是黑色，保证从爷爷向下的路径此时满足路径上的黑色数目相同
                // 可能G节点的父节点也是红色，这个时候我们需要将G节点当做新增节点递归处理
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);                       // 情况2
                    rotateLeft(x);                         // 情况2
                    // 将父节点左旋，注意旋转后父节点x变成了之前右孩子的左孩子
                }
                // 这里的x的父节点其实是上面旋转前的x
                setColor(parentOf(x), BLACK);              // 情况3
                setColor(parentOf(parentOf(x)), RED);      // 情况3
                rotateRight(parentOf(parentOf(x)));        // 情况3
                // 将爷爷几点进行右旋转，因为它为红色，而它的左孩子为黑色，是旋转后的根节点
            }
        } else { // 和if中的逻辑对称
            // 获取X的叔节点(U)
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);              // 情况4
                setColor(y, BLACK);                        // 情况4
                setColor(parentOf(parentOf(x)), RED);      // 情况4
                x = parentOf(parentOf(x));                 // 情况4
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);                       // 情况5
                    rotateRight(x);                        // 情况5
                }
                setColor(parentOf(x), BLACK);              // 情况6
                setColor(parentOf(parentOf(x)), RED);      // 情况6
                rotateLeft(parentOf(parentOf(x)));         // 情况6
            }
        }
    }
    // 将根节点强制设置为黑色
    root.color = BLACK; 
}

它的思想是把「多出来」的红色往上一层推，确保下面层的红黑性质，最后推到根以后，如果依然违反性质1，则可以直接把根由红改黑即可，就相当于把这「多出来」的红色推到树以外的节点去了。

put

successor方法

对于一棵二叉查找树，给定节点t，其后继（树中比大于t的元素中最小的那个元素）可以通过如下方式找到：

t的右子树不空，则t的后继是其右子树中最小的那个元素。

t的右孩子为空，则t的后继是其第一个向左走的节点的祖先。

TreeMap 中寻找节点后继的代码如下：

// 寻找节点后继函数successor()
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
  if (t == null)
      return null;
  else if (t.right != null) {// 1. t的右子树不空，则t的后继是其右子树中最小的那个元素
      Entry<K,V> p = t.right;
      while (p.left != null)
          p = p.left;
      return p;
  } else {// 2. t的右孩子为空，则t的后继是其第一个向左走的祖先
      Entry<K,V> p = t.parent;
      Entry<K,V> ch = t;
      while (p != null && ch == p.right) { // 向上遍历，直到ch为p的左孩子
          ch = p;
          p = p.parent;
      }
      return p; // 返回parent
  }
}

predecessor方法

对于一棵二叉查找树，给定节点t，其前驱（树中比小于t的元素中最大的那个元素）可以通过如下方式找到：

t的左子树不空，则t的前驱是其左子树中最大的那个元素。
t的左孩子为空，则t的前驱是其第一个向右走的节点的祖先。

对应的图可以对比successor部分的图看，分别找45的前驱和35的前驱。

TreeMap 中寻找节点前驱的代码如下：

// 寻找节点前驱函数successor()
static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.left != null) {// 1. t的左子树不空，则t的前驱是其有子树中最大的那个元素
        Entry<K,V> p = t.left;
        while (p.right != null)
            p = p.right;
        return p;
    } else {// 2. t的左孩子为空，则t的前驱是其第一个向右走的祖先
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.left) { // 向上遍历，直到ch为p的右孩子
            ch = p;
            p = p.parent;
        }
        return p; // 返回parent
    }
}

remove方法

remove(Object key)的作用是删除key值对应的entry，该方法首先通过上文中提到的getEntry(Object key)方法找到key值对应的entry，然后调用deleteEntry(Entry<K,V> entry)删除对应的entry。由于删除操作会改变红黑树的结构，有可能破坏红黑树的约束条件，因此有可能要进行调整。

getEntry()函数前面已经讲解过，这里重点放deleteEntry()上，该函数删除指定的entry并在红黑树的约束被破坏时进行调用fixAfterDeletion(Entry<K,V> x)进行调整。

由于红黑树是一棵增强版的二叉查找树，红黑树的删除操作跟普通二叉查找树的删除操作也就非常相似，唯一的区别是红黑树在节点删除之后可能需要进行调整。现在考虑一棵普通二叉查找树的删除过程，可以简单分为两种情况：

删除点p的左右子树都为空，或者只有一棵子树非空。
删除点p的左右子树都非空。

对于上述情况1，处理起来比较简单，直接将p删除（左右子树都为空时），或者用非空子树替代p（只有一棵子树非空时）；对于情况2，可以用p的后继s（树中大于x的最小的那个元素）代替p，然后使用情况1删除s（此时s一定满足情况1，可以画画看）。

基于以上逻辑，红黑树的节点删除函数deleteEntry()代码如下：

// 红黑树entry删除函数deleteEntry()
private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;
    if (p.left != null && p.right != null) {// 2. 删除点p的左右子树都非空。
        Entry<K,V> s = successor(p);// 后继
        p.key = s.key;
        p.value = s.value;
        p = s;
    }
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    if (replacement != null) {// 1. 删除点p只有一棵子树非空。
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;
        p.left = p.right = p.parent = null;
        if (p.color == BLACK)
            fixAfterDeletion(replacement);// 调整
    } else if (p.parent == null) {
        root = null;
    } else { // 1. 删除点p的左右子树都为空
        if (p.color == BLACK)
            fixAfterDeletion(p);// 调整
        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

上述代码中占据大量代码行的，是用来修改父子节点间引用关系的代码，其逻辑并不难理解。下面着重讲解删除后调整函数 fixAfterDeletion() 。首先请思考一下，删除了哪些点才会导致调整？只有删除点是 BLACK 的时候，才会触发调整函数，因为删除 RED 节点不会破坏红黑树的任何约束，而删除 BLACK 节点会破坏规则4。

跟上文中讲过的 fixAfterInsertion() 函数一样，这里也要分成若干种情况。记住，无论有多少情况，具体的调整操作只有两种：1.改变某些节点的颜色，2.对某些节点进行旋转。

remove

删除节点时先要找到顶替的节点，如果删去的节点是黑色则破坏了性质2，也需要调整。调整的思想也同前面类似，把这个黑色赋予顶替节点，则顶替节点相当于有两重黑色，然后将它的两重黑色向上推，一直推到根，再从根推到外面去了。

private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            Entry<K,V> sib = rightOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);                   // 情况1
                setColor(parentOf(x), RED);             // 情况1
                rotateLeft(parentOf(x));                // 情况1
                sib = rightOf(parentOf(x));             // 情况1
            }
            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);                     // 情况2
                x = parentOf(x);                        // 情况2
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);       // 情况3
                    setColor(sib, RED);                 // 情况3
                    rotateRight(sib);                   // 情况3
                    sib = rightOf(parentOf(x));         // 情况3
                }
                setColor(sib, colorOf(parentOf(x)));    // 情况4
                setColor(parentOf(x), BLACK);           // 情况4
                setColor(rightOf(sib), BLACK);          // 情况4
                rotateLeft(parentOf(x));                // 情况4
                x = root;                               // 情况4
            }
        } else { // 跟前四种情况对称
            Entry<K,V> sib = leftOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);                   // 情况5
                setColor(parentOf(x), RED);             // 情况5
                rotateRight(parentOf(x));               // 情况5
                sib = leftOf(parentOf(x));              // 情况5
            }
            if (colorOf(rightOf(sib)) == BLACK &&
                colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);                     // 情况6
                x = parentOf(x);                        // 情况6
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);      // 情况7
                    setColor(sib, RED);                 // 情况7
                    rotateLeft(sib);                    // 情况7
                    sib = leftOf(parentOf(x));          // 情况7
                }
                setColor(sib, colorOf(parentOf(x)));    // 情况8
                setColor(parentOf(x), BLACK);           // 情况8
                setColor(leftOf(sib), BLACK);           // 情况8
                rotateRight(parentOf(x));               // 情况8
                x = root;                               // 情况8
            }
        }
    }
    setColor(x, BLACK);
}

References

https://www.cnblogs.com/chenssy/p/3746600.html
https://www.cnblogs.com/CarpenterLee/p/5503882.html
https://www.cnblogs.com/CarpenterLee/p/5525688.html
https://blog.csdn.net/qq_25940921/article/details/82183093
https://zhuanlan.zhihu.com/p/31805309
https://www.zhihu.com/question/30527705

本文首次发布于 LiuShuo’s Blog, 转载请保留原文链接.

TreeMap and Red-Black Tree