红黑树难吗_最坏时间复杂度

【高阶数据结构】红黑树详解　　@[TOC] 　　前言　　这篇文章我们再来学习一种平衡搜索二叉树——红黑树红黑树和AVL树都是常见的自平衡二叉搜索树，它们都可以用于高效地支持插入、删除和查找等操作。虽然它们都能够保持树的平衡性，但在不同的应用场景下，红黑树和AVL树有各自的优势和适用性。　　1. 红黑树的概念及性质　　1.1 红黑树的概念　　红黑树（Red-Black Tree）也是是一种自平衡的二叉搜索树，与AVL树不同的是它在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍（最长路径也不会超出最短路径的两倍，因此红黑树的平衡性要求相对宽松，没有AVL树那样严格），从而使搜索树达到一种相对平衡的状态。

　　1.2 红黑树的性质　　红黑树具有以下特点每个结点不是黑色就是红色根结点必须是黑色的红色结点的两个子结点必须都是黑色的，这保证了没有两个连续的红色节点相连 每个叶子结点都是黑色的(此处的叶子结点指的是空结点，也被称为NIL节点)任意结点到其每个叶子结点的简单路径上，黑色节点的数量相同：确保了树的黑平衡性，即红黑树中每条路径上黑色结点的数量一致。

　　大家可以对照着看一下上面的图，看它是否满足这些性质。　　思考：为什么满足上面的性质，红黑树就能保证：其最长路径中结点个数不会超过最短路径结点个数的两倍？（其实不带第4条就可以，加不加第4条都不会影响每条路径黑色结点数量是否相等）那通过上面的性质我们可以得知，红黑树中的结点要么是黑色，要么是红色，这没什么可说的；然后要求根结点一定是黑色的，红色结点不能连续出现，如果出现了红色结点，那它的子结点必须是黑色的，然后还要求每条路径黑色结点的数量必须相等。那这样其实就可以保证一棵红黑树中最长路径不超高最短路径的两倍。当然实际中不同的红黑树情况是不一样的，所以我们这里来分析一种极端的情况：大家想，如果一棵红黑树有红有黑，它里面如果有一条全黑的路径，那这条全黑的路径一定就是最短路径；如果有一条是一黑一红，一黑一红…，这样黑红相间的，那他就是最长的路径。然后它们里面的黑色结点个数又是相同的的，所以最长路径最多是最短路径的两倍，不可能超过最短路径两倍。所以这样红黑树的高度就能够保持在一个相对平衡的范围内，当然他就没有AVL树那么严格。比如这样的

　　那另外:其实分析上面的性质，红黑树是可以全黑的，全部黑色结点，只要满足上面的性质即可。　　然后大家思考一个问题，上面第四条性质——每个叶子结点都是黑色的(此处的叶子结点指的是空结点，也被称为NIL节点)，有什么用？那大家先算一下这个红黑树有多少条路径？

　　如果不带空的话，我们可能会认为有5条，但是这里计算路径其实应该走到空（NIL），所以正确的应该是有11条路径。所有我们可以认为这条规则就是为了更好的帮我们区分不同路径的。　　然后再补充一个概念：结点的黑高（黑色高度）：从某结点出发（不含该结点）到达任一空叶结点的路径上经过的黑结点总数

