红黑树算法复杂度_完全二叉树和满二叉树图解

深入理解linux中常用高级数据结构之红黑树 　　一、为什么要有红黑树？ 　　二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是 O(logn)。 　　但是，在已经有了性能不错的二叉搜索树，为什么还需要引入红黑树呢？ 　　那是因为，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于 log2n 的情况，从而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到 O(n)。 　　而且，我们希望树的结构具有关联性，即相邻版本之间，比如说第一次插入，和第二次插入时，树的结构不能发生太大变化，应该可以经过O（1）次数就可以变化完成。对于AVL树来说，插入是满足这个条件的，删除却不满足这个条件。 　　要解决这两个问题，我们需要设计一种平衡二叉查找树，也就是今天要讲的红黑树。 　　二、什么是“平衡二叉查找树”？ 　　平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看，上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。

　　平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。最先被发明的平衡二叉查找树是AVL树，它严格符合我刚讲到的平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过 1，是一种高度平衡的二叉查找树。 　　但是很多平衡二叉查找树其实并没有严格符合上面的定义（树中任意一个节点的左右子树的高度相差不能大于 1），比如我们下面要讲的红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。 　　我们学习数据结构和算法是为了应用到实际的开发中的，所以，我觉得没必去死抠定义。对于平衡二叉查找树这个概念，我觉得我们要从这个数据结构的由来，去理解“平衡”的意思。 　　发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。 　　所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。 　　所以，如果我们现在设计一个新的平衡二叉查找树，只要树的高度不比 log2n 大很多（比如树的高度仍然是对数量级的），尽管它不符合我们前面讲的严格的平衡二叉查找树的定义，但我们仍然可以说，这是一个合格的平衡二叉查找树。 　　三、红黑树的定义 　　红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树，我前面说了，它的定义是不严格符合平衡二叉查找树的定义的。那红黑树究竟是怎么定义的呢？ 　　顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：每个结点要么是红的要么是黑的。根结点是黑的。每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；如果一个结点是红的，那么它的两个儿子都是黑的。对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

　　相关视频推荐 　　90分钟了解4种红黑树的Linux内核应用场景 　　定时器设计—红黑树、时间轮、最小堆 　　5种红黑树的用途，从应用到内核场景的优缺点 　　学习地址：c/c++ linux服务器开发/后台架构师 　　需要C/C++ Linux服务器架构师学习资料加qun（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等），免费分享

　　四、为什么说红黑树是“近似平衡”的？ 　　平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。 　　二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是 log2n，所以如果要证明红黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近 log2n 就好了。 　　红黑树与AVL树相似，但提供更快的实时有界最坏情况下的插入和删除性能（分别达到最多两轮和三轮以平衡树），但速度稍慢（但仍为O（log n））查找时间； 　　红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用，如实时应用（real time application）中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为基础模板的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树实现。 　　红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。 　　五、红黑树为什么综合性能好？ 　　在《算法（第4版）》 中说过， 红黑树等价于2-3树, 换句话说，对于每个2-3树，都存在至少一个数据素是同样次序的红黑树。在2-3树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得2-3树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍2-3树的原因，尽管2-3树在实践中不经常使用。 　　其中2-节点 等价于普通平衡二叉树的节点，3-节点 本质上是非平衡性的缓存。 当需要再平衡（rebalance）时，增删操作时，2-节点 与 3-节点间 的 转化会吸收不平衡性，减少旋转次数，使再平衡尽快结束。 在综合条件下，增删操作相当时，数据的随机性强时，3-节点的非平衡性缓冲效果越明显。因此红黑树的综合性能更优。 　　继续追根溯源，红黑树的性能优势，本质上是用空间换时间。 　　六、实现红黑树 　　红黑树的平衡过程：大致过程就是：遇到什么样的节点排布，我们就对应怎么去调整。只要按照这些固定的调整规则来操作，就能将一个非平衡的红黑树调整成平衡的。 　　一棵合格的红黑树需要满足这样几个要求：每个结点要么是红的要么是黑的。根结点是黑的。每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；如果一个结点是红的，那么它的两个儿子都是黑的。对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。 　　在插入、删除节点的过程中，第四、第五点要求可能会被破坏，而我们今天要讲的“平衡调整”，实际上就是要把被破坏的第三、第四点恢复过来。 　　在正式开始之前，我先介绍两个非常重要的操作，左旋（rotate left）、右旋（rotate right）。左旋全称其实是叫围绕某个节点的左旋，那右旋的全称估计你已经猜到了，就叫围绕某个节点的右旋。

