红黑树算法复杂度_八种基本排序及其时间复杂度

小星学DSA丨一文学完红黑树（简明教程）　　这是小星学DSA系列的第一篇，我会记录我学习的过程与理解，希望能够帮到你。本篇文章的思维导图如下，在文章的末尾，我会给出更加详细的思维导图。

　　红黑树的定义　　红黑树的概念与性质　　红黑树是一棵节点为黑色或红色的二叉搜索树；性质1：根节点与外部节点（叶子节点的空子节点）为黑色性质2：从根节点到外部节点的路径上，不能有两个连续的红色节点性质3：从根节点到外部节点的路径上，黑色节点的数目相同小星说丨一句话概括红黑树性质：头尾黑，红红不相连，黑节点数目相等　　红黑树的复杂度及证明　　红黑树的空间复杂度为O(n)红黑树的时间复杂度为: O(lgn) 　　证明红黑树的时间复杂度　　等价命题：一棵含有n个节点的红黑树的高度至多为2log(n+1)逆否命题：高度为h的红黑树，其节点至少为
$2^{h/2}-1$ 个设节点x路径中黑节点的数量为bh(x)，则上述命题为：高度为h的红黑树，其黑节点至少为
$2^{bh(x)}-1$ 个数学归纳法证明： h = 0, 易证假设h=H-1时等式成立，则h=H时，根节点的两个子节点高度均为H-1，则根节点的黑节点数量至少为
$2*2^{bh(root.child)}-2+1=2^{bh{(root)}}-1$ ,等式成立小星说丨用高度推节点数地计算和理解更容易　　红黑树的操作　　红黑树的作为树的基本操作：查找、插入、删除为了维护红黑树性质需要的操作：左旋、右旋　　红黑树的左旋与右旋　　左旋即被旋转的节点（根节点）变为了右节点的左子节点，右节点代替了它的位置，而右节点原先的左子节点则变为了被旋转节点的右节点；

　　右旋即被旋转的节点（根节点）变为了左节点的右子节点，左节点代替了它的位置，而左节点原先的右子节点则变为了被旋转节点的左节点。小星说丨左旋：被左旋的节点变为左子节点；右旋：被右旋的节点变为右子节点。想象被旋转的节点是一个跷跷板的支点，左旋即把右节点翘上去，右旋即把左节点翘上去，多出来的节点由支点接住。　　红黑树的查找　　在查找上，红黑树与普通的二叉搜索树完全一样，不一样的点在于红黑树的查找复杂度为O(lgn)。二叉搜索树的查找非常简单，只要将查找值与当前节点的值比较，大则向右找，小则向左找，这里不再赘述。　　红黑树的插入　　红黑树的插入总共三步：1. 将红黑树当作二叉查找树，插入节点；2. 将插入的节点着色为红色；3. 通过旋转着色，使之重新成为一颗红黑树。接下来我们详细说明一下这三步：1. 首先我们不考虑颜色，而是根据二叉查找树的性质，找到红黑树的插入点。我们用一个节点指针遍历二叉树，反复与节点比较，大则向右，小则向左，直到到达null；2. 为了在插入时不破坏红黑树的性质3（从根节点到外部节点的路径上，黑色节点的数目相同），我们将该节点着色为红色，接下来，只要解决红-红冲突，便能完成插入。　　插入修正　　小星说丨一句话理解红黑树的插入修正：红色矛盾向上转移，直到移到根节点变为黑色。因为矛盾要向上转移，因此我们需要考虑上一层长辈节点的状态，即父节点与叔叔节点。　　这里，我给插入修正的情况做了一个总结表当前节点父节点叔叔节点当前节点与父亲节点的偏向操作根节点染黑红黑无需修正红红红父节点和叔叔节点变黑，祖父节点变红，开始解决祖父节点可能存在的矛盾红红黑不一致当前节点通过左旋或右旋成为原父节点的父节点，使二者朝向一致，此时将原父节点当作当前节点，再次判断当前节点状态。红红黑一致父节点通过左旋或右旋成为原祖父节点的父节点，父节点变为黑色，原祖父节点变为红色　　可以这样理解红黑树插入修正的逻辑：1. 父亲红，叔叔红，那么就交换父亲层和祖父层的颜色，将红色矛盾向上转移至祖父，而父亲和叔叔这一层可以变为黑色；2. 父亲红，叔叔黑，由于性质3的限制，不能直接交换（下一层需要两个变黑才能换上一层一个变红），为了只变父亲这边不变叔叔那边，于是使用左旋或右旋来交换父亲和祖父的颜色；3. 旋转时要保持当前节点和父亲节点的父子关系，所以要求偏向一致。小星说丨红黑树插入修正达到以下三种情况，即为最终情况，可以彻底解决矛盾，其他的操作是为了达到这三种状态。1. 当前节点为根节点2. 当前节点的父节点为黑色3. 双红偏向一致，叔叔黑色