　　1.3 已经学了AVL树，为啥还要学红黑树　　然后我们再来分析一个问题：大家想，对于一棵红黑树来说，如果它里面全部的黑色结点一共有N个的话，那它的最短路径长度就差不多是$log_2 (N)$。然后整棵树的节点数量就是在【N，2N】之间。所以最长路径长度就可以认为差不多是2$log_2 (N)$ 所以红黑树的查找最少是$log_2 (N)$次，最多是2$log_2 (N)$次，所以红黑树查找的时间复杂度是O($log_2 N$)，计算时间复杂度前面的常数项可以省略嘛。而AVL树也是O($log_2 N$），但AVL树是比较严格的O($log_2 N$），而红黑树是省略了常数项。所以严格来说，红黑树的查找效率是比不上AVL树的（但对于计算机来说是没什么差别的），但是它们是同一个数量级的，都是O($log_2 N$）。　　那既然好像都差不多，为什么我们已经学了AVL树了，还要学红黑树呢？红黑树有什么优势吗？ ，由于AVL树要求更加严格的平衡，所以在进行插入和删除操作时，可能需要更频繁地进行旋转操作来调整树的结构，以保持平衡。相比之下，红黑树的插入和删除操作需要旋转的次数相对较少，因此在插入和删除操作频繁的情况下，红黑树可能更加高效。这个如果大家学完这篇文章或许能更好的理解。　　所以综合而言：红黑树其实更胜一筹，红黑树在实际应用中更为常用，STL中的map和set底层就是用的红黑树，我们后面也会用红黑树进行模拟实现。当然红黑树和AVL树在不同的应用场景下有各自的优势和适用性，所以我们都有必要学习学习。　　2. 红黑树结构的定义　　那我们先来定义一下红黑树的结构：这里结点的颜色我们可以用一个枚举

　　这些代码很简单，相信就不用给大家解释了。　　然后大家看，这里结点的颜色我们给的是红色，为什么要选择红色呢？黑色不可以吗？我们来分析一下如果我们插入一个新结点给的是黑色，那它一定会违反上面提到的红黑树的第5条性质——每条路径上黑色结点的数量一致。

　　因为原来每条路径黑色结点数量是相同的，现在新插入一个黑色结点的话，那插入的这条路径会增加一个黑色结点，但是其它路径数量不变，所以其它所有的路径黑色结点数量都和这一条不相等，这样就比较麻烦了。那如果我们插入结点默认给红色呢？会违反规则吗？那红色的话其实要看具体情况了：如果插入一个红色结点，但是它的父亲也是红色，那就出事了，因为红黑树里面不能出现连续的红色结点，那这种情况就需要调整了。但如果它的父亲是黑色，那就没问题，不需要进行什么处理。　　所以我们新插入的结点给成红色，当然如果是第一次插入根结点我们可以直接给黑色，因为红黑树要求根结点必须是黑色嘛。　　3. 插入（仅仅是插入过程）　　由于红黑树也是一种搜索二叉树，是在二叉搜索树的基础上加上其平衡限制条件来实现平衡。　　所以红黑树插入的逻辑也根搜索二叉树一样：

　　那插入一下就完事了吗？当然不是，和AVL树一样，插入新结点之后，我们要去判断此时这棵树是否还满足是一棵红黑树，如果不满足就要进行相应的调整。　　那红黑树又是如何进行调整的呢？　　4. 插入结点之后根据情况进行相应调整　　对于红黑树来说，插入新结点之后，我们要检查红黑树的性质是否遭到破坏，如果遭到破坏的话，就需要进行相应的调整。　　因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连续红色结点出现，此时需要对红黑树分情况来讨论：　　约定：当我们在红黑树中插入一个新结点的时候，cur为当前新插入结点，p（parent）为父结点，g（grandfather）为祖父结点，u（uncle）为叔叔节点比如

　　我们下面分成了三种情况，但是有些地方分的比较细的话会分为五种：第一种就是第一次插入，作为根结点，直接将它染成黑色就完了，那这种我们上面已经处理过了。第二种就是插入的时候它的父亲是黑色的（新插入的结点是红色的），这种就不需要调整，插入完直接结束。那第二种的话我们也不需要单去处理，因为第二种不进入我们下面讲的三种情况，所以就不会对他进行任何处理，最后直接结束。　　最后全部写完大家可以自己捋一遍。　　下面讲解剩下的三种情况：　　4.1 cur为红，p为红，g为黑，u存在且为红（无需旋转，变色即可）　　情况分析及处理　　那这个我们就认为是情况三。　　那首先我们还是来看一下该情况对应的一个抽象图：

　　这就是我们当前要讨论的情况，那大家看到这里我没有像AVL树那里的画成高度为h的树，因为红黑树这里就不太高度了，而是重点结点的颜色。那这里a/b/c/d/e高度都为0的话其实就是cur就是新增的结点，如果不为0代表的情况其实就是下面插入之后调整更新上面变成这种情况，那他们的处理方法是统一的。现在我们插入一个红色结点，那这里就出现了连续红色结点的情况，这是不行的。那我们可以直接把p改成黑色吗？这样不就没有连续红色结点了不可以，直接把p改成黑色的话，这条路径就增加了一个黑色结点，但是其它路径数量不变，那就不满足所有路径黑色结点数量相同的性质了。　　那对于这种情况我们要如何去处理呢？首先第一步：将p,u改为黑，g改为红

　　那这样处理过后就不存在连续红色结点的情况了，而且每条路径黑色结点的数量依然相等。　　那这样就完了吗？还没有。如果g是根节点，调整完成后，需要将g改为黑色。

　　这样它才满足是一棵红黑树。　　那上面是g是根结点的情况，那如果g是一棵子树呢？比如这样：

　　当然这里不止在cur这个位置插入会引发这种情况（上面那个也是），p的两个孩子位置，u的两个孩子位置，在这4个位置新插入结点是不是都是这种情况啊。　　那这种情况又如何处理呢？如果g是子树，那前面的步骤还是一样——将p,u改为黑，g改为红

　　然后呢？如果g的父亲是黑色，就可以结束了，但现在g的父亲也是红色，所以：继续向上调整，把g当成cur，重新确定p、u、g，进行同样的操作，一直往上走

　　直至某一次调整完遇到9的父亲为黑或者走到根停止　　代码实现　　那我们来写一下代码：

　　上面画图没有画父亲是祖父右孩子的情况，单处理方式是一样的，这里代码直接加上了。代码我就不过多解释了，相信结合图和上面的分析大家很容易能看懂。　　4.2 cur为红，p为红，g为黑，u不存在/u存在且为黑（单旋+变色）　　情况四　　情况分析及处理　　那上面讨论的是u存在且为红的情况，那如果u不存在或者u存在且为黑呢？　　先来看u不存在的情况：像这样

　　cur是新插入的结点，它的叔叔u不存在。怎么处理呢？其实跟下面讨论的u存在且为黑的处理方法一样，下面统一说明。　　来看u存在且为黑的情况：如果出现u存在且为黑的情况一定是由上面的4.1情况3调整得到的。为什么呢？大家看，如果插入的时候就是这种情况

　　是不可能出现的，因为这样的话插入之前红黑树中不同路径的黑色结点数量就不相等了，他就不符合是一颗红黑树了。所以出现这种情况一定是情况一转变得来的

　　就是这样子，这种情况的话c里面一定要有一个黑色结点，d/e要么为空，要么是一个红色结点，这样才满足是红黑树（在插入之前），我们就不具体画了，情况比较多。那如何处理呢？ 那对于这种情况我们要进行的旋转+变色（对于上面u不存在也是一样）为什么要旋转？因为这种情况的话最长路径有可能已经超过最短路径的两倍了，比如上面这个图如果如果d/e是空的话就已经超过了。所以要先旋转降高度，再去调整颜色使它符合红黑树。进行什么旋转呢？那就要看具体情况了，其实还是我们AVL树那里学习的四种情况。当前我们是在较高左子树的左侧插入，所以要进行的旋转是右单旋

　　先旋转（对g这棵树）的目的就是让它变平衡。然后变色怎么变呢？变色的话不论那种旋转是统一的：p、g变色–p变黑，g变红

　　然后大家看就重新符合红黑树了（上面说了c里面一定要有一个黑色结点，d/e要么为空，要么是一个红色结点）。　　那上面说了u为空也是一样的处理，我们可以来画一下

　　首先这种情况也应该是右旋（较高左子树左侧插入）

　　是不是一样的处理啊。　　这里变色的情况是一样的，关键在于判断并进行不同的旋转。我们上面分析的情况是在较高左子树的左侧插入，所以先要进行右单旋，然后变色。如果我们是在右侧插入（较高右子树的右侧）的话，那就是先进性左单旋，然后变色，这里变色是一样的。比如这样：

　　代码实现　　这里的代码我们等到后面和双旋的一起写　　那上面我们说细分的话有5种情况，上面已经说了4种，那最后一种其实也是u不存在/u存在且为黑，与上一种情况的区别就是第5中是==双旋==+变色　　4.3 cur为红，p为红，g为黑，u不存在/u存在且为黑（双旋+变色）　　上面我们分析的是需要进行单旋然后变色的情况，那当然就有需要进行双旋调整高度，然后再变色的情况。当然本质是因为插入的情况不同，所以需要不同的旋转来降高度。　　情况分析及处理　　那我们就来分析一下需要双旋+变色的情况：首先前提条件根上面一样，还是cur为红，p为红，g为黑，u不存在/u存在且为黑　　这里画图我就不分那么细了，因为跟上面其实差不多，只是要进行的旋转不同我们来画一种左右双旋+变色的情况

　　那如果u不存在，那就是这样

　　那先进行一个左右双旋

　　这样高度就降下去了，然后怎么变色呢？ cur变黑，g变红（不论哪种双旋，变色是一样的）

　　这样就重新调整为红黑树了。　　再给大家画一下u存在且为黑的情况吧：同样的，如果这里出现u存在且为黑的情况，也一定是有4.1情况3调整更新得到的比如这样

　　那然后其实和u为空一样，先进行一个左右双旋（因为我们这里画的还是较高左子树右侧插入的情况）

　　然后变色，还跟上面一样，cur变黑，g变红

　　4.4 （单/双）旋转+变色代码统一实现　　那接下来我们来写一下需要旋转+变色调整的几种情况的代码　　首先我们来看左侧插入的情况（右单旋/左右单旋）

　　那我们来写一下：

　　这就是左侧插入的两种需要旋转的情况处理　　那我们再来写一下右侧插入的：

　　叔叔为红我们上面写过了，这里还是写叔叔不存在或者存在且为黑的情况

　　就写好了。左旋右旋的代码直接拷贝AVL树的就行，记得把平衡因子的更新删掉。　　5. 红黑树的测试　　5.1 验证其为搜索二叉树　　首先我们还是先来验证他是否是二叉搜索树，看它中序是否有序就行了

　　测试一下

　　是平衡的，没问题。再换一组数据

　　没什么问题 ps：我在这个地方测试的时候修改了几处错误，都是判断的==写成=了，我都改了过来，上面代码的截图有错误的地方我也做了修改。如果有遗漏的地方，大家发现了上面代码片段的截图有地方有错误的话，可以看我最后分享的源码。（不过应该都被我修改过了）　　5.2 验证其是否平衡且满足红黑树性质　　那如何判断它是否满足是一棵红黑树呢？　　其实就是去检查那几条规则（性质）：首先结点颜色要么是黑色，要么是红色，这没什么好检查的。然后根结点必须是黑色，这个可以检查一下，如果根结点不是黑色（是红色）直接就不符合了

　　然后如果出现连续的红色结点，那也不符合。那怎么检查有没有出现连续红色结点呢？我们可以去遍历这棵树，然后遇到红色结点判断它的孩子是不是红色结点，如果存在红色结点它的孩子也是红色，那就不符合。这样确实可以，但是不太好，因为孩子的话要检查两个，而且结点的孩子有还有可能不存在，为空，那还得再加一个判断。所以我们可以这样做：遍历遇到红色结点我们去看它的父亲，如果它的父亲也为红色那就不行。而判断父亲的话，只有根结点没有父亲，但是根结点是黑色的也不会去检查它。所以这样写会好一点

　　然后还剩一个，我们要检查每条路径黑色结点数量是否相等，存在不相等的情况就不符合。那这个要如何检查呢？，我们可以先求出一条路径的黑色结点数量，把它作为基准值，然后再递归求出每条路径的黑色结点数量和它比较，如果存在不相等的情况，就不符合。

　　那就写好了　　然后我们来验证一下：

　　5.3 大量随机数构建红黑树进行测试　　下面我们来生成一些随机数构建一棵红黑树测试一下：先来10万个

　　没有出现问题来100万

　　没有问题。　　5.4 插入相同数量随机数比较AVL树和红黑树的高度　　然后我们AVL树写的求高度的函数拷贝过来，在AVL树和红黑树中插入相同数量的随机数，看看它们的高度会差多少：

　　我们看到插入相同数量随机数它们的高度是可以达到一样高的，当然这里产生的随机数可能会有很多重复值，所以实际不会插入那么多。

　　还是10万个，这次对产生的随机数都加个i（那产生的随机数不同的数量就多了），我们看到就有一些差异了那让他们插入的值不相同呢？

　　大家看这次差异就大了，还是红黑树要高一点那增加到100万个数据呢？

　　这次差的就多了。那这个结果其实也证实了我们上面说的，就是AVL树对平衡的控制是比较严格的，而红黑树是相对宽松的。　　6. 红黑树的删除　　红黑树的删除呢我们这里不做详细讲解：红黑树的删除比较复杂，要比插入还复杂好多。但关键的是红黑树的删除在考研包括我们找工作笔试面试的时候一般是不会考察的，所以我们也没必要去学。大家有兴趣的可以自己查找相关资料进行学习，可以参考《算法导论》或者《STL源码剖析》　　7. 红黑树的查找　　那红黑树的查找就也和搜索二叉树的查找一样，之前讲过，这里就不再说了。　　8. 红黑树与AVL树的比较　　红黑树和AVL树都是高效的自平衡搜索二叉树，增删改查的时间复杂度都是O($log_2 N$)。红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，所以AVL树的插入和删除操作比红黑树更耗时。因为AVL树在插入和删除节点后，会进行更多的旋转操作以维持一个较为严格的平衡，所以插入和删除操作的时间复杂度更高。相对而言，红黑树对平衡的控制比较宽松，降低了插入删除时需要旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。在实际应用中，红黑树的使用更广泛。许多编程语言和库都使用红黑树作为基础数据结构，例如C++ STL中的std::map和std::set就是基于红黑树实现的。　　9. 红黑树的应用　　1. C++ STL库 — map/set、mutil_map/mutil_setJava 库linux内核其他一些库　　10. 源码分享　　10.1 RBTree.h 　　10.2 Test.cpp

红黑树难吗_最坏时间复杂度

相关推荐