java红黑树删除源代码 java的红黑树

红黑树(Red-black tree)

树 是一种 抽象数据类型 ，或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的 数据集合 。

红黑树 是一种自平衡二叉查找树，典型的用途是实现 关联数组 ，它是复杂的，但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的 O(log n ) 时间内做查找，插入和删除，这里的 n 是树中元素的数目。

一个由n个节点随机构成的二叉查找树的高度为(log n ).证明如下java红黑树删除源代码：

而时间复杂度是以某个基础数据操作的重复次数作为量度。红黑树的是二叉搜索树，左子树上所有节点的值均小于他的根节点的值，右子树上所有节点均大于根节点的值，左右子节树相对根节点按大小分布。如果把每次节点值的比较看成基础数据操作，那么最差的查找情况是一直查找到高度最大的根节点，那么查找的时间复杂度即与高度成正比，可表示成 O(log n ) 。

简单java红黑树删除源代码了解了红黑树的字面定义，下面动手感受下红黑树的相关操作。当你插入或者删除一个节点时，可能会破坏红黑树的性质，所以需要对树节点进行重新着色或者旋转，来保持红黑树的结构。首先看下二叉树的旋转。

假设pivot节点不为空，其右子树不为空，那么左旋即是：使pivot的右孩子Y为子树的根，pivot节点为子树根节点的左孩子，pivot左孩子、Y节点的右孩子不改变，Y节点左孩子变为pivot节点右孩子。

假设pivot节点不为空，其左子树不为空，那么右旋：使pivot的左孩子Y为子树的根，pivot节点为子树根节点的右孩子，pivot的右孩子、Y节点的左孩子不变，Y节点的右孩子变为pivot节点的左孩子。

实战演练之增加、删除节点时，如何保证红黑树的性质不被破坏。

往一个空的红黑树中，依次插入数据：12 1 9 2 0 11 7 19 4

节点为根节点，所以为黑色，两个null节点为黑色节点。

按照二叉搜索树的逻辑，9小于12、大于1，应该是1节点的右孩子。但，新增的两个NIL节点已经使得12，1，9，NI这条路径的黑色节点至少为两个，而12，NIL这条路径的黑色节点只有两个。所以要对1节点进行左旋，9节点变为12节点的左孩子，发现问题还是存在。继续，对12节点进行右旋，9节点为根节点，1、12分别为9节点的左右孩子。尝试着色，9节点必须为黑色，而1，12节点可以为红色，也可以为黑色。

0节点直接作为1节点的左孩子，保持跟2节点相同的颜色即可。左右子树依旧保持平衡。

从二叉查找树的性质看，7节点作为2节点的右孩子即可。这时来分析着色问题，我们先看最短路径的黑色分布，9，12，NIL这条路径，有三个黑色节点，以此为参考，尝试改变9节点左子树的着色。目前最长的路径是9，1，2，7，NIL这条路径。保持三个黑色节点的话，9跟NIL已经为黑色节点，而红色节点又不能挨着，所以只能是1为红色节点，2为黑色节点，7为红色节点。那么9，1，0，NIIL这条路径，0就要为黑色节点。调整完毕。

19节点作为12节点的右孩子，与左孩子保持一样的红色即可。

4节点应该作为7节点的左子树，无论着什么颜色，以1节点为根节点的子树，都要破坏红黑性质。所以应该进行旋转。先以7为根节点进行一次右旋，再以2为根节点进行一次左旋。尝试着色即可。

类似插入节点的分析、总结，删除节点也可以针对每种场景找到固定的着色方法，就像玩一个游戏，有自己的推理跟玩法。我先做个PPT，这块稍后补充。

所有的插入、删除都是有限个情况，基于插入、删除的情况分析，即可编写算法生成红黑树，使其在固定的业务场景中发挥红黑树稳定操作效率的特色了。

在 计算机科学 中， AVL树 是最先发明的 自平衡二叉查找树 。在AVL树中任何节点的两个 子树 的高度最大差别为一，所以它也被称为 高度平衡树 。查找、插入和删除在平均和最坏情况下都是 O （log n ）。增加和删除可能需要通过一次或多次 树旋转 来重新平衡这个树。

节点的 平衡因子 是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

不提问题的码农不是好程序员。自己写完了红黑树的简单剖析，感觉还是只懂皮毛，没有从触碰到算法的核心内容。所以，不妨留几个小问题，担心自己脑子生锈或者没事想玩手机的时候，再提笔研究下红黑树。

教你初步了解红黑树

算法的时间复杂度和空间复杂度-总结

红黑树从头至尾插入和删除

AVL树

红黑树C源码实现与剖析

Echo

8 Nov，2016

相关问答

Q1: （转）红黑树

红黑树是平衡二叉树的一种，是目前使用最多的一种树结构。红黑树通过对节点的染色以及巧妙的动态调整，使得树保持适度平衡。

红黑树可以保证：在每次插入或删除操作之后的重平衡过程中，全树的拓扑结构的更新仅涉及常数个节点。尽管在最坏的情况下需要对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次染色，调整完成

（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，继续调整

红黑的删除操作的总共耗时不会超过O(logn)次。

参考：

《数据结构第三版》

Q2: 红黑树——删除、双黑缺陷

首先按照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的红黑树的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。