红黑树复杂度_红黑树复杂度分析

我画了 20 张图，给女朋友讲清楚红黑树
　　作者：CJW

　　红黑树是一种常见的自平衡二叉查找树，常用于关联数组、字典，在各种语言的底层实现中被广泛应用，Java的TreeMap和TreeSet就是基于红黑树实现的。本篇分享将为读者讲解红黑树的定义、创建和用途。

　　一.红黑树的定义

　　每个节点或者是黑色，或者是红色。根节点是黑色。每个叶子节点是黑色。如果一个节点是红色的，则它的子节点必须是黑色的从任意一个节点到叶子节点，经过的黑色节点是一样的。

　　这段关于 红黑树 的描述来源于 《算法导论》，你看完这段话可能一脸懵逼。本文希望能够由浅入深地、渐进式地引导读者了解红黑树，因此我们会先从红黑树的意义说起，为什么我们需要一棵红黑树。

　　二. 平衡二叉查找树

　　我们以这样一个数组为例 [42，37，18，12，11，6，5] 构建一棵二叉搜索树，由于数组中任意一点都可以作为二叉搜索树的根节点，因此这棵二叉搜索树并不唯一，我们来看一个极端的例子（以42作为根节点，顺序插入元素）

　　在这个例子中，二叉搜索树退化成了链表，搜索的时间复杂度为 O(n)，失去了作为一棵二叉搜索树的意义。

　　为了让二叉搜索树不至于太“倾斜”，我们需要构建一棵 平衡二叉搜索树。

　　可以看出，平衡二叉搜索树的搜索时间复杂度为O(logn)，避免了因为随机选取根节点构建二叉搜索树而可能造成的退化成链表的情况。下面再抄一段平衡二叉搜索树的官方定义：

　　平衡二叉查找树：简称平衡二叉树。是由前苏联的数学家 Adelse-Velskil和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。它具有如下几个性质： 性质1. 可以是空树。 性质2 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1

　　（如果读者还不清楚平衡二叉搜索树的概念，可以先查阅前文 动画：什么是平衡二叉树，本文不再详细介绍平衡二叉搜索树）

　　三. 2-3树

　　经过上面的例子，我们可以知道，构建一棵平衡的二叉搜索树的关键在于选取“正确”的根节点，那么我们如何在每次构建平衡二叉搜索树时都能选取合适的根节点呢，这里就要用到另一种重要的树：2-3树（读作二三树），2-3树和红黑树是等价的，理解2-3树对理解红黑树以及B类树都有很大的帮助。

　　2-3树的基本概念

　　所谓2-3树，即满足二叉搜索树的性质，且节点可以存放一个元素或者两个元素，每个节点有两个或三个孩子的树。性质1：满足二叉搜索树的性质性质2： 节点可以存放一个或两个元素性质3： 每个节点有两个或三个子节点

　　2-3树本质上也是一棵搜索树，和二叉搜索树的区别在于，2-3的节点可能存放 2 个元素，而且每个节点可能拥有 3 个子节点。2-3树存在以下两种节点：2-节点（存在两个子节点）和3-节点（存在3个子节点）

　　2-3树的创建

　　下面我们来看如何创建一棵2-3树，创建2-3树的规则如下：

　　规则1. 加入新节点时，不会往空的位置添加节点，而是添加到最后一个叶子节点上 规则2. 四节点可以被分解三个2-节点组成的树，并且分解后新树的根节点需要向上和父节点融合

　　我们依然使用上面的示例数组[42，37，18，12，11，6，5]，依然使用顺序插入的方式来构建2-3树，看看是否会出现退化成链表的情况。

　　我们可以注意到，在创建2-3树的每一步中，整棵树始终保持平衡。

　　既然2-3树已经能够保持自平衡，为什么我们还需要一棵红黑树呢，这是因为 2-3树这种每个节点储存1~2个元素以及拆分节点向上融合的性质不便于代码操作，因此我们希望通过一些规则，将2-3树转换成二叉树，且转换后的二叉树依然能保持平衡性。

　　2-3树和红黑树的等价性

　　本小节我们以一棵2-3树为例，将其从2-3树转换成为一棵红黑树，从而学习了解2-3树和红黑树的转换规则，并体会2-3树和红黑树之间的等价性。

　　对于2-3树中的2-节点来说，本身就和二叉搜索树的节点无异，可以直接转换为红黑树的一个黑节点，但是对于3-节点来说，我们需要进行一点小转换： 将3-节点拆开，成为一棵树，并且3-节点的左元素作为右元素的子树 将原来的左元素标记为红色（表示红色节点与其父节点在2-3树中曾是平级的关系）

