锐客网

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

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

IT技术删除


所有的插入、删除都是有限个情况，基于插入、删除的情况分析，即可编写算法生成红黑树，使其在固定的业务场景中发挥红黑树稳定操作效率的特色了 。
在 计算机科学 中， AVL树 是最先发明的 自平衡二叉查找树。在AVL树中任何节点的两个 子树 的高度最大差别为一，所以它也被称为 高度平衡树。查找、插入和删除在平均和最坏情况下都是 O （logn ） 。增加和删除可能需要通过一次或多次 树旋转 来重新平衡这个树 。
节点的 平衡因子 是它的左子树的高度减去它的右子树的高度（有时相反） 。带有平衡因子1、0或 -1的节点被认为是平衡的 。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树 。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来 。
不提问题的码农不是好程序员 。自己写完了红黑树的简单剖析，感觉还是只懂皮毛，没有从触碰到算法的核心内容 。所以 ， 不妨留几个小问题，担心自己脑子生锈或者没事想玩手机的时候，再提笔研究下红黑树 。
教你初步了解红黑树
算法的时间复杂度和空间复杂度-总结
红黑树从头至尾插入和删除
AVL树
红黑树C源码实现与剖析
Echo
8 Nov，2016
（转）红黑树红黑树是平衡二叉树的一种 ， 是目前使用最多的一种树结构 。红黑树通过对节点的染色以及巧妙的动态调整，使得树保持适度平衡 。
红黑树可以保证：在每次插入或删除操作之后的重平衡过程中，全树的拓扑结构的更新仅涉及常数个节点 。尽管在最坏的情况下需要对O(logn)个节点冲染色，但是就分摊意义而言，仅为O(1)个 。
红黑树的适度平衡标准：任一节点左、右子树的高度相差不得超过两倍 。
红黑树的条件：
（1）树根为黑色
（2）外部节点均为黑色
（3）其余节点若为红色 ， 则其孩子节点必为黑色
（4）从任一外部节点到根节点的沿途，黑节点的数目相等
满足上面四个条件的二叉搜索树，为红黑树 。
红黑树与4阶B树之间存在密切的联系 ， 经过适当的转换之后，两者是等价的 。
红黑树的插入操作：
（1）在红黑树中查找要插入的节点X，若允许插入节点X，则在该位置插入节点X
（2）节点X染为红色
（3）判断此时红黑树是否满足条件（3），若满足则插入操作完成，否则进行调整
红黑树插入新节点导致的红黑树调整，称为双红修正 ， 其中双红修正有两种情况：RR-1和RR-2 。
RR-1 u为黑的情况：
1 ~ 2次旋转，2次染色，调整随之完成
RR-2 u为红的情况：
0次旋转，3次染色，可能导致上层节点的再次双红，需要继续调整 ， 最多O(logn)次
红黑树的删除操作：
（1）找到需要删除的节点X ， 若有 ， 则删除
（2）判断删除之后的红黑树是否满足条件（3）与（4），若不满足，则进行调整
红黑树删除操作导致的红黑树调整，为双黑调整 ， 双黑调整有四种情况 。
（1）BB-1，黑s有红子t：
1 ~ 2次旋转，3次染色，调整完成
【java红黑树删除源代码 java的红黑树】（2）BB-2-R，黑s无红子，p红：
0次旋转，2次染色 ， 调整完成
（3）BB-2-B，黑s无红子 ， p黑：
0次旋转，1次染色，必然会导致再次双黑 ， 但上升一层，继续调整
（4）BB-3，红s：
1次旋转，2次染色，转化为BB-1或者BB-2-R ， 继续调整

推荐阅读


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

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