锐客网

  1. 首页 > 睿知 > it技术 > >

红黑树的左旋java代码 红黑树csdn( 二 )

IT技术删除


下面我们应该分析什么情况下插入结点能破坏红黑树 。
假如我们插入的结点是黑色的，肯定是破坏了二叉树的性质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准备左旋图的情况了 。
总结
这里上面的方法是算法导论给出的，下面的是自己实现的 。
删除操作和二叉树的操作一样，同样的只不过是删除的时候，可能引起对红黑树性质的破坏 。

推荐阅读


上一篇：数据结构c语言版视频，数据结构c语言版视频

下一篇：耳机单反直播教程，用单反直播怎么设置