　　红黑树的删除　　红黑树的删除同样是三步：1. 将红黑树当作二叉搜索树，找到需要删除的节点2. 使用恰当的节点值代替该删除节点，并将矛盾转移到代替节点3. 删除代替节点，并根据代替节点的情况，旋转着色使之重新成为一颗红黑树看起来比插入要复杂一些，这是因为插入的地方肯定为叶子节点，而删除的地方则不一定，因此我们需要将删除的矛盾转移至叶子节点，然后再来解决红黑树的矛盾。　　找到代替节点　　找到删除节点后，我们需要明确，删除节点的位置是否可以空置，如果不空置，是否需要找一个替代节点，而替代节点又如何解决？这里有三种情况：1. 被删除节点为叶子节点，由于它已经是叶子节点，因此这个地方可以为空，也即节点可以直接删除。

　　2. 被删除的节点有一个子节点，那么我们就用这个子节点代替这个节点的位置，而将子节点删除，由于红黑树的的性质3限制，这个子节点肯定是一个叶子节点。

　　3. 被删除的节点有两个子节点，那么我们就找到该节点的后继节点（右子树的最左节点），用后继节点代替这个节点的位置，而将后继节点删除，后继节点也必定为一个叶子节点

　　删除修正　　经过第二步，我们将删除指定节点的任务，都转化为了删除一个叶子节点的任务，接下来，我们需要根据这个叶子节点的状态，通过旋转着色维护红黑树的性质。小星说丨一句话总结红黑树的删除修正：父节点下放弥补双黑，兄弟相应调整。这里主要影响到的是兄弟节点和侄子节点　　以下两种情况，可以直接删除该节点，用一个外部节点代替其位置

　　以下几种情况，为了维护性质3，我们在用外部节点代替该节点时，将该外部节点标记为双黑（DB，double black)

　　这样理解红黑树的删除修正逻辑：为了弥补双黑节点将要失去的黑色，我们将父节点加一个黑色弥补到这条线路上，但这样兄弟节点那边会多一个黑色。因此，如果侄子是黑的，那么兄弟就可以变红来保持黑色平衡；否则为了不影响兄弟路线上的黑色数目，父节点需要通过旋转来到DB的路径，而兄弟路线上少的一个黑色要由远侄子（不会被带到DB路线上的侄子）弥补。因此，这种情况下兄弟必须是黑色（这个黑色将贡献给父亲），而远侄子也必须是红色（才能弥补一个黑色）。小星说丨红黑树删除修正达到以下三种情况，即为最终情况，可以彻底解决矛盾，其他的操作是为了达到这三种状态。1. 当前节点为根节点2. 当前节点为红色节点3. 兄黑远侄子红

　　手撕红黑树　　知乎的编辑器太难用了，原始的Markdown语法都识别不了，这一部分的代码与讲解可以参看我的个人网站　　小星code丨一文学完红黑树　　总结　　在最后，我们再用一张思维导图总结本篇博客的内容

　　源代码　　本文代码已在github上开源，包含c++，python(待补充), golang(待补充)的红黑树代码(https://github.com/Yuxin1999/star-code) 　　参考资料　　(红黑树-插入篇-掘金)(Deletion in Red-Black (RB) Tree)(Red-Black Tree)

红黑树算法复杂度_八种基本排序及其时间复杂度

相关推荐