锐客网

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

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

IT技术删除


所以为了防止我们的二叉搜索树退化成一个链表，就产生了 平衡二叉树。平衡二叉树 可以保证它的左右两个子树的高度差不会超过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的父节点同样也是其祖父节点的左孩子，此时以祖父节点为支点进行右旋；

推荐阅读


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

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