　　前面我说了，红黑树的插入、删除操作会破坏红黑树的定义，具体来说就是会破坏红黑树的平衡，所以，我们现在就来看下，红黑树在插入、删除数据之后，如何调整平衡，继续当一棵合格的红黑树的。 　　1、插入操作的平衡调整 　　首先，我们来看插入操作。 　　红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。所以，关于插入操作的平衡调整，有这样两种特殊情况，但是也都非常好处理。如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。 　　除此之外，其他情况都会违背红黑树的定义，于是我们就需要进行调整，调整的过程包含两种基础的操作：左右旋转和改变颜色。 　　红黑树的平衡调整过程是一个迭代的过程。我们把正在处理的节点叫作节点。节点会随着不停地迭代处理，而不断发生变化。最开始的节点就是新插入的节点。 　　新节点插入之后，如果红黑树的平衡被打破，那一般会有下面三种情况。我们只需要根据每种情况的特点，不停地调整，就可以让红黑树继续符合定义，也就是继续保持平衡。 　　我们下面依次来看每种情况的调整过程。提醒你注意下，为了简化描述，我把父节点的兄弟节点叫作叔叔节点，父节点的父节点叫作祖父节点。 　　CASE 1：如果节点是 a，它的叔叔节点 d 是红色，我们就依次执行下面的操作：将节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；将节点 a 的祖父节点 c 的颜色设置成红色；节点变成 a 的祖父节点 c；跳到 CASE 2 或者 CASE 3。

　　CASE 2：如果节点是 a，它的叔叔节点 d 是黑色，节点 a 是其父节点 b 的右子节点，我们就依次执行下面的操作：节点变成节点 a 的父节点 b；围绕新的节点b 左旋；跳到 CASE 3。

　　CASE 3：如果节点是 a，它的叔叔节点 d 是黑色，节点 a 是其父节点 b 的左子节点，我们就依次执行下面的操作：围绕节点 a 的祖父节点 c 右旋；将节点 a 的父节点 b、兄弟节点 c 的颜色互换。调整结束。

　　2、删除操作的平衡调整 　　红黑树插入操作的平衡调整还不是很难，但是它的删除操作的平衡调整相对就要难多了。不过原理都是类似的，我们依旧只需要根据节点与周围节点的排布特点，按照一定的规则去调整就行了。 　　删除操作的平衡调整分为两步，第一步是针对删除节点初步调整。初步调整只是保证整棵红黑树在一个节点删除之后，仍然满足最后一条定义的要求，也就是说，每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；第二步是针对节点进行二次调整，让它满足红黑树的第三条定义，即不存在相邻的两个红色节点。 　　1. 针对删除节点初步调整 　　这里需要注意一下，红黑树的定义中“只包含红色节点和黑色节点”，经过初步调整之后，为了保证满足红黑树定义的最后一条要求，有些节点会被标记成两种颜色，“红 – 黑”或者“黑 – 黑”。如果一个节点被标记为了“黑 – 黑”，那在计算黑色节点个数的时候，要算成两个黑色节点。 　　在下面的讲解中，如果一个节点既可以是红色，也可以是黑色，在画图的时候，我会用一半红色一半黑色来表示。如果一个节点是“红 – 黑”或者“黑 – 黑”，我会用左上角的一个小黑点来表示额外的黑色。 　　CASE 1：如果要删除的节点是 a，它只有一个子节点 b，那我们就依次进行下面的操作：删除节点 a，并且把节点 b 替换到节点 a 的位置，这一部分操作跟普通的二叉查找树的删除操作一样；节点 a 只能是黑色，节点 b 也只能是红色，其他情况均不符合红黑树的定义。这种情况下，我们把节点 b 改为黑色；调整结束，不需要进行二次调整。

　　CASE 2：如果要删除的节点 a 有两个非空子节点，并且它的后继节点就是节点 a 的右子节点 c。我们就依次进行下面的操作：如果节点 a 的后继节点就是右子节点 c，那右子节点 c 肯定没有左子树。我们把节点 a 删除，并且将节点 c 替换到节点 a 的位置。这一部分操作跟普通的二叉查找树的删除操作无异；然后把节点 c 的颜色设置为跟节点 a 相同的颜色；如果节点 c 是黑色，为了不违反红黑树的最后一条定义，我们给节点 c 的右子节点 d 多加一个黑色，这个时候节点 d 就成了“红 – 黑”或者“黑 – 黑”；这个时候，节点变成了节点 d，第二步的调整操作就会针对节点来做。

　　CASE 3：如果要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是右子节点，我们就依次进行下面的操作：找到后继节点 d，并将它删除，删除后继节点 d 的过程参照 CASE 1；将节点 a 替换成后继节点 d；把节点 d 的颜色设置为跟节点 a 相同的颜色；如果节点 d 是黑色，为了不违反红黑树的最后一条定义，我们给节点 d 的右子节点 c 多加一个黑色，这个时候节点 c 就成了“红 – 黑”或者“黑 – 黑”；这个时候，节点变成了节点 c，第二步的调整操作就会针对节点来做。

　　2. 针对节点进行二次调整 　　经过初步调整之后，节点变成了“红 – 黑”或者“黑 – 黑”节点。针对这个节点，我们再分四种情况来进行二次调整。二次调整是为了让红黑树中不存在相邻的红色节点。 　　CASE 1：如果节点是 a，它的兄弟节点 c 是红色的，我们就依次进行下面的操作：围绕节点 a 的父节点 b 左旋；节点 a 的父节点 b 和祖父节点 c 交换颜色；节点不变；继续从四种情况中选择适合的规则来调整。

