数据结构与算法之美_25_红黑树(上):为什么工程中都用红黑树这种二叉树?

lickylin 2020-04-22

二叉查找树是最常用的一种二叉树,它支持快速插入、删除、查找操作,各个操作的时间复杂度跟树的高度成正比,理想情况下,时间复杂度是 O(logn)。

不过,二叉查找树在频繁的动态更新过程中,可能会出现数的高度远大于 log2^n 的情况,从而导致各个操作的效率下降。极端情况下,二叉树会退化为链表,时间复杂度会退化到 O(n)。要解决这个复杂度退化问题,就需要设计一种平衡二叉查找树,也就是我们今天讲的这种数据结构。

在工程中,很多用到平衡二叉查找树的地方都会用红黑树。为什么呢?

什么是“平衡二叉查找树”?

平衡二叉树的严格定义是:二叉树中的任意一个节点的左右子树的高度相差不能大于 1。

从这个定义上看,完全二叉树、满二叉树其实都是平衡二叉树,但是非完全二叉树也有可能是平衡二叉树。

数据结构与算法之美_25_红黑树(上):为什么工程中都用红黑树这种二叉树?

平衡二叉查找树不仅满足上面平衡二叉树的定义,还满足二叉查找树的特点。最先被发明的平衡二叉查找树是 AVL 树,它严格符合平衡二叉树的定义,即任何节点的左右子树的高度相差不超过 1,是一种高度平衡的二叉查找树。

但是很多平衡二叉查找树其实并没有严格符合上面的定义,比如红黑树,它从根节点到各个叶子节点的最长路径,有可能会比最短路径大一倍。

对于平衡二叉查找树的概念,我们要从这个数据结构的由来,去理解“平衡”的意思。

发明平衡二叉查找树这类数据结构的初衷是,解决平通二叉查找树在频繁的插入、删除等动态更新的情况下,出现时间复杂度退化的问题。

所以,平衡二叉树中“平衡”的意思,其实就是让整棵树左右看起来比较“对称”、比较“平衡”,不要出现左子树很高、右子树很低的情况。这样就能让整棵树的高度相对来说低一些,相应的插入、删除、查找等操作的效率高一些。

所以,如果我们现在设计一个新的平衡二叉查找树,只要树的高度不比 log2^n 大很多(比如树的高度仍然是对数量级的),尽管它不符合我们前面讲的严格的平衡二叉查找树的定义,但是仍然可以说,这是一个合格的平衡二叉查找树。

如何定义一棵“红黑树”?

平衡二叉查找树有很多,比如 Splay Tree(伸展树)、Treap(树堆)等,但是我们提到平衡二叉查找树,听到的基本上都是红黑树。

红黑树英文是“Red-Black Tree”,简称 R-B Tree。它是一种不严格的平衡二叉查找树。

红黑树中的节点,一类被标记为黑色,一类被标记为红色。除此之外,一棵红黑树还要满足一下几个要求:

  • 根节点是黑色的;
  • 每个叶子节点都是黑色的空节点(NIL),即叶子节点不存储数据;
  • 任何相邻的节点都不能同时为红色,即红色节点是被黑色节点隔开的;
  • 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点;

这里的第二点要求“叶子节点都是黑色的空节点”,它主要是为了简化红黑树的代码实现而设置的,下一节会讲到。这一节我们暂时不考虑这一点,所以,在画图和讲解时,将黑色的、空的叶子节点都省略掉了。

数据结构与算法之美_25_红黑树(上):为什么工程中都用红黑树这种二叉树?

为什么说红黑树是“近似平衡”的?

平衡二叉查找树的初衷,是为了解决二叉查找树因为动态更新导致的性能退化问题。所以,“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。

二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树(满二叉树或完全二叉树)的高度大约是 log2^n,所以如果要证明红黑树是近似平衡的,只需要分析,红黑树的高度是否比较稳定地趋近 log2^n 就好了。

首先,如果将红色节点从红黑树中去掉,那单纯包含黑色节点的红黑树的高度是的多少呢?

红色节点删除之后,有些节点就没有父节点了,它们会直接这些节点的祖父节点(父节点的父节点)作为父节点。所以,之前的二叉树就变成了四叉树。

