`

红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名,Adelson

阅读更多
红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名,Adelson-Velskii和Landis,将其称为AVL-树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持)。

红黑树的定义如下:


满足下列条件的二叉搜索树是红黑树

    * 每个结点要么是“红色”,要么是“黑色”(后面将说明)
    * 所有的叶结点都是空结点,并且是“黑色”的
    * 如果一个结点是“红色”的,那么它的两个子结点都是“黑色”的
    * (注:也就是說,如果結點是黑色的,那么它的子節點可以是紅色或者是黑色的)。
    * 结点到其子孙结点的每条简单路径都包含相同数目的“黑色”结点
    * 根结点永远是“黑色”的

之所以称为红黑树的原因就在于它的每个结点都被“着色”为红色或黑色。这些结点颜色被用来检测树的平衡性。但需要注意的是,红黑树并不是平衡二叉树,恰恰相反,红黑树放松了平衡二叉树的某些要求,由于一定限度的“不平衡”,红黑树的性能得到了提升。

从根结点到叶结点的黑色结点数被称为树的“黑色高度”(black-height)。前面关于红黑树的性质保证了从根结点到叶结点的路径长度不会超过任何其他路径的两倍。

我们来解释一下这个结论。考虑一棵黑色高度为3的红黑树:从根结点到叶结点的最短路径长度显然是2(黑-黑-黑),最长路径为4(黑-红-黑-红- 黑)。由于性质4,不可能在最长路经中加入更多的黑色结点,此外根据性质3,红色结点的子结点必须是黑色的,因此在同一简单路径中不允许有两个连续的红色结点。综上,我们能够建立的最长路经将是一个红黑交替的路径。

由此我们可以得出结论:对于给定的黑色高度为n的红黑树,从根到叶结点的简单路径的最短长度为n-1,最大长度为2(n-1)。

插入和删除操作中,结点可能被旋转以保持树的平衡。红黑树的平均和最差搜索时间都是O(log2 n)。Cormen [2001]给出了对于这一结论的证明。在实际应用中,红黑树的统计性能要好于平衡二叉树,但极端性能略差。

红黑树中结点的插入过程

插入结点的过程是:


    * 在树中搜索插入点
    * 新结点将替代某个已经存在的空结点,并且将拥有两个作为子结点的空结点
    * 新结点标记为红色,其父结点的颜色根据红黑树的定义确定;如果需要,对树作调整

注意 空结点和NULL指针是不同的。在简单的实现中,可以使用作为“监视哨”,标记为黑色的公共结点作为前面提到的空结点。

给一个红色结点加入两个空的子结点符合性质4,同时,也必须确保红色结点的两个子结点都是黑色的(根据性质3)。尽管如此,当新结点的父结点时红色时,插入红色的子结点将是违反定义的。这时存在两种情况。

红色父结点的兄弟结点也是红色的

例如下面的情况(X是希望插入的结点,

简单地对上级结点重新着色将解决冲突。当结点B被重新着色之后,应该重新检验更大范围内树结点的颜色,以确保整棵树符合定义的要求。结束时根结点应当是黑色的,如果它原先是红色的,则红黑树树的黑色高度将递增1。

红色父结点的兄弟结点是黑色的

这种情形比较复杂,如下图:

重新对结点着色将把结点A变成黑色,于是,树的平衡将被破坏,因为左子树的黑色高度将增加,而右子树的黑色高度没有相应地改变。如果我们把结点B着上红色,那么左右子树的高度都将减少,树依然不平衡。此时,继续对结点C进行着色将导致更糟糕的情况,左子树黑色高度增加,右子树黑色高度减少。为了解决问题,需要旋转并对树结点进行重新着色。这时算法将正常结束,因为子树的根结点(A)被着色为黑色,同时,不会引入新的红-红冲突。

结束插入过程

插入结点时,可能会需要重新着色,或者旋转,来保持红黑树的性质。如果旋转完成,那么算法就结束了。对于重新着色来说,我们会在子树的根留下一个红色结点,于是需要继续向上对树进行修整,以保持红黑树的性质。最坏情况下,我们将不得不对到树根的所有路径进行处理。插入的时间复杂度为O(log2 n)。删除结点的时间复杂度与此类似。

结点的删除

红黑树的结点删除情况要比插入复杂一些。我们可以把实际的删除操作分成3种情况(先不讨论颜色),其中被删除的结点用紫色标记,蓝色表示任意颜色的结点,可能是红色,也可能是黑色:

情况a: 被删除的结点没有子结点(两个子结点都是空结点)

原先属于X的空结点被A“继承”。如果被删除结点是黑色结点,则可能造成树的黑色高度变化。

情况b: 有一个子结点

B结点取代原X结点的位置。如果被删除的结点是黑色结点,则可能造成树的黑色高度发生变化;如果B是红色结点,还可能需要重新着色。

情况c: 有两个子结点

这种情形比较复杂。需要将X和它的左子树中的键值最大的结点进行交换。这通常会导致重新着色,对树的黑色高度的改变,以及随之而来的旋转。

需要说明的是,仅仅删除结点是不够的,因为此后很可能还需要对树进行重新着色。如果删除的是红色结点,那么没有关系,因为这不会影响树的黑色高度;而如果删除的是黑色结点,事情就没那么简单了。需要把受到影响(移动或交换)的结点标记为黑色,如果它原来已经是黑色的,那么需要标记为“双黑”(双黑,或double-black是许多英文资料中提及的一个概念。简单地说,标记为“双黑”意味着需要对周围的红色结点进行“抹黑 ”处理)。

包含“双黑”结点显然不符合红黑树的要求,因此必须消除这种情况。出现“双黑”的情况可以分为4种:

1、双黑结点的兄弟结点是红色的

2、双黑结点的兄弟是黑色的,并且它的兄弟有两个黑色的子结点

3、双黑结点的兄弟是黑色的,并且,它的兄弟的左、右子结点分别是红色和黑色

4、双黑结点的兄弟是黑色的,并且,它的兄弟的右子结点是红色的

很显然,上述四种情况包括了可能的所有状况。

处理双黑结点的基本思想是进行“色彩补偿”。换言之,将邻近的红色结点变为黑色,同时,此双黑结点也“还原”为黑色。

总结

红黑树引入了“颜色”的概念。引入“颜色”的目的在于使得红黑树的平衡条件得以简化。正如著名的密码学专家Bruce Schneier所说的那样,“Being Partly balanced can be good enough”,红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。

红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。当然,还有一些更好的,但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡,但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高。

当然,红黑树并不适应所有应用树的领域。如果数据基本上是静态的,那么让他们待在他们能够插入,并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的,例如,做一个哈希表,性能可能会更好一些。

在实际的系统中,例如,需要使用动态规则的防火墙系统,使用红黑树而不是散列表被实践证明具有更好的伸缩性。

 

分享到:
评论

相关推荐

    红黑树: 理论与实现

    它的统计性能要好于平衡二叉树(有些书籍根据作者姓名,Adelson-Velskii和Landis,将其称为AVL-树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的...

    二叉搜索树,红黑树,AVL平衡树,B树

    二叉搜索树(Binary Search Tree,BST)是一种特殊的二叉树数据结构,它的每个节点都包含一个键(key)、一个关联的值、一个指向左子树的指针和一个指向右子树的指针。在二叉搜索树中,对于任意节点: 1. 所有左...

    平衡二叉树可视化

    红黑树则是一种弱平衡的二叉查找树,它允许节点不平衡,但通过颜色属性(红色或黑色)来保证任何节点到每个叶子节点的最长路径不超过最短路径的两倍,同样保持高效的查找性能。 在Windows编程中实现平衡二叉树的...

    平衡二叉树数据结构课程设计

    平衡二叉树是一种特殊的二叉树数据结构,它在保持二叉查找树特性的同时,通过特定的结构调整策略,确保了树的高度平衡。这样的设计使得在平衡二叉树中执行插入、删除和查找等操作的时间复杂度可以保持为O(log n),...

    高度平衡的二叉树.

    **红黑树**也是一种高度平衡的二叉搜索树,它通过在每个节点上附加一个代表颜色的属性来维护平衡。红黑树的平衡性质体现在以下五条规则: 1. **每个节点要么是红色,要么是黑色**。 2. **根节点是黑色**。 3. **每...

    广工数据结构实验——平衡二叉树

    在这个实验中,`平衡二叉树数据结构实验.cpp`很可能是实现平衡二叉树(可能是AVL树或红黑树)的C++源代码。它可能包含了基本的二叉树操作(如插入、删除和查找)以及平衡调整算法的实现。源代码可以帮助我们理解如何...

    平衡二叉树的操作演示

    平衡二叉树是一种特殊的二叉树数据结构,它在保持二叉搜索树特性的同时,通过特定的结构调整,确保了左右子树的高度差不超过1。这种平衡特性使得在平衡二叉树上的常见操作如插入、查找、删除等可以以近似O(log n)的...

    数据结构:实现平衡二叉树的各种算法-C/C++代码类资源

    在IT领域,数据结构是计算机科学的基础,而平衡二叉树是其中一种高效的数据存储和检索结构。平衡二叉树,顾名思义,是一种保持树的高度平衡的二叉搜索树,它确保了任何节点的两个子树的高度差不超过1。这种特性使得...

    2015广工数据结构实验--平衡二叉树(包含源码和实验报告).zip

    平衡二叉树是一种特殊的二叉树数据结构,它在保持二叉查找树特性的同时,通过特定的结构调整策略,使得树的高度始终保持平衡,从而确保了在插入、删除和查找操作中的效率。这种数据结构在信息技术领域有着广泛的应用...

    二叉排序树和平衡二叉树计算程序

    在"VC二叉排序树和平衡二叉树计算程序"中,很可能是包含了用C++(Visual C++,简称VC)编写的程序,用于实现二叉排序树和平衡二叉树(如AVL树或红黑树)的基本操作。这样的程序通常会包括节点结构定义、插入、删除和...

    动态打印平衡二叉树

    动态打印平衡二叉树是一种高级的数据结构操作技术,主要涉及二叉平衡树(特别是AVL树或红黑树)的概念,以及如何有效地在保持平衡的同时进行插入、删除、查找等操作,并能优雅地呈现其结构。下面将详细介绍这些知识...

    平衡二叉树.zip 平衡二叉树的学习与思考

    平衡二叉树是一种特殊的二叉树数据结构,它在保持二叉查找树特性的同时,通过特定的结构调整,确保了树的高度平衡。这种平衡状态使得在平衡二叉树中执行插入、删除和查找操作的效率非常高效,通常为O(log n)时间...

    二叉树-基于C++实现的平衡二叉树.zip

    C++实现平衡二叉树时,我们需要定义一个二叉树节点结构体,包括节点值、颜色(对于红黑树)以及指向左子节点和右子节点的指针。接着,我们需要实现基本操作如插入、删除和查找,以及在这些操作后进行的平衡调整(如...

    C语言平衡二叉树.zip

    2. 红黑树:红黑树是一种自平衡的二叉查找树,由Rudolf Bayer在1972年提出。它允许节点是红色或黑色,并遵循五个性质:每个节点要么是红色要么是黑色;根节点是黑色;所有叶子节点(NIL节点)是黑色;如果一个节点是...

    平衡二叉树的实现广工数据结构课设源码加报告

    平衡二叉树是数据结构中的一个重要类型,它是一种特殊的二叉树,能够保持左右子树的高度差不超过1,从而确保了搜索、插入和删除等操作的时间复杂度为O(log n)。在这个广工(广东工业大学)数据结构课程设计中,学生...

    平衡二叉树的详细实现,C++语言

    另一种常见的平衡二叉树是红黑树,它不保证完全平衡,但保证了任意节点到其每个叶子节点的最长路径不超过最短路径的两倍。红黑树的规则包括:节点可以是红色或黑色;根节点是黑色;所有叶子节点是黑色;每个红色节点...

    平衡二叉树

    平衡二叉树是一种特殊的二叉树数据结构,它在保持二叉查找树特性的同时,通过特定的结构调整使得左子树和右子树的高度差不超过1,从而保证了数据的高效检索。这种数据结构的设计目标是优化查找、插入和删除操作的...

    基于java实现的平衡二叉树源码.zip

    平衡二叉树是一种特殊的二叉树数据结构,它在任何时候都保持了左右子树的高度差不超过1,从而保证了在插入和删除操作后的查找、插入和删除效率始终保持在一个较高的水平,通常为O(logn)。在Java中实现平衡二叉树,...

    平衡二叉树 java源码.zip

    平衡二叉树是一种特殊的二叉树数据结构,它在任何时候都保持着左右子树的高度差不超过1,这使得在树中的所有操作(如插入、删除和查找)都能在O(log n)的时间复杂度内完成。在Java中实现平衡二叉树,通常会用到AVL树...

    高度平衡的二叉树.zip

    高度平衡的二叉树是一种特殊的二叉树结构,它的特点是左右子树的高度差不超过1,这样的树在数据结构和算法领域具有重要的应用价值。在计算机科学中,平衡二叉树的目的是为了保持数据的高效检索,尤其是在大规模数据...

Global site tag (gtag.js) - Google Analytics