数据结构与算法之美——红黑树

08/13 10:19
阅读数 47

一、前言

       上两节,我们依次讲了树、二叉树、二叉搜索树。二叉搜索树是最常见的一种二叉树。它支持快随插入、删除、查找操作。各个操作的时间复杂度和树的高度成正比,平均时间复杂度是O(logN)。

       不过二叉搜索树在频繁动态更新过程中可能会出现树的高度远大于 log2n 的情况,从而导致各个操作的效率下降。极端情况下,二叉树会退化为链表,时间复杂度会退化到 O(n)。要解决复杂度退化这个问题,需要一种平衡二叉搜索树。比如红黑树、AVL树、树堆。

       在工程中,很多用到平衡二叉搜索树的地方都会使用红黑树。为什么工程中都喜欢用红黑树而不是其他平衡二叉搜索树。

二、平衡二叉搜索树

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

                                            

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

       发明平衡二叉查找树这类数据结构的初衷是,解决普通二叉查找树在频繁的插入、删除等动态更新的情况下,出现时间复杂度退化的问题。所以,平衡二叉查找树中“平衡”的意思,其实就是让整棵树左右看起来比较“对称”、比较“平衡”,不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些,相应的插入、删除、查找等操作的效率高一些

三、红黑树

       红黑树的英文是“Red-Black Tree”,简称 R-B Tree。它是一种不严格的平衡二叉查找树,顾名思义,红黑树中的节点一类被标记为红色,一类被标记为黑色。一颗红黑树满足这么几个条件。

       ①根节点是黑色的

       ②每个叶子节点都是黑色的空节点,也就是说,叶子节点不存储数据。

       ③任何相邻的节点都不能同时为红色,也就是说红色节点是被黑色节点隔开的。

       ④ 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点。

四、为什么红黑树是近似平衡?

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

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

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

四、解答开篇

        为什么在工程中大家都喜欢用红黑树这种平衡二叉查找树?AVL 树是一种高度平衡的二叉树,所以查找的效率非常高,但是,有利就有弊,AVL 树为了维持这种高度的平衡,就要付出更多的代价。每次插入、删除都要做调整,就比较复杂、耗时。所以,对于有频繁的插入、删除操作的数据集合,使用 AVL 树的代价就有点高了。

        红黑树只是做到了近似平衡,并不是严格的平衡,所以在维护平衡的成本上,要比 AVL 树要低。所以,红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说,要面对各种异常情况,为了支撑这种工业级的应用,我们更倾向于这种性能稳定的平衡二叉查找树。

五、总结

        关于红黑树,我们究竟需要掌握哪些东西呢?我们学习数据结构和算法,要学习它的由来、特性、适用的场景以及它能解决的问题。对于红黑树,也不例外。你如果能搞懂这几个问题,其实就已经足够了。

        红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中,复杂度退化的问题而产生的。红黑树的高度近似 log2n,所以它是近似平衡,插入、删除、查找操作的时间复杂度都是 O(logn)。因为红黑树是一种性能非常稳定的二叉查找树,所以,在工程中,但凡是用到动态插入、删除、查找数据的场景,都可以用到它。不过,它实现起来比较复杂,如果自己写代码实现,难度会有些高,这个时候,我们其实更倾向用跳表来替代它。

        至于红黑树是怎么维持近似平衡的?  什么时候左旋?什么时候右旋?

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部