红黑树
做出了贡献红黑树是一种
与AVL树相比,红黑树保持的高度不变量稍微宽松一些。因为红黑树的高度稍微大一些,所以在红黑树中查找速度会慢一些。然而,更宽松的高度不变式使得插入和删除更快。此外,红黑树之所以流行,是因为它相对容易实现。
这个图像显示了红黑树的表示。注意每一个叶子实际上是一个黑色的空值。这些性质对于证明树的高度不变量是很重要的。
概述
红黑树类似于
- 每个节点要么是红色的,要么是黑色的,这可以保存在内存中的单个位(例如。'红色' = 1,'黑色' = 0)。
- 树的根总是黑色的。
- 所有的叶子都是空的,它们是黑色的。
- 如果一个节点是红色的,那么它的父节点就是黑色的。
- 从一个给定节点到它的任何后代叶节点的任何路径都包含相同数量的黑节点。这有时被称为
black-depth . - 红黑树的高度最多
晚些时候 .
当插入某些节点时,会打乱树的高度不变式,然后使用其节点的当前着色方案重新排列树。一旦树被重新排列,它就会被重新粉刷,以确保着色特性得到保持。
红黑树的高度
证明红黑树的高度特别重要因为红黑树的高度是计算它的渐近复杂度和性能的依据。这是一种方法。
首先想象一棵有高度的红黑树
- 2个黑人孩子,在这种情况下,黑人父母仍然有
2 的孩子。 - 1个黑子结点和1个红子结点,这时黑父结点就有了
3. 的孩子。 - 2个红色的子结点,此时黑色的父结点就有了
4 的孩子。
下面是一个合并过程的图形示例(假设任意偏离的箭头指向一个黑节点)。
现在,我们将所有的红结点合并到它们的父结点中。这意味着任何黑结点现在都有
如你所见,每个黑结点有2、3或4个子结点。
这棵新树的高度,
树的叶子数正好等于
操作
在红黑树中,有两种操作可以改变树的结构,插入和删除。这些变化可能包括节点的添加或删除、节点颜色的改变或通过旋转重新组织节点。通过展示插入过程的各种情况和算法,我们可以推断出关于删除的相同情况。
插入一个节点需要首先在树中搜索以找到合适的位置。然后将节点作为
1)案例1
在第一种情况下,我们插入的节点是红色的,它的父节点是红色的,它的父节点的兄弟节点也是红色的。我们知道被插入节点的祖父结点将是黑色的,所以我们所要做的就是将被插入节点的祖父结点的颜色与被插入节点的父结点及其兄弟结点的颜色进行切换。但是,这种情况可能需要通过树的根继续修复,因为插入节点的祖父母可能有一个红色的父节点。
下面的图表展示了这种情况。被插入的节点被标记为“INSERT”。左边的树显示了案例,右边的树显示了它的纠正。
2)第二种情况
情况2发生在节点的父节点是红色的,但是父节点的兄弟节点是黑色的,并且节点的值在其父节点和祖父节点之间。
我们处理情况2的方法是旋转到情况3。旋转有两种,左旋转和右旋转。情况2使用左旋转,因为所涉及的节点是逆时针旋转的。下图显示了情况2中的旋转。
可以看到,在标签为“ROTATE”的节点上执行了左旋转。
3)案例3
病例3涉及祖父母的右旋转。在下面的图形中,要围绕它旋转的节点被标记为“ROTATE”,插入的节点被标记为“INSERT”,第三个节点被标记为“MIDDLE”,以显示旋转结束后的位置。
删除,如上所述,以完全相同的方式工作。一旦从树中取出一个节点,树就会出现上述三种情况中的任何一种。那么问题就以同样的方式解决了。
渐近的复杂性
我们知道在插入或删除事件中需要做什么。那么每个操作的运行时是多少?
我们证明了 在情况1中,我们需要退回到树之外,重新给节点上色。这个过程也需要 在情况2和3中,我们分别进行1或2次旋转。在这一点上,我们终止。这些情况都是常数时间操作。我们知道插入和删除需要 在红黑树中搜索和任何平衡二叉树一样, 参见: *平摊分析
平均
空间
搜索
遍历
*
插入
删除
Python实现
一个python实现可能看起来像这样。注意,此实现仅用于学术目的,并不能保证任何功能。
基本的节点和树类看起来像这样。每个节点都需要跟踪其子节点、父节点、颜色和键。的
1 2 3 4 5 6 7 8 9 10 11 |
|
使用二进制搜索可以很容易地实现搜索功能。注意,此实现假设没有两个键具有
1 2 3 4 5 6 7 8 |
|
insert函数的行为与搜索类似,因为它会在树中找到新节点应该去的位置。但是,它需要调用一些函数来确保之后树被修复。
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
的
12 34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
|
这是
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
参考文献
- 伯内特,C。
维基百科“红-黑”树 .2016年4月25日,从https://en.wikipedia.org/wiki/Red-black_tree