锐客网

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

红黑树的左旋java代码 红黑树csdn

IT技术删除

有关红黑树的java程序 ， 编译成功但运行不出结果 。java8不是用红黑树来管理hashmap，而是在hash值相同的情况下（且重复数量大于8） ， 用红黑树来管理数据 。红黑树相当于排序数据 。可以自动的使用二分法进行定位 。性能较高 。
一般情况下，hash值做的比较好的话基本上用不到红黑树 。
红黑树-算法导论 这个周看算法导论 ， 看到红黑树 ， 看的我云里雾里绕啊 。虽然最后看懂了 ， 据我估计 ， 要是过一个星期不看保证忘干净，因此决定写篇博客记录下红黑树 。
红黑树是二叉树的一种，所以学习红黑树必须先搞懂二叉树 。
如图，一颗二叉树是按照结点（二叉树结构）组成的 。每个结点可以用链表结构标示 。每个结点都应该有left rightp，他们分别指向左儿子，右儿子和父结点 。每个结点还应该有个关键字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 代替呢 。因此如下结构 。
旋转应该是二叉树的性质，只是普通二叉树没必要旋转 。红黑树需要旋转来平衡树结构 。
结果如下 。
右旋的过程只是相反而已 。
左旋的作用是将右儿子变成父结点 。
右旋的作用是将左儿子变成父结点 。
这样变化有什么用处呢？
我们知道，红黑树就是二叉树，因此向二叉树中插入数据没有啥区别 。只是不过，当我们插入结点的某些时候就破坏了红黑树性质 。因此，我们需要对二叉树进行调整让其适合红黑树的特性 。

推荐阅读


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

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