锐客网

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

java红黑树删除源代码 java的红黑树( 三 )

IT技术删除


红黑的删除操作的总共耗时不会超过O(logn)次 。
参考：
《数据结构第三版》
红黑树——删除、双黑缺陷首先按照BST常规算法，执行：r = removeat(x,_hot)
x由孩子r接替 //另一孩子记作w（即黑的NULL）
条件1和2依然满足，但3和4不一定 //在原树中，考查x与r
若二者之一为红，则3和4不难满足
双黑缺陷
若x与r均黑double-black
摘除x并代之以r后，全树黑深度不再统一，原B-树中x所属节点下溢
在新树中，考查r的父亲p = r-parent ，  r的兄弟s = r==p-lc ? p-rc : p-lc
以下分四种情况处理
BB-1：s为黑，且至少有一个红孩子t
3+4重构：t、s、p重命名为a、b、c
r保持黑；a和c染黑；b继承p的原色
如此，红黑树性质在全局得以恢复——删除完成 //zig-zag等类似
BB-2R：s为黑，且两个孩子均为黑；p为红
r保持黑；s转红；p转黑
在对应的B-树中，等效于下溢节点与兄弟合并
红黑树性质在全局得以恢复
失去关键码p之前，上层节点不会继续下溢 ， 合并之前，在p之左或右侧还必有（问号）关键码 。必为黑色，有且仅有一个
BB-2B：s为黑，且两个孩子均为黑；p为黑
s转红；r与p保持黑
BB-3：s为红（其孩子均为黑）
zag(p)或zig(p)；红s转黑 ， 黑p转红
既然p已转红 ， 接下来绝不会是情况BB-2B，而只能是BB-1或BB-2R
复杂度
红黑树的每一删除操作都可在O(logn)时间内完成
其中，至多做
1.O(logn)次重染色
2.一次“3+4”重构
3.一次单旋
关于java红黑树删除源代码和java的红黑树的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站 。

推荐阅读


上一篇：服务器不支持ssl，服务器不支持ssl连线

下一篇：如何创建单位微信视频号呢，单位如何申请微信视频号