红黑树的原理五234树,红黑树之原理详解 _红黑

红黑树之原理详解性质1: 每个节点要么是黑色 ,要么是红色。
性质2: 根节点是黑色。
性质3: 每个叶子节点(NIL)是黑色。
性质4: 每个红色节点的两个子节点一定都是黑色。
性质5: 任意一个节点到每个叶子节点的路径都包含数量相同的黑节点。俗称: 黑高 !
从性质5又可以推出:
性质5.1: 如果一个节点存在黑子节点,那么该结点肯定有两个子节点。
插入操作包括两部分工作:
注意: 插入结点,必须为红色 ,理由很简单,红色在父节点(如果存在)为黑色节点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。如果插入结点是黑色,那么插入位置所在的子树黑色结点总是1,必须做自平衡。
最简单的一种情景,直接把插入结点作为根结点就行
注意: 根据红黑树性质2: 根结点是黑色。还需要把插入结点设为黑色。
处理: 更新当前结点的值,为插入结点的值
由于插入的结点是红色的,当插入结点的父结点为黑色时,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。
再次回想红黑树的性质2: 根结点是黑色。如果插入结点的父结点为红结点 ,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。这一点很重要,因为后序的旋转操作肯定需要祖父结点的参与。
依据红黑树性质4可知,红色结点不能相连===>祖父结点肯定为黑结点
因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是:黑红红。显然最简单的处理方式是把其改为: 红黑红
处理:
1.将P和U结点改为黑色
2.将PP改为红色
3.将PP设置为当前结点,进行后序处理
注意: 单纯从插入前来看,叔叔结点非红即空(NIL结点),否则的话破坏了红黑树性质5,此路径比其它路径多一个黑色结点。
处理:
处理:
该情景对应情景4.2,只是方向反转,直接看图
处理:
处理:

文章插图
红黑树详解首先，我们来了解一下二叉查找树,二叉查找树具备以下几个特点：
1、左子树上所有节点的值均小于或等于它的根节点的值；
2、右子树上所有节点的值均大于或等于它的根节点的值；
3、左右子树也分别为二叉排序树。
下面我们以一棵典型的二叉查找树来查找值为10的节点：
以上图例正是典型的二分查找的思想，查找所需的最大次数等同于二叉查找树的高度。在往树中插入新节点的时候也要用类似的方法，通过一层一层地比较大小从而找到新节点适合插入的位置。但是即便如此，二叉查找树依旧存在它的缺陷，并且此缺陷恰恰体现在插入新节点的时候。请看下面图例展示：
这样的瘸腿形态虽然也符合二叉查找树的特性，但是查找的性能却大打折扣，几乎变成了线性数据结构。为了解决二叉查找树多次插入新节点而导致的不平衡问题，红黑树便应运而生了。
红黑树是一种自平衡的二叉查找树，除了符合二叉查找树的特性外，还具有下列性质：
1、根节点是黑色，节点是红色或黑色；
2、每个叶子节点都是黑的空节点；（nil节点）
3、每个红色节点的两个子节点都是黑色；（也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点）
4、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些规则的限制，保证了红黑树的平衡，红黑树从根到叶子的最长路径不会超过最短路径的两倍。当红黑树插入或者删除节点的时候，红黑树的规则可能被打破，这时候就需要做出调整来维持它的平衡了。请看下面的例子（注意：新插入的节点必须是红色，否则就没有意义了）：
由于父节点22是也是红色节点，因此打破了红黑树的规则（每个红黑树的两个子节点都是黑色），所以必须进行调整，使之重新符合规则。那么我们需要作出怎样的调整才能保证一棵红黑树始终是符合规则的标准红黑树呢？调整有两种方法：“变色”和“旋转”，其中，旋转又分为两种形式：“左旋转”和“右旋转” 。
为了重新符合红黑树的规则，尝试把红色节点变成黑色，或者把黑色节点变成红色。
下图是摘自上面红黑树的一部分，节点25并非根节点。正如上面所说因为新节点21和节点22连续出现了红色，不符合规则，所以把节点22从红色变成黑色。
但这样并不算完，节点22变成黑色后，凭空多出的黑色节点又打破了规则，发生连锁反应，需要继续把节点25从黑色变为红色。
此时仍未结束，节点25变为红色后，又和节点27形成了两个连续的红色，规则又被打破，需要继续把节点27从红色变为黑色。
如此一路走下来，完成变色调整。
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为左孩子。
顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为右孩子。
这几种方法究竟怎么使用呢？红黑树的插入和删除包含很多种情况，每种情况都有不同的处理方式，下面举一个典型的例子，可以体会一下这个过程。
还以刚才插入节点21为例：
首先我们变色处理，把节点25及其下方的节点变色：
此时节点17和节点25是连续的两个红色节点，那么此时再把节点17变成黑色节点可以吗？显然是不可以的，这样依然不符合规则，更不可以把根节点13变成红色。
既然变色已经无法解决问题，我们此时就要使用旋转了，我们把节点13看作X，把节点17看作Y，进行左旋转：
旋转完成后，由于根节点必须是黑色，所以还需要进行变色：
至此并没有结束，因为其中两条路径（17->8->6->NIL）的黑色节点数是4，其他路径的黑色节点数是3，依旧不符合规则。这时我们需要把节点13看成X，节点8看成Y，做右旋转：
然后再进行变色：
经过上面一系列的调整，我们的红黑树终于变得重新符合规则，整个过程有点复杂，经历了：变色-->左旋转-->变色-->右旋转-->变色这样的一系列步骤。
经过上面细致的步骤演示，想必大家对二叉查找树和红黑树有所了解了吧，对红黑树结构插入新节点所触发的一系列的变化流程也有了大概印象。实际中红黑树的应用是很多的，比如JDK（Java开发工具包）的集合类TreeMap和TreeSet底层就是红黑树实现的，在Java8中， HashMap也用到了红黑树。其实关于红黑树自平衡的调整，插入和删除节点时涉及到的情形一一展开讲解还是很多很多的，但是万变不离其中，红黑树自平衡调整的主体思想都是上面所叙述的，大家有兴趣可以再进行深入的探究。