　　我们来转换一棵复杂点的2-3树，根据上边的两条转换规则，我们将2-节点直接转换为黑色节点，将3-节点拆成一棵子树，并给左元素标上红色，这个过程应该不难理解，另外我们可以注意到，由于红色节点是由3-节点拆分而来，因此所有的红色节点都只会出现在左子树上。

　　四. 红黑树的性质和复杂度分析

　　红黑树基本性质分析

　　在完成了2-3树到红黑树的转换之后，我们重新审视红黑树的五条性质：

　　(1) 每个节点或者是黑色，或者是红色

　　这是红黑树的定义，没什么好说的。

　　(2) 根节点是黑色

　　根节点要么对应2-3树的2-节点或者3-节点，而这两者的根节点都是黑色的，因而根节点必然是黑色。从上图2-3树节点和红黑树节点对应关系就能很容易看出来

　　(3) 每个叶子节点是黑色

　　注意，这里的叶子是指的为空的叶子节点，上图的红黑树的完整形式应该是这样的：

　　(4) 如果一个节点是红色的，则它的子节点必须是黑色的

　　由于红黑树的每个节点都由2-3树转换而来，红色节点连接的节点必然是一个2-节点或者3-节点，而无论是2-节点还是3-节点，其根节点都是黑色的，因此红色节点的子节点必然是黑色的

　　(5) 从任意一个节点到叶子节点，经过的黑色节点是一样多的

　　这是红黑树最重要的一条性质，也是红黑树的价值所在。由于红黑树是由2-3树转换而来，因此每一个黑色节点必然对应2-3树的某个2-节点或者3-节点，因此红黑树的黑节点也能拥有2-3树的平衡性。如果对这条性质还不够理解，可以对着上文2-3树和红黑树的转换图再理解理解。

　　红黑树时间复杂度分析

　　网上有很多使用数学归纳法来计算红黑树时间复杂度的证明了，这里就不再赘述。我们可以简单思考一下，对于一棵普通的平衡二叉搜索树来说，它的搜索时间复杂度为O(logn)，而作为红黑树，存在着最坏的情况，也就是查找的过程中，经过的节点全都是原来2-3树里的3-节点，导致路径延长两倍，时间复杂度为O(2logn)，由于时间复杂度的计算可以忽略系数，因此红黑树的搜索时间复杂度依然是O(logn)，当然，由于这个系数的存在，在实际使用中，红黑树会比普通的平衡二叉树（AVL树）搜索效率要低一些。

　　既然红黑树的效率比AVL树的效率低，那么红黑树的优势体现在哪呢？事实上，红黑树的优势体现在它的插入和删除操作上，红黑树的插入和删除相较于AVL树的性能会高一些，在后续红黑树的创建章节中，读者应该能够体会到红黑树在调整树平衡操作上的优势。

　　五. 红黑树的创建

　　上文中我们讲解了如何由2-3树转换一棵红黑树，下面我们就来看看如何不经过2-3树直接创建一棵红黑树，毕竟我们写代码的时候不能先创建一棵2-3树再转化成红黑树吧。我们回想一下2-3树的创建规则：

　　规则1. 加入新节点时，不会往空的位置添加节点，而是添加到最后一个叶子节点上 规则2. 四节点可以被分解三个2-节点组成的树，并且分解后新树的根节点需要向上和父节点融合

　　简单来说，2-3树的创建分为「融合」和「拆分」两步，为了实现这两步，我们需要在创建二叉树的基础操作上增加另外几个操作，分别是： 保持根节点黑色 左旋转 右旋转 颜色翻转

　　保持根节点黑色和左旋转

　　由于我们往2-3树插入节点时做的都是融合，因此新加入的节点和原位置的节点是平级关系，所以我们往红黑树里增加节点的时候，增加的都是红色节点。

　　我们插入第一个红色节点42，哦吼，第一步就与红黑树的性质2「根节点是黑色」冲突，为了解决这种冲突，我们将根节点变成黑色。

　　下面我们继续插入节点37，同样的，新插入的节点都为红色

　　这里我们要思考一下，如果我们颠倒顺序，先插入 37 再插入 42 呢，是直接把 42 加到 37 的右子树上么，这显然是错误的，因为在前边2-3树转红黑树的过程中，我们已经了解到，所有的红色节点都只会出现在左子树上，因此我们需要进行左旋转，将节点的位置和颜色旋转过来。

　　上面是两个独立的节点，如果节点拥有左右子树，在旋转后仍然能满足二叉搜索树的性质吗，我们需要推广到一般情形。

　　我们来看一个例子：

　　经过以上几步，我们就完成了一般情形下的左旋转，我们可以对应地写几句伪代码，这里把 37 称作node，42 称作 target

　　颜色翻转

　　上一小节我们介绍了左旋转的情形，其实左旋转的情形就对应着2-3树中生成3-节点的情形，也就是从2-节点到3-节点这一步，那么从3-节点到4-节点，再到拆分4-节点的这一步又对应红黑树的什么操作呢，我们来看一个简单的例子。

