锐客网

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

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

IT技术删除


这里把删除二叉树的总结搬过来
这里我们罗列下这三种情况各个删除结点的结构 。
二叉树第一种情况：没有儿子的情况 。
二叉树第二种情况：只有一个儿子 。左儿子或者右儿子 。有四种情况
二叉树第三种情况：最多有一个右儿子
我们看出来，第三种情况不是第一种情况，就是第二种情况 。因此这里我们只需要研究第一种情况和第二种情况就行了 。
当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的颜色了 。

推荐阅读


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

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