　　CASE 2：如果节点是 a，它的兄弟节点 c 是黑色的，并且节点 c 的左右子节点 d、e 都是黑色的，我们就依次进行下面的操作：将节点 a 的兄弟节点 c 的颜色变成红色；从节点 a 中去掉一个黑色，这个时候节点 a 就是单纯的红色或者黑色；给节点 a 的父节点 b 添加一个黑色，这个时候节点 b 就变成了“红 – 黑”或者“黑 – 黑”；节点从 a 变成其父节点 b；继续从四种情况中选择符合的规则来调整。

　　CASE 3：如果节点是 a，它的兄弟节点 c 是黑色，c 的左子节点 d 是红色，c 的右子节点 e 是黑色，我们就依次进行下面的操作：围绕节点 a 的兄弟节点 c 右旋；节点 c 和节点 d 交换颜色；节点不变；跳转到 CASE 4，继续调整。

　　CASE 4：如果节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色的，我们就依次进行下面的操作：围绕节点 a 的父节点 b 左旋；将节点 a 的兄弟节点 c 的颜色，跟节点 a 的父节点 b 设置成相同的颜色；将节点 a 的父节点 b 的颜色设置为黑色；从节点 a 中去掉一个黑色，节点 a 就变成了单纯的红色或者黑色；将节点 a 的叔叔节点 e 设置为黑色；调整结束。

　　3、小结 　　第一点，把红黑树的平衡调整的过程比作魔方复原，不要过于深究这个算法的正确性。你只需要明白，只要按照固定的操作步骤，保持插入、删除的过程，不破坏平衡树的定义就行了。 　　第二点，找准节点，不要搞丢、搞错节点。因为每种操作规则，都是基于节点来做的，只有弄对了节点，才能对应到正确的操作规则中。在迭代的调整过程中，节点在不停地改变，所以，这个过程一定要注意，不要弄丢了节点。 　　第三点，插入操作的平衡调整比较简单，但是删除操作就比较复杂。针对删除操作，我们有两次调整，第一次是针对要删除的节点做初步调整，让调整后的红黑树继续满足第四条定义，“每个节点到可达叶子节点的路径都包含相同个数的黑色节点”。但是这个时候，第三条定义就不满足了，有可能会存在两个红色节点相邻的情况。第二次调整就是解决这个问题，让红黑树不存在相邻的红色节点。 　　六、红黑树的应用场景 　　1、如果应用场景中对插入删除频繁，对查找要求较高，这种场景更适合红黑树（ 如果应用场景中对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树，这种场景更适合AVL树）。 　　2、通常红黑树被用于存储内存中的有序数据，增删很快，内存存储不涉及 I/O 操作（B/B+树更适合IO操作的数据结构（比如磁盘数据），可以减少 I/O 次数，B和B+主要用在文件系统以及数据库中做索引等，比如Mysql：B-Tree Index in MySql） 　　3、现在部分场景使用跳表来替换红黑树，对并发和性能有要求的情况下，如何选择合适的数据结构（是跳跃表还是红黑树）？ 　　3.1 skiplist的复杂度和红黑树一样，而且实现起来更简单。 　　3.2 在并发环境下skiplist有另外一个优势，红黑树在插入和删除的时候可能需要做一些rebalance的操作，这样的操作可能会涉及到整个树的其他部分，而skiplist的操作显然更加局部性一些，锁需要盯住的节点更少，因此在这样的情况下性能好一些。 　　3.3.跳表区间查找效率更高，做range相关功能简单，定位首尾后可以直接拿到前驱和后继。 　　所以这里结论是，如果考虑实现简单（红黑树相对skiplist实现更为复杂一点，平衡调节需要考虑7种场景平衡旋转，如下图），性能不差，并发友好，需要区间查找，可能skiplist是一个比较好的选择。 　　4、红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构（persistent data structure）之一，它们用来构造关联数组和集合，每次插入、删除之后它们能保持为以前的版本。除了的时间之外，红黑树的持久版本对每次插入或删除需要的空间也不会太多。 　　实际上，对于普通开发者来说，不需要自己实现红黑树（可以借鉴成熟的实现，可以忽略红黑树实现的复杂性），所以生产环境中红黑树使用还是比较常见。 　　红黑树已经落地的场景 　　1、C++ 　　广泛用在C++的STL中。如map和set都是用红黑树实现的； 　　2、Java 　　Java的集合框架(HashMap、TreeMap、TreeSet)； HashMap的底层实现，在JDK1.8中为了解决过度哈希冲突带来的长链表，当链表长度大于某个阈值会将链表转为红黑树； 　　3、Linux操作系统 　　CFS进程调度算法中，vruntime利用红黑树来进行存储，选择最小vruntime节点调度。 　　数据包CD / DVD驱动程序执行相同的操作。 　　高分辨率计时器代码使用rbtree来组织未完成的计时器请求。 　　ext3文件系统跟踪红黑树中的目录条目。 　　虚拟内存结构管理（VMA）。 　　多路复用技术的Epoll的核心结构也是红黑树+双向链表。 加密密钥和网络数据包均由红黑树跟踪。 　　4、Linux应用程序 　　nginx用红黑树管理timer等。