首页天道酬勤()

()

admin 11-29 18:59 235次浏览

00-1010最后一节详细介绍了C语言中的二叉查找树,并提到数据可以存储在二叉查找树的结构中,可以获得很好的搜索性能。

二叉查找树搜索效率好的原因是,在向树中插入值时,总是严格遵守左子节点的值小于父节点的值,右子节点的值大于父节点的值的规则。以搜索12为例:

从根节点开始,

12大于9,所以转到右边的节点;

12小于29,所以转到左节点;

搜索完成。

这避免了遍历所有值。如果你稍微想一下,你会发现当二叉查找树的每个节点都有两个子节点时,kdxl是最好的。此时,kdxl可以存储尽可能多的值,同时保持出色的搜索性能。为什么呢?让我们考虑极端情况,假设所有节点(除了最后一个节点)只有一个子节点,如下图所示:

在这种情况下,二叉树是一个链表。搜索时只能像链表一样线性遍历,二叉树的搜索性能就丧失了。

二叉搜索树的局限性

为了解决二叉查找树的这一缺陷,提出了自平衡二叉查找树。平衡二叉查找树本质上是一个二叉查找树,只是它的所有叶节点的深度差小于1。

节点的深度是指从根节点到达它的父节点的数量。树末端的节点称为叶节点。

根据前面的分析,右边的图显然比右边的图有更好的表现。

00-1010自平衡二叉树虽然可以充分发挥二叉查找树的优秀搜索特性,但是维护起来非常麻烦,在插入新数据时很难保证良好的效率,因此提出了红黑树。典型的红黑树结构如下:

红树林是一个半平衡的二叉查找树,它放弃了二叉查找树的绝对平衡来换取更简单的可维护性,这使得二叉查找树在插入新数据和搜索数据时具有良好的搜索性能。

红黑树之所以是半平衡二叉查找树,是因为红黑树中所有叶节点的深度差不会超过一次。为什么呢?在回答这个问题之前,我们先来看看红黑树的几个特点:

所有节点不是红色就是黑色。根节点必须是黑色的。所有空(或无)节点都是黑色的。红色节点的两个子节点必须是黑色的(没有连续的红色节点)。从根节点到任何叶节点,黑色节点的数量是相等的。只要二叉查找树符合以上五个属性,它就是一棵红黑树。其实提出这五个性质的目的是为了获得红黑树“所有叶节点的深度差不会超过一次”的特性。请看下图:

叶子最浅的路径必须出现在所有黑色节点的路径中,最深的路径必须同时有黑色节点和红色节点。属性要求所有路径中黑色节点的数量相等,因此在比较叶节点的最深路径和最浅路径时,应该只考虑最深路径中的红色节点。4属性要求路径中不能出现连续的红色节点,因此最深的路径必须在红色和黑色节点之间交替,这就解释了为什么叶子节点的最深路径最多是最浅路径的两倍。

如果插入和删除操作遵循红黑树的五个规则,那么树将始终保持红黑树,即半平衡树,可以在插入和查询过程中保持树的优异性能。我们之所以煞费苦心去维护一棵红黑树,是因为实践证明红黑树的这些规则是比较容易遵循的。

00-1010虽然几棵红黑树

规则看来比较容易遵循,但是在使用C语言编程实现时,还是有些繁琐的。向红黑树插入数据时,一般分为两个步骤,首先把红黑树当作一棵普通的二叉搜索树插入数据,然后再进行旋转变换以及重新着色的操作,调整二叉树仍然是一个红黑树。

应该明白,红黑树也是一棵二叉搜索树,所以二叉搜索树的性质红黑树也应遵循。在向红黑树插入数据后的变换和重新着色操作中,着色显然不会影响二叉搜索树的性质,“红黑色”只是节点的一个标记而已,它不影响节点记录的数据,也不影响节点间的相对关系。真正改变树结构的是“旋转”操作,应该尽力避免会破坏二叉搜索树性质的操作,所以人们定义了“树节点的左旋和右旋”,如下图:

树节点的左旋和右旋均不改变二叉搜索树的性质,β始终介于 A、B之间。@Sun_TTTT 的动图更清晰一点,清楚的反应了左旋和右旋的特点:

右旋:

只要在努力把二叉搜索树变换成红黑树的过程中,始终遵循不破坏二叉搜索树性质的操作,那么最后得到的红黑树一定仍然也是二叉搜索树。下图就是一次变换,按照前文的分析,显然变换后的二叉树的总体搜索性能更好。

那么,该怎样变换呢?其实还是有些复杂的,限于篇幅,本节不做介绍,下一节再结合 linux 内核中关于红黑树的C语言代码深入讨论之。

小节

我们费尽心思的琢磨出红黑树,又提出看起来非常拗口的红黑树 5 条性质,其实目的只有一个:尽可能方便的维持二叉搜索树的平衡性。这样就避免了文章一开头提到的“不合理树的结构”导致的二叉树搜索性能的下降,也不会出现“极端情况”:使用二叉树的数据结构,却生成了一条链表。。。

欢迎在评论区一起讨论,质疑。文章都是手打原创,每天最浅显的介绍C语言、linux等嵌入式开发,喜欢我的文章就关注一波吧,可以看到最新更新和之前的文章哦。

您真的需要导入“反应”吗?(反响)深入浅出 LVS 负载均衡系列(二):DR
数据结构图(红黑树是平衡二叉树吗) 红黑树与平衡二叉树(b树和红黑树区别)
相关内容