算力 | 手写红黑树

关注
发布于: 2020 年 12 月 03 日
前言红黑树对于大多数人来说，似乎都是一场噩梦。当然这里并不讨论红黑树在实际开发过程中究竟能否被运用上，但至少，不懂红黑树始终是你在数据结构上的一块短板。大部分情况下，我在interview候选人时，提问并不会太刁钻，重点是考察候选人分析问题与解决问题的实际能力，当然，如果候选人对算法比较自信时，我便会考察ConcurrentHashMap的相关实现，毕竟ConcurrentHashMap中涉及到的相关数据结构&算法（比如：散列表、链表、二叉排序树、红黑树），线程安全（比如：Java8之前的分段锁，之后的Sync+CAS）等，足以探测出候选人的大致算力。本文，我会侧重于红黑树的具体实现过程而非概念。
前世 | 二叉查找树（BS-Tree）在正式讲解红黑树之前，我们有必要首先回顾下二叉查找树，因为从本质上来讲，红黑树演变自二叉查找树，只是相对而言，前者引入了一些特定的平衡规则，以便于降低时间复杂度。我们都知道，二叉查找树CRD的平均时间复杂度是O(logn)，但在最坏情况下，CRD时间复杂度将会升级为O(n)。
﻿
就查找算法而言，性能相对较好的当属二分查找（时间复杂度为O(log2n)），但二分查找算法在实际使用过程中却存在一定的局限，并不太适用于数据频繁发生变动的场景，因此，在这种情况下，二叉查找树或许是一个不错的替代方案。相对于普通的二叉树而言，二叉查找树是一种相对特殊的二叉树，因为节点会根据值的大小有序分布在根节点的左/右两边，也就是说，小于根节点值的节点会被分布在左边，反之右边，并且根节点的左/右子树同样也是一颗二叉查找树，如图1所示。
图1 二叉排序树
二叉排序树的整体实现并不复杂，仅节点的删除操作略显繁琐。接下来，我先从节点的插入操作开始讲起。二叉排序树的特点相信大家已经非常明确了，小于根节点值的节点会被分布在其左边，反之右边；也就是说，当根节点不为空时，待插入节点首先需要和根节点进行比较，如果小于根节点的值，就同其左子树按照相同的规则继续比较，直至最终找到叶子节点后，再将待插入节点作为新的叶子节点挂靠在原叶子节点的左边或右边即可。
二叉排序树插入实现，示例1-1。
void insert(int key, T value) {
    var nn = new Node<>(key, value);
    if (Objects.isNull(root)) {
        root = nn;
    } else {
        insert(root, root.parent, nn);
    }
}
void insert(Node<T> n1, Node<T> n2, Node<T> n3) {
    if (Objects.isNull(n1)) {
        if (n3.key < n2.key) {
            n2.left = n3;
        } else {
            n2.right = n3;
        }
        n3.parent = n2;
    } else {
        insert(n3.key < n1.key ? n1.left : n1.right, n1, n3);
    }
}
﻿
以图1中的数据分布为基础，如果新增一个节点11，那么目标节点将会作为节点40的左子树，如图2所示。
图2 执行插入操作后的数据分布
节点的遍历操作，通常情况下有前序、中序，以及后序等3种方式。由于二叉排序树中的数据分布相对有序，因此，如果希望数据按照升序的方式执行输出，则可以采用中序遍历。
中序遍历实现，示例1-2。
void inOrder() {
    inOrder(root);
}
void inOrder(Node<T> n) {
    if (Objects.nonNull(n)) {
        inOrder(n.left);
        System.out.println(n);
        inOrder(n.right);
    }
}
﻿
在讲解二叉排序树的删除操作之前，我们首先需要实现目标节点查找和后继节点查找等2项查找操作。目标节点的查找，首先需要拿比较值与根节点进行匹配，如果值相等就返回，反之根据二叉排序树的数据分布规则继续与左/右子树依次匹配，直至最终值相等时才返回目标节点。
二叉排序树获取当前节点实现，示例1-3。
Node<T> getNode(int key) {
    if (Objects.nonNull(root)) {
        return root.key == key ? root : getNode(key, root);
    }
    return null;
}
Node<T> getNode(int key, Node<T> n) {
    if (Objects.nonNull(n)) {
        if (key == n.key) {
            return n;
        }
        return getNode(key, key < n.key ? n.left : n.right);
    }
    return null;
}
﻿
而所谓后继节点，实质上指的就是同时存在左/右子树的待删除节点的继承节点。之所以说二叉排序树的删除操作略显繁琐，是因为我们需要考虑4种可能存在的删除情况，如下所示：
待删除节点并不存在任何子树；
待删除节点仅存在左子树；
待删除节点仅存在右子树；
待删除节点同时存在左/右子树。
﻿
当待删除节点并不存在任何子树时，我们直接删除目标节点即可；如果待删除节点仅存在左子树的情况下，则需要将其parent.left或parent.right指向待删除节点的左子树，存在右子树的情况下执行相反操作；如果待删除节点同时存在左/右子树时，就需要先找到后继节点，然后将待删除节点的parent.left或parent.right指向后继节点，并由后继节点继承待删除节点的左/右子树。
关于后继节点的查找方式，通常有2种，如下所示：
左子树的最右节点；
右子树的最左节点。
﻿
本文选择以“左子树的最右节点”为后继节点的查找方式，示例1-4。
Node<T> getSucceedNode(int key) {
    var n = getNode(key);
    if (Objects.nonNull(n)) {
        return getSucceedNode(n.left);//如果左子树不存在任何右节点，后继节点就是左子树
    }
    return null;
}
Node<T> getSucceedNode(Node<T> n) {
    if (Objects.nonNull(n)) {
        var sn = getSucceedNode(n.right);
        return Objects.nonNull(sn) ? sn : n;
    }
    return null;
}
﻿
以图2为例，如果待删除节点为100，那么其后继节点就是60；而如果待删除节点为150，其后继节点就是120，如图3所示。
图3 寻找后继节点
二叉排序树的节点删除操作，示例1-5。
boolean delete(int key) {
    var n = getNode(key);
    if (Objects.nonNull(n)) {
        delete(n);
        return true;
    }
    return false;
}
void delete(Node<T> n) {
    if (Objects.nonNull(n.left) && Objects.nonNull(n.right)) {
        var sn = getSucceedNode(n.key);
        n.key = sn.key;
        n.value = sn.value;
        n.left.parent = n;
        n.right.parent = n;
        delete(sn);//递归删除后继节点
        return;
    } else {
        if (Objects.isNull(n.parent)) {
            root = Objects.nonNull(n.left) ? n.left : n.right;
            root.parent = null;
        } else {
            var c = Objects.nonNull(n.left) ? n.left : n.right;
            if (n.parent.left == n) {
                n.parent.left = c;
            } else {
                n.parent.right = c;
            }
            if (Objects.nonNull(c)) {
                c.parent = n.parent;
            }
        }
    }
}
﻿
至此，二叉排序树的基本实现就完成了，关于求最大值、最小值、节点数、树高等相关实现由于篇幅有限，本文就不再过多进行讲解。
今生 | 红黑树（RB-Tree）在本文的开篇我曾提及过，二叉查找树CRD的平均时间复杂度是O(logn)，但在最坏情况下，CRD时间复杂度会降为O(n)。这是因为二叉查找树的时间复杂度与节点的插入顺序存在直接关系，如果节点的插入顺序为100、200、300、400、500，那么这颗二叉排序树就会完全退化成一个链表，失去了原本高效的CRD性能，如图5所示。
图5 退化成链表的二叉排序树
介于链表在最坏情况下访问和搜索的时间复杂度会降为O(n)，因此ConcurrentHashMap在链表元素个数>=8时，会将其转换成一颗红黑树，以便于提升检索效率和缩短RT时间，源码示例1-7。
if (binCount != 0) {
    if (binCount >= TREEIFY_THRESHOLD) //TREEIFY_THRESHOLD 缺省值为8
        treeifyBin(tab, i);
        if (!added)
            return val;
        break;
}
﻿
红黑树的性能究竟如何？尽管红黑树和二叉查找树的CRD平均时间复杂度都是O(logn)，但在最坏情况下，前者的CRD时间复杂度仍然可以保持在O(logn)水平，而不会下降到O(n)，如图6所示。
图6 常见数据结构的时间复杂度和空间复杂度
红黑树之所以能够在最坏的情况下将CRD时间复杂度控制在O(logn)，与它自身的4项平衡规则密切相关：
每个节点，只能是红色或黑色；
根节点必须是黑色；
如果节点为红色，那么它的左/右子树必须是黑色；
任意路径的黑高相同。
﻿
图7 红黑树黑高
由于红黑树会在每一次写入操作完成后对目标节点进行着色、左/右旋转处理来让其始终保持平衡，因此，从逻辑上来说（黑高），红黑树中任意节点的左/右子树高度始终是保持一致的，不会因为节点的不平衡而导致二叉树退化成链表，如图7所示。
节点插入修正红黑树之所以“复杂”，我认为是大部分人的空间想象力存在短板所导致的。本文，我会尽量用最清晰和路径最短的示例来进行说明，以便于大家快速理解和上手。
﻿
假设节点插入成功后，接下来要做的事情就是对目标节点进行重新着色和左/右旋转处理，单边（待插入节点的父节点在祖父节点的左边/右边）一共存在3种插入修正情况，如下所示：
插入节点存在uncle节点，且uncle节点为RED；
插入节点不存在uncle节点，或uncle节点为BLACK，且在parent的左边；
插入节点不存在uncle节点，或uncle节点为BLACK，且在parent的右边。
﻿
图8 第1种插入修正处理
我们先从第1种情况开始讲起，如图8所示。假设节点200(BLACK)同时拥有左子树100(RED)和右子树300(RED)，那么当插入节点50(RED)时（新插入节点缺省都为RED），根据二叉排序树的数据分布规则，节点50会作为节点100的左子树，但这却违背了红黑树的规则，RED节点并不能包含相同颜色的子树。因此，在这种情况下，我们只需要将节点100和300着色为BLACK，节点200着色为RED即可（如果是根节点，最终仍然会被修正为BLACK）。
第1种节点插入修正情况实现，示例1-8。
void i_fixup(Node<T> n) {
    if (root == n) {
        root.color = Color.BLACK;//如果是根节点，着色为BLACK并退出
        return;
    }
    if (Objects.isNull(n) || n.parent.color == Color.BLACK) {
        return;//如果parent.color为BLACK则退出
    } else {
            var parent = n.parent;
            var gandfather = parent.parent;
        if (gandfather.left == parent) {
            var uncle = gandfather.right;
            if (Objects.nonNull(uncle) && uncle.color == Color.RED) {
                parent.color = Color.BLACK;
                uncle.color = Color.BLACK;
                gandfather.color = Color.RED;
                i_fixup(gandfather);//将gandfather节点进行递归修正
            }
        }
    }
}
﻿
在此大家需要注意，如果待插入节点的父节点为BLACK时，则无需进行任何修正处理，直接插入即可，因为这并不会破坏红黑树的平衡。
图9 第2种插入修正处理
第2种情况，如图9所示。节点200(BLACK)仅包含左子树100(RED)，那么当插入节点50(RED)时，根据二叉排序树的数据分布规则，节点50会作为节点100的左子树，但这却违背了红黑树的规则，因此我们需要将节点100着色为BLACK，节点200着色为RED，然后再对节点200进行右旋后即可恢复这颗红黑树的平衡。
第2种节点插入修正情况实现，示例1-9。
if (Objects.nonNull(uncle) && uncle.color == Color.RED) {
    //省略情况1相关实现逻辑
} else {
    if (parent.left == n) {//情况2相关实现逻辑
        parent.color = Color.BLACK;
        gandfather.color = Color.RED;
        rightRotate(gandfather);
    }
}
﻿
针对目标节点进行右旋时，如果其左子树不存在右子树，那么当右旋结束后，原父节点会变为其左子树的右子树；如果其左子树存在右子树，那么则由原父节点继承为左子树即可，如图10所示。
图10 节点右旋示例
红黑树的节点右旋实现，示例1-10。
void rightRotate(Node<T> n) {
    var left = n.left;
    n.left = left.right;
    if (Objects.nonNull(left.right)) {
        left.right.parent = n;
    }
    left.right = n;
    reset(left, n);//重设引用关系
}
﻿
左旋操作同理，如果其右子树不存在左子树，那么当左旋结束后，原父节点会变为其右子树的左子树；如果其右子树存在左子树，那么则由原父节点继承为右子树即可。
图10 第3种插入修正情况
第3种情况，如图10所示。节点200(BLACK)仅包含左子树100(RED)，当插入节点150(RED)时，根据二叉排序树的数据分布规则，由于目标节点>100，因此将会作为节点100的右子树，但这同样也违背了红黑树的规则，因此我们需要对其进行修正处理。在此，我们并不必急于对节点200和100着色，而是先将节点100左旋，待旋转结束后，节点100会作为节点150的左子树，然后再将节点100作为入参递归调用修正函数i_fixup()进入到情况2的逻辑处理上。
第3种节点插入修正情况实现，示例1-11。
if (Objects.nonNull(uncle) && uncle.color == Color.RED) {
    //省略情况1实现逻辑
} else {
    if (parent.left == n) {
       //省略情况2实现逻辑
    } else {//情况3实现逻辑
        leftRotate(parent);
        i_fixup(parent);
    }
}
﻿
在此大家需要注意，如果待插入节点的父节点在祖父节点的右边，只需调换顺序处理即可，本文就不再过多进行讲解了。至此，关于红黑树的节点插入修正基本实现就完成了。
节点删除修正看到这里，或许很多同学都会认为红黑树的修正处理太麻烦，确实，左/右旋转加上着色处理确实容易把人绕晕，但这仅仅只是开始。相对于插入修正而言，红黑树的删除修正单边（继承节点在父节点的左边/右边）一共存在4种情况，如下所示：
brother节点为RED；
brother节点为BLACK，且左/右子树为null或BLACK；
brother节点为BLACK，且存在颜色为RED的左子树；
brother节点为BLACK，且存在颜色为RED的右子树。
﻿
在此大家需要注意，触发删除修正存在2个前提，首先是被删除的目标节点必须是BLACK（因为删除RED节点并不会对红黑树的平衡产生影响，无需修正，可直接删除），其次，必须存在brother节点。那有没有一种可能，即被删除的节点不存在任何brother节点，或仅包含一个颜色为RED的brother节点？答案是否定的，因为这违背了红黑树的规则，黑高不相等，所以被删除节点必定会存在直接或间接颜色为BLACK的brother节点。
图11 第1种和第2种删除修正情况
如图11所示。假如我们删除节点200(BLACK)后，红黑树的平衡就一定会被打破，因为根节点左/右子树的黑高并不相等，且由于brother节点300为RED满足于第1种删除修正情况，因此，首先需要将其父节点100(BLACK)着色为RED，brother节点着色为BLACK，然后再左旋父节点100，待左旋结束后，原父节点100会作为其右子树300的左子树。由于产生左旋后brother节点会被重新指向为节点250，此时同时也满足于第2种修正情况，因此我们还需要将节点100着色为BLACK，其右子树着色为RED。
第1种和第2种节点删除修正情况实现，示例1-12。
void d_fixup(Node<T> n1, Node<T> n2) {
    Node<T> bro = null;
    while ((Objects.isNull(n1) || n1.color == Color.BLACK) && root != n1) {
        if (n2.left == n1) {//情况1相关实现逻辑
            bro = n2.right;
            if (bro.color == Color.RED) {
                bro.color = Color.BLACK;
                n2.color = Color.RED;
                leftRotate(n2);
                bro = n2.right;
            }
            //情况2相关实现逻辑
            if ((Objects.isNull(bro.left) || bro.left.color == Color.BLACK) && (Objects.isNull(bro.right) || bro.right.color == Color.BLACK)) {
                if (n2.color == Color.RED) {
                    n2.color = Color.BLACK;
                    bro.color = Color.RED;
                    break;
                } else {
                    bro.color = Color.RED;
                    n1 = n2;
                    n2 = n1.parent;
                }
            }
        }
    }
}
﻿
如图12所示。当我们删除节点100(BLACK)后，红黑树的平衡就被打破了，由于brother节点300为BLACK，且左子树为RED，正好满足于第3种删除修正情况，因此，我们首先需要将brother着色为父节点200(BLACK)的颜色，父节点在非BLACK的情况下着色为BLACK，然后再右旋brother节点，待右旋结束后，brother节点会作为其原左子树250的右子树。此时红黑树仍然非平衡，因此我们还需要左旋父节点200，让这颗红黑树恢复平衡。
图12 第3种删除修正情况
第3种节点删除修正情况实现，示例1-13。
if (n2.left == n1) {
    bro = n2.right;
    if (bro.color == Color.RED) {
        //省略情况1相关实现逻辑
    }
    if ((Objects.isNull(bro.left) || bro.left.color == Color.BLACK) && (Objects.isNull(bro.right) || bro.right.color == Color.BLACK)) {
        //省略情况2相关实现逻辑
    } else {
        if (Objects.nonNull(bro.left) && bro.left.color == Color.RED) {//情况3相关实现逻辑
            bro.left.color = n2.color;
            n2.color = Color.BLACK;
            rightRotate(bro);
            leftRotate(n2);
        } 
        break;
    }
} 
﻿
如图13所示。当我们删除节点100(BLACK)后，红黑树的平衡就被打破了，由于brother节点300为BLACK，且右子树为RED，正好满足于第4种删除修正情况，因此，我们首先需要先将brother着色为父节点200(BLACK)的颜色，父节点在非BLACK的情况下着色为BLACK，brother节点的右子树着色为BLACK，然后再左旋父节点200即可。
图13 第4种删除修正情况
第4种节点删除修正情况实现，示例1-14。
if (n2.left == n1) {
    bro = n2.right;
    if (bro.color == Color.RED) {
				//省略情况1相关实现逻辑
    }
    if ((Objects.isNull(bro.left) || bro.left.color == Color.BLACK) && (Objects.isNull(bro.right) || bro.right.color == Color.BLACK)) {
        //省略情况2相关实现逻辑
    } else {
        if (Objects.nonNull(bro.left) && bro.left.color == Color.RED) {
            //省略情况3相关实现逻辑
        } else if (Objects.nonNull(bro.right) && bro.right.color == Color.RED) {//情况4相关实现逻辑
            bro.color = n2.color;
            n2.color = Color.BLACK;
            bro.right.color = Color.BLACK;
            leftRotate(n2);
        }
        break;
    }
}
﻿
在此大家需要注意，如果继承节点在父节点的右边，只需调换顺序处理即可，本文就不再过多进行讲解了。至此，本文内容全部结束。如果在阅读过程中有任何疑问，欢迎在评论区留言参与讨论。
项目地址红黑树实现，https://github.com/gaoxianglong/algorithm/blob/master/src/main/java/RBTree.java
﻿
推荐文章：
硬核系列 | 深入剖析字节码增强
硬核系列 | 深入剖析 Java 协程
白玉试毒 | 灰度架构设计方案
新时代背景下的 Java 语法特性
剖析 Java15 新语法特性
看门狗 | 分布式锁架构设计方案 -01
看门狗 | 分布式锁架构设计方案 -02
码字不易，欢迎转发