文章插图
红黑树——一个自平衡的二叉搜索树普通的二叉搜索树在最坏的情况下，可能退化成一个链表。而又因为二叉搜索树的所有操作的性能（添加，删除，查找等），与二叉搜索树的高度有关。在最坏的情况下，二叉搜索树的高度和元素个数相同，此时二叉搜索树的效率降为了O(n)级别。
所以为了防止我们的二叉搜索树退化成一个链表，就产生了平衡二叉树。平衡二叉树可以保证它的左右两个子树的高度差不会超过1 。平衡二叉树有很多实现，一个经典实现就是红黑树。
在红黑树中将树中的节点划分为两种状态，分别用黑色和红色来表示。
红黑树为了保证自己能够平衡子树，所以制订以下五个规则：
1、每个节点必须有颜色，要么黑色，要么红色，没有别的颜色。
2、根节点必须是黑色
3、所有的空节点(nil节点)都认为是黑色节点。
4、红色的节点不能连续，即一个红色的节点，它的父节点和子节点不能也是红色的，
5、无论从哪一个节点起始，到它每个叶子节点的路径中，黑色节点数量必须相同。
在对红黑树进行添加、删除等操作之后，必须使红黑树符合这5个规则。
那么问题来了，在添加删除操作之后，树中节点的数量都变了，是怎么保证整个树满足上述这些规则呢？
这里涉及到3种操作，变色、左旋和右旋。通过这个三种操作，在增删节点之后调整树的形状结构，使它满足上述5个规则。这也是红黑树能保持平衡的原因。
变色操作我们在下文的添加、删除节点的实际操作中，再进行在描述。
先来说一下左右旋。
文字描述一下就是，2的右孩子节点4，变为了2的父节点， 2由父节点变为4的左孩子。同时，4原来的左孩子变为2的右孩子。
右旋与左旋相反，即以某节点为支点进行顺时针旋转。同样，我们看下图，是以5为支点进行的右旋:
文字描述同样反过来，5的左孩子节点3，变为5的父节点，5由父节点变为3的右孩子。3原来的右孩子变为5的左孩子。
首先是在树中找到新节点正确的位置，寻找位置的过程与普通的二叉搜索树相同，只是将新插入的节点默认为红色节点。为什么默认为红色？因为如果你将新节点默认为黑色，则插入后肯定会打破原本符合规则的红黑树（上述第5条规则）。但是，如果你将新节点定为红色，则有可能不用任何操作就符合红黑树规则，如下图，当新插入的红色节点，它的父亲节点为黑色时候，此时已经满足红黑树规则了。所以用红色比黑色好。
如果很不巧，新插入的节点的父亲节点也为红色，因为红色节点不能连续，所以我们需要调整红黑树的结构使其满足规则。在调整的过程中我们会遇到3种需要处理的情况，我们来一一进行说明。
情况1：
插入新节点40，此时它的父节点为红色，并且它的叔叔节点（即51）也为红色。此时我们需要进行变色操作。将该节点的父亲节点、叔叔节点都变为黑色，祖父节点变为红色。
此时上图已经满足红黑树的规则。但有的时候我们经过了变色操作后，仍不满足红黑树的规则，会遇到下面的情况。
情况2：
如图，我们插入新的节点53，在按情况1的操作变色后，变成了这样:
最后我们说一下情况3的情景，如下图：
我们向树中插入新节点37，在按情况1的操作变色后，变成了这样：
情况3：
3种情况我们说明完了，但是你可能还会有这样的疑问，什么时候进行左旋，什么时候进行右旋；什么时候以父节点为支点旋转，什么时候又以祖父节点为支点旋转？
那么我们可以总结一下，当遇到连续的红色节点应该怎么办：当前节点我们叫它X，如果X相对于父节点的左右位置和父节点相对于祖父节点的左右位置相同，此时，就以祖父节点为支点，进行反向旋转。例如：X为父节点的左孩子， X的父节点同样也是其祖父节点的左孩子，此时以祖父节点为支点进行右旋；
如果X相对于父节点的左右位置和父节点相对于祖父节点的左右位置不同，则以X的父节点为支点，进行旋转，旋转方向与X相对于父节点左右位置相反。例如：X为其父节点的左孩子，X的父节点为祖父节点的右孩子，此时以X的父节点为支点进行一次右旋。
在红黑树中删除节点，肯定要涉及到要删的这个节点是红色的还是黑色的。删除红色比较简单，我们先说一下删除红色节点。
删除节点要考虑这个节点所处的位置，所以我们罗列一下红色的节点所有可能的位置情况。
你可能会发现为什么少了一种情况？它不能只有左子树或者只有右子树吗?我们可以看下图:
很明显，这四种情况都不符合红黑树的规则，所以根本不会出现这种情况。
而对于既有左子树也有右子树的情况。我们可以先和普通的二叉搜索树的删除操作一样，将它与前驱或者后继交换一下。它就又变成第一种情况——成为了一个叶子节点。所以我们只需考虑当它是叶子节点的情况。
接下来我们看一下当要删除的节点是黑色的时候应该怎么办。
同样我们列一下节点位置可能的情况：
第三种情况和删除红色节点时的处理方法一样，可以转换成第一种或第二种情况，所以我们只关心前两种情况。
当要删除的黑色节点只有一个子树时：
最后我们看一下最难处理的一种情况。
要删除的黑色节点是叶子节点时：
情况1：待删除黑色节点20，它的兄弟节点为红色。
操作方法为：将远侄子节点变黑，兄弟节点与父亲节点互换颜色，最后以父节点为支点进行左旋。(为什么是左旋？因为待删除的20是左孩子，我们要将左子树长度拉长，将它沉下来，使它变成多余的节点好删除它，如果它是右孩子，则进行右旋)
操作后如下图就完成了。
情况3：待删除黑色节点20，它的兄弟节点为黑色，但它没有红色的远侄子节点(即nil点，记住，nil点算黑色)，只有红色的近侄子节点。
操作后如下图:
此时有了红色的远侄子，就满足了情况2，再按情况2进行一次操作就完成了。
情况4：待删除黑色节点20，它的兄弟节点为黑色，远侄子、近侄子节点都没有。(即两个nil节点，nil节点算黑色)
我们将上图红黑树按流程演示一下:
第一步按情况4操作，将55变红。并将父节点50看做当前节点，继续操作。
此时有关红黑树的知识就说完了。
以上所有内容都为自己查阅资料学习理解之后手敲的。尽量得采用通俗易懂的描述和解释让读者更明白。27张图都是自己亲自画的，花费了四天才写完，如果觉得写的还可以，麻烦点亮喜欢支持一下，如果还是不懂，可以下方留言QQ等联系方式，我亲自告诉你。