　　我们以一棵已经拥有两个节点的红黑树为例，现在这一红一黑两个节点就对应了2-3树的3-节点[37 42]，我们加入新的红色节点 66 ，节点 66 按照二叉搜索树的原则，暂时加在节点 42 的右子树上。

　　之前我们说过，红色节点表示该节点与其父节点在2-3树中是平级关系，也就是说这种左右子节点都是红色节点的情况其实对应了2-3树中临时的4-节点。当然，我们知道红色的节点是只能出现在左子树上，所以我们需要进行一些变形。

　　我们应该如何把这棵临时的不规范的红黑树转换成一棵正确的红黑树呢，回想2-3树拆分4-节点的过程：4-节点被拆分为3个2-节点，拆分后的子树的根节点向上融合。由于2-节点对应着红黑树中的黑色节点，因此我们直接把左右子树上的37和66直接翻转为黑色，此即颜色翻转。由于根节点还需要向上融合，因此我们把根节点再标记为红色（相当于加入新节点）

　　我们写两句代码，毕竟这些翻来覆去的操作不是给人看的，是给机器看的。

　　代码非常简单，就是把根节点变成红色，左右子元素变成黑色。当然只有像上图这种树结构（根节点黑色而左右子元素红色）才适用这种颜色翻转。

　　右旋转

　　我们刚才插入了节点66，66比42大，因此被加入到了节点42的右子树上，然后我们使用颜色翻转就完成了转换。然而节点并不总是被添加到右子树上，比如说插入节点12，12小于37，因此节点12被加入到37的左子树上：

　　对于这种情况，我们需要进行右旋转，我们直接以一般情况来讲解：

　　经过以上几步，我们就完成了一般情形下的右旋转，我们可以对应地写几句伪代码，这里把 37 称作target，42 称作 node。

　　其他情况

　　我们通过颜色翻转和右旋转，解决了往3-节点添加节点的两种情况，分别是大于b节点情况，小于a节点的情况，那么如果插入的节点大于 a 而小于 b 呢。

　　对于上图的第三种情况，我们需要结合左旋转、右旋转、颜色翻转等子过程来调整成为一棵正确的红黑树，下面以[37 40 42]作为例子：

　　流程总结

　　我们总结一下以上三种情形，会发现其实红黑树插入节点不过五种形式

　　1. 插入到一个2-节点，且节点小于该2-节点

　　2. 插入到一个2-节点，且节点大于该2-节点

　　3. 插入到一个3-节点，且插入节点小于3-节点的两个节点

　　4. 插入到一个3-节点，且插入节点大于3-节点的两个节点

　　5. 插入到一个3-节点，且插入节点在3-节点的两个节点之间

　　其实这五种形式都可以用一个逻辑链条来表示，我们回顾一下6.4里，插入的节点小于a大于b的转换过程，出于通用性，我把具体数字隐去了。

　　我们发现，这个流程已经包含了以上五种情况，如果我们插入的节点大于a也大于b，那么我们可以直接跳到第四步，然后进行颜色翻转；如果我们插入的节点小于a也小于b，那么跳到第三步；如果插入节点在ab之间，那么就对应第二步。

　　有了这个逻辑流程，我们的代码一下子清晰起来，我们只需要通过几个条件判断，就能描述红黑树所有旋转方式，下面我们来写一段代码：

　　到这里，我们就实现了红黑树的所有平衡操作，从这个过程中，我们还能得出一个重要结论，即红黑树任何不平衡，都能在3次旋转内得到解决，这也就是红黑树相较AVL树的优势所在。

　　六. 红黑树和AVL树的比较

　　1. AVL树比红黑树更为平衡，其搜索效率也好于红黑树, 经过我们之前的分析可以知道, 红黑树在最坏的情况下搜索时间复杂度为2logn，大于AVL树的logn。AVL树是严格平衡，红黑树只能达到“黑平衡”，即从任意节点出发到叶子节点经过的黑节点数量相同，但经过的红色节点数量不确定，最差的情况下，经过的红色节点和黑色节点一样多。

　　2. 红黑树增删节点的性能优于AVL树，当我们往红黑树增加节点或删除节点引起红黑树不平衡，我们只需要最多三次旋转就能解决，而相同条件下，AVL树的旋转次数要多于红黑树，因此红黑树在增删节点上相较于AVL树更优

　　七.总结

　　最后做个概括，红黑树是以牺牲部分搜索性能换取增删性能的折中方案，用非严格的平衡，换取旋转次数的减少。在实际使用中，如果所维护的树需要频繁增删节点，红黑树会更加合适，反之，则适合AVL树。我画了 20 张图，给女朋友讲清楚红黑树