数据结构与算法之美_25_红黑树(上):为什么工程中都用红黑树这种二叉树?

红黑树的定义中有一条:从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。我们从四叉树中取出某些节点,放到叶子节点位置,四叉树就变成了完全二叉树。所以,仅包含黑色节点的四叉树的高度,比包含相同节点个数的完全二叉树的高度还要小。

完全二叉树的高度近似 log2^n,这里的四叉“黑树”的高度要低于完全二叉树,所以,去掉红色节点的“黑树”的高度也不会超过 log2^n。

现在,我们知道了只包含黑色节点的“黑树”的高度,那我们现在把红色节点加回去。

在红黑树中,红色节点不能相邻,即有一个红色节点就要至少有一个黑色节点,将它跟其他红色节点隔开。红黑树中包含最多黑色的路径不会超过 log2^n,所以加入红色节点之后,最长路径不会超过 2log2^n,也就是说,红黑树的高度近似 2log2^n。

所以,红黑树的高度只比高度平衡的 AVL 树的高度 log2^n 仅仅大了一倍,在性能上,下降得并不多。这样推导出来的结果不够精确,实际上红黑树的性能更好。

解决开篇

为什么在工程中大家都喜欢用红黑树这种平衡二叉查找树?

前面提到过的 Treap、Splay Tree,绝大部分情况下,它们操作的效率都很高,但是也无法避免极端情况下时间复杂度的退化。尽管这种情况出现的概率不大,但是对于单次操作时间非常敏感的场景来说,它们并不适用。

AVL 树是一种高度平衡的二叉树,所以查找的效率非常高,但是,有利就有弊,AVL 树为了维护这种高度的平衡,就付出很多的代价。每次插入、删除都要做调整,比较复杂、耗时。所以,对于有频繁的插入、删除操作的数据集合,使用 AVL 树的代价就有点高了。

红黑色知识做到了近似平衡,并不是严格的平衡,所以在维护平衡的成本上,要比 AVL 树要低。

所以,红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说,要面对各种异常情况,为了支撑这种工业级的应用,我们更倾向于这种性能稳定的平衡二叉查找树。

内容小结

红黑树是一种最难掌握的一种数据结构,最难的是它的实现。

关于红黑树,我们要掌握学习它的由来、特性、使用的场景以及它能解决的问题。

红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中,复杂度退化的问题而产生的。红黑树的高度近似 log2^n,所以它是近似平衡,插入、删除、查找操作的时间复杂度都是 O(logn)。

因为红黑树是一种性能非常稳定的二叉查找树,所以,在工程中,但凡是用到动态插入、删除、查找数据的场景,都可以用到它。不过,它实现起来比较复杂,自己实现难度会有些高,这时候,我们其实更加倾向于用跳表来代替它。

课后思考

动态数据结构支持动态地数据插入、删除、查找操作,除了红黑树,我们前面还学习过哪些呢?能对比下各自的优势、劣势、以及应用场景吗?

> 动态数据结构是支持动态的更新操作,里面存储的数据是时刻在变化的,通俗一点讲,它不仅仅支持查询,还支持删除、插入数据。而且,这些操作都非常高效。如果不高效,也就算不上是有效的动态数据结构了。

答:

动态数据结构特点优点缺点应用场景
跳表查找、删除、插入的时间复杂度是 O(logn)实现简单,并且范围查询效率高需要额外存储索引,存储索引空间复杂度是 O(n)适用于顺序遍历、区间查找、不在乎内存占用的场景
散列表查找、删除、插入的时间复杂度是 O(1)查找、删除、插入时间复杂度是常量数据大时会需要进行扩容而消耗性能,而且会产生散列冲突,存储的数据是无序的,不能有序的遍历比较适用于经常查找、不需要顺序遍历、数据不经常更新的场景
平衡二叉查找树(红黑树)查找、删除、插入的时间复杂度是 O(logn),中序遍历就是顺序遍历插入、删除、查找操作比较稳定实现复杂,区间查找不方便适用于顺序遍历、不需要区间查找的场景
 

相关推荐