锐客网

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

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

IT技术删除


如果X相对于父节点的左右位置和父节点相对于祖父节点的左右位置不同，则以X的父节点为支点，进行旋转，旋转方向与X相对于父节点左右位置相反 。例如：X为其父节点的左孩子，X的父节点为祖父节点的右孩子，此时以X的父节点为支点进行一次右旋 。
在红黑树中删除节点 ， 肯定要涉及到要删的这个节点是红色的还是黑色的 。删除红色比较简单 ， 我们先说一下删除红色节点 。
删除节点要考虑这个节点所处的位置 ， 所以我们罗列一下红色的节点所有可能的位置情况 。
你可能会发现为什么少了一种情况？它不能只有左子树或者只有右子树吗?我们可以看下图:
很明显，这四种情况都不符合红黑树的规则 ， 所以根本不会出现这种情况 。
而对于既有左子树也有右子树的情况 。我们可以先和普通的二叉搜索树的删除操作一样，将它与前驱或者后继交换一下。它就又变成第一种情况——成为了一个叶子节点 。所以我们只需考虑当它是叶子节点的情况 。
接下来我们看一下当要删除的节点是黑色的时候应该怎么办 。
同样我们列一下节点位置可能的情况：
第三种情况和删除红色节点时的处理方法一样 ， 可以转换成第一种或第二种情况，所以我们只关心前两种情况 。
当要删除的黑色节点只有一个子树时：
最后我们看一下最难处理的一种情况 。
要删除的黑色节点是叶子节点时：
情况1：待删除黑色节点20 ， 它的兄弟节点为红色 。
操作方法为：将远侄子节点变黑，兄弟节点与父亲节点互换颜色，最后以父节点为支点进行 左旋。(为什么是左旋？因为待删除的20是左孩子，我们要将左子树长度拉长 ， 将它沉下来，使它变成多余的节点好删除它，如果它是右孩子，则进行右旋)
操作后如下图就完成了 。
情况3：待删除黑色节点20 ， 它的兄弟节点为黑色 ， 但它没有红色的远侄子节点(即nil点，记住，nil点算黑色) ， 只有红色的近侄子节点 。
操作后如下图:
此时有了红色的远侄子，就满足了情况2，再按情况2进行一次操作就完成了 。
情况4：待删除黑色节点20，它的兄弟节点为黑色，远侄子、近侄子节点都没有 。(即两个nil节点，nil节点算黑色)
我们将上图红黑树按流程演示一下:
第一步按情况4操作 ， 将55变红 。并将父节点50看做当前节点 ， 继续操作 。
此时有关红黑树的知识就说完了 。
以上所有内容都为自己查阅资料学习理解之后手敲的 。尽量得采用通俗易懂的描述和解释让读者更明白 。27张图都是自己亲自画的，花费了四天才写完，如果觉得写的还可以，麻烦点亮喜欢支持一下，如果还是不懂，可以下方留言QQ等联系方式，我亲自告诉你 。
在linux操作系统内核实现里经常使用的红黑树在linux操作系统内核实现里经常使用的红黑树如下红黑树的左旋java代码：
二叉树红黑树的左旋java代码，按中序遍历后为一递增数组红黑树的左旋java代码，自平衡意味着树的高度有一个上限，对于红黑树，其为2log(n+1)，所以时间复杂度为最差为Olog(n) 。
赋予二叉搜索树自平衡特性的方法有多种，红黑树通过一下4条约束实现自平衡:
Every node is either red or black.
All NIL nodes (figure 1) are considered black.
A red node does not have a red child.
Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.
其中根节点为黑色 。

推荐阅读


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

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