文章插图
红黑树-算法导论这个周看算法导论，看到红黑树，看的我云里雾里绕啊。虽然最后看懂了，据我估计，要是过一个星期不看保证忘干净，因此决定写篇博客记录下红黑树。
红黑树是二叉树的一种，所以学习红黑树必须先搞懂二叉树。
如图，一颗二叉树是按照结点（二叉树结构）组成的。每个结点可以用链表结构标示。每个结点都应该有left right p ，他们分别指向左儿子，右儿子和父结点。每个结点还应该有个关键字key 。如果某个儿子结点不存在，则相应位置就是nil 。跟结点是树中唯一的父结点值是nil的节点。
设x为二叉树中的一个结点，如果y是x的左子树中的一个结点，则key[y]<=key[x] 。如果y是x的右子树中的一个结点，则key[x]<=key[y]
我们有很多结点，如何将他组合成符合二叉树性质的二叉树呢？
我们一般通过下面两种方式遍历二叉树中的key
树根的关键字（key）在左子树和右子树的关键字之间输出就是中序遍历算法
树根的关键字（key）在左子树和右子树的关键字之前输出就是前序遍历算法
从图中我们能看出只要沿着各个结点的left指针查找下去，知道遇见nil 时候为止，就是最小值，最大值正好相反。
如图，3的前趋是2，后继是6 。
前趋后继的规律是什么呢?
前趋：如果结点x的左子树为非空，则x的前趋就是做子树中的最右结点。要是x的左子树为nil，并且有前趋y（key是最最小值对应的x是没有前趋的），那么y是x的最低祖先，并且y的右儿子也是x的祖先。（x必须出现在y的右儿子的分支中，并且y是最低祖先）
后继：如果结点x的右子树为非空，则x的后继就是右子树中的最左结点。要是x的右子树为nil ，并且有后继y（key是最大值对应的x是没有后继的），那么y是x的最低祖先，并且y的左儿子也是x的祖先。（x必须出现在y的左儿子的分支中，并且y是最低祖先）
这里一定要搞明白，因为这里是红黑树删除的基础部分。
二叉树结点的删除分三种情况。
这里针对第三种情况的删除，我们不是删除z，而是删除的是z的后继y，把y的值赋值给z，这样不破坏树中的结构。变成了只是删除了一个叶子，这个叶子的特点是左儿子是nil。
红黑树是一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是RED或者Black 。通过对任何一条从跟到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
树中每个结点包含五个域：color，key，left，right 和p 。如果某结点没有一个子结点或者父结点，则该结点相应的指针为nil 。
从图中我们能看出每个叶子节点都是nil 。nil对象都是一样的。干嘛不用一个nil 代替呢。因此如下结构。
旋转应该是二叉树的性质，只是普通二叉树没必要旋转。红黑树需要旋转来平衡树结构。
结果如下。
右旋的过程只是相反而已。
左旋的作用是将右儿子变成父结点。
右旋的作用是将左儿子变成父结点。
这样变化有什么用处呢？
我们知道，红黑树就是二叉树，因此向二叉树中插入数据没有啥区别。只是不过，当我们插入结点的某些时候就破坏了红黑树性质。因此，我们需要对二叉树进行调整让其适合红黑树的特性。
下面我们应该分析什么情况下插入结点能破坏红黑树。
假如我们插入的结点是黑色的，肯定是破坏了二叉树的性质5 。（除非是根节点不破坏。）
但是我们插入的结点是红色的，不一定破坏二叉树的五条性质，为了方便，我们还是将二叉树插入的结点染成红色的比较好。(情况变少)
当我们插入一个红色结点可能破坏那些性质呢？第一条和第三条肯定是不会被破坏的，恒成立的。第五条因为插入的结点是红色的肯定也是成立的。这里可能不成立的是第二条（跟结点是黑的，要是插入的结点就是根结点）和第四条（如果一个结点是红的，它的两个儿子是黑的，因为要是插入的结点的父结点是红的话，那么父父结点就不符合要求了）。
因此，红黑树的结构被破坏就两种情况，不是性质2就是性质4.
性质2好解决，将结点染成黑色的就行了。不做分析。
我们重点分析性质4破坏，我们如何修正。
我们知道性质4被破坏的条件是父节点是红色的。
如图
这里我们分情况讨论 s 的颜色。
第一种情况： s的结点是红色。
这个情况，我们从根到左边的黑色结点数是2 ，右边的黑色结点数是2 。
那么我们如何将其变成从跟到叶子的所有路线的结点数是2还不破坏红黑树呢？
只有下面一种变化才能符合红黑树，这样从根向下就符合红黑树了。
将祖父结点（跟结点）变成红色，p 和s 结点都变成黑节点。
从上面的结果图我们能看出来，根父的颜色不定，可能是红色的，也可能是黑色的，那么我们就应该让根当做被插入的新节点，遍历根父的兄弟的结点的颜色情况情况。这其实就是递归了。
要是每个根父的兄弟结点都是红色的话，那么遍历到根就结束了。将根染成黑色即可。要是根父的兄弟不是红色，那么就应该进入到第二种情况了。
第二种情况：s结点是黑色的。
这种情况不管如何变化，让总结点数不变的情况下，单纯染色根本没有办法让所有结点符合红黑树特性。让从根到叶子的路径含有相同的黑色结点。那么怎么办呢？
我们知道，二叉树可以旋转，旋转可以改变树的结构。
这里我们用根做旋转（左旋或者右旋），结果如下
我们看看旋转结果，结果1，根变成p儿子的一边黑色结点树没有变化。而x的一边黑色结点数量减少了1 。那我们如何让x一边增加1呢？只有如下一种情况，将p染成黑色，根染成红色。
结果2是无法达到我们的要求的，因此我们需要抛弃掉这种情况，让s是黑的时候只能变成结果1 。
结果1所有的情况下都满足红黑树，不需要进行递归了。
这里我们需要看看什么情况下，x结点是p结点的儿子而不是根结点的儿子。这里我们需要看左旋右旋逻辑图了。
因此这里我们总结下结果1 的条件
结果2 就是剩下的。那么要是结果2的情况，我们应该如何处理呢。
那么结果2 在右旋的结构图就很清晰了。如下。p的右儿子是插入的结点x 。
这种情况如何解决呢？
因为x是p的右儿子，所以旋转只能是左旋转。我们以p为根节点旋转。
结果如下
这样就变成了结果1 准备右旋转的的情况了。
同理，情况2的左旋图就变成了结果1准备左旋图的情况了。
【红黑树的原理五234树,红黑树之原理详解】总结
这里上面的方法是算法导论给出的，下面的是自己实现的。
删除操作和二叉树的操作一样，同样的只不过是删除的时候，可能引起对红黑树性质的破坏。
这里把删除二叉树的总结搬过来
这里我们罗列下这三种情况各个删除结点的结构。
二叉树第一种情况：没有儿子的情况。
二叉树第二种情况：只有一个儿子。左儿子或者右儿子。有四种情况
二叉树第三种情况：最多有一个右儿子
我们看出来，第三种情况不是第一种情况，就是第二种情况。因此这里我们只需要研究第一种情况和第二种情况就行了。
当x是红色的时候
将x删除，我们发现红黑树的黑色结点的数量不会发生任何变化。红黑树结构正常
我们发现不管什么条件下，删除红色结点红黑树不会发生任何变化。
这里我们需要讨论下 p 和 s的颜色，我们知道p 和s 分别只有红色和黑色，并且p 和s 不能同时为红色。那么p 和s的组合情况只有三种了。
我们发现不管哪一种情况都删除x的那一支都缺少一个黑色结点。
组合1
组合一通过染色是不可能达到树的平衡的。（有人好说了，把p染成黑色，s染成红色不就行了？我刚开始也犯了这个错误，要是s的两个儿子是红色怎么办呢？红色是不参与节点数计算的。）
因此我们这里直能通过旋转来改变树的结构来看看能不能达到我们的要求。我们以p旋转看看结果如下。
这貌似也不行，因为SL 可能是红色的，违反性质4 。因此我们可以看出来，p是红色的情况下，旋转一次想让红黑树平衡依赖S的两个结点的颜色。
要是p左旋，那么s的左孩子是黑色的就可以。要是p右旋，那么s的右孩子是黑色的就可以了。
因此这里讨论下s的两个孩子的颜色情况。
如果SL 和SR 都是红色怎么处理呢？
单纯的旋转根本不可能让红黑树成立。只能先改变颜色在旋转了。
颜色改变如下
要是SL 和SR都是黑色的情况下
结构图如下
这种结构图 SL SR 都是nil 。这种情况下旋转一下 p就行了。
SR SL只有一个颜色是红色的。如果p的删除分支是左儿子。那么SL 是红色，只能以s先右旋转。这样就变成了 SL SR都是黑色，但是s是红色的情况。是SL ,SR变化成平衡树的中间过程
最后这种情况，和SL SR 都是黑色一样的处理。
组合2
这里我们单纯靠染色是不可能实现树平衡的。因为删除x的结点的一支的结点都是黑色的。没有可以改变的红色结点存在。怎么办呢？我们只能通过旋转将删除的节点的一支上面增加红色结点才行。这里有个s是红色的，我们需要让其到删除结点分支上。
旋转结果
这样组合2删除结点的分支上有红色结点了。到这里我们发现这个地方的树可能违反红黑树了。
违反1：根是红色的话，s是红色违反性质4.
违反2：p结点黑节点数量还是对不上。违反性质5
不过没关系，要是我们能通过染色让树平衡的话，不用再调整树的结构的话，那么组合2也就算是解决了。
貌似通过染色也解决不了这个树平衡的问题，不过违反的红黑树的地方可以减少，我们将s染成黑色，p染成红色。
这里我们发现只有 p删除结点的一支，黑色结点数量少一。正好是组合一的情况。按照组合一的情况做一次旋转就可以解决问题
组合三
这种情况是最复杂的了。我们知道S要是红色，这就是组合2的情况，要是p是红色，那么就是组合1了。那我们想办法怎么让s或者p变成红色的呢？我们先从叶子节点找红色结点，看能不能让s或者p变成红色的。肯定是可以的。不过有一定条件。这里需要依赖SL,SR的颜色了。
当SL,SR都是红色，这种变化只通过改变颜色就可以让s变成红色，变成组合2的情况。
当SL,SR 只有一个红色的时候，通过改变颜色是不能达到要求的。因此我们就需要做旋转来达到要求。
当SL SR 都是黑色。没有红色， p结点一下是不能解决这个问题的。那怎么办呢？这样只能依赖p的父类了。不过这里需要注意的是p本身不平衡，我们这里依赖p的父类的时候，p需要是平衡的。如何平衡p呢？
我们只需要将s变成红色就可以了。p就平衡了。
不过这里注意，p的这一整支的所有分支都是少黑色结点1 的。
这里我们注意到p只有一个儿子。这里我们需要把p当成删除结点x的一个儿子。这样就转换成了x带一个儿子的情况了。这种情况如何平衡树。下面讨论一个孩子的时候包含，暂时不在这里讲解。
先拿一种情况分析 x是p的左儿子，x有一个左儿子
分析L 如果L是黑色的话，肯定是nil 。因此可以将这种只有一个儿子的情况转换成没有儿子的情况。也可以这么说，要是x有儿子，儿子的颜色一定不是黑色。而是红色。如图

文章插图

特别声明：本站内容均来自网友提供或互联网，仅供参考，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。