彻底搞懂红黑树(一)_为什么红黑树用继承-程序员宅基地

技术标签: 数据结构/算法  数据结构  算法导论  

红黑树和c++ 虚拟继承内存分布 几乎成了我的死敌,因为完全没用过,所以导致每次看懂了之后都忘了(也许不是真的看懂了,有些关键性的东西没理解透),这次准备把这两个难题(其实也不难)仔细看懂,然后再写一份比较详细的文档作为备忘。


首先是红黑树

零  八卦起源

    1972年,鲁道夫贝尔最先发明,但是他称之为“对称二叉B树”,真正的称之为“红黑树”是在1978年Leo J. Guibas 和 Robert Sedgewick的一篇论文开始的。
红黑树的命名和Xerox PARC也有关系,当时Robert Sedgewick在施乐做访问学者的时候,施乐正好发明出激光彩色打印机,然后觉得这个打印机打出的红色很好看,就用了红色来区分结点的不同,于是就叫红黑树了。 (注:这个数据结构是1972 由 Rudolf Bayer 发明的,叫 "symmetric binary B-tree")。摘自 左耳朵耗子的 微博。


一  红黑树的定义

算法导论里是这样定义一棵红黑树的:
      1、每个结点或是红色的,或是黑色的
      2、根节点是黑色的
      3、每个叶结点(NIL)是黑色的
      4、如果一个节点是红色的,则它的两个儿子都是黑色的。
      5、对于每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑色结点。
    话说这些性质里面,前四个都很容易理解,但惟独第五个,我是怎么读怎么觉得拗口,原因就是对这个“子孙节点”感到疑惑,这个子孙节点是啥子玩意儿呢?所有的子、孙节点??? 如果当前节点是根节点,那么根据定义:子孙节点有相同的黑色节点数,那不是搞笑吗?怎么可能得到呢。后来我看了一下英文版的,发现是这个:descendant leaves,貌似理解为子孙节点也不错哈,但我查了《Introduction to Algorithms》全书,也就这么一处用了descendant leaves,其他地方都是leaves,很显然这里的descendant leaves应该是特指,不应该就泛泛的翻译为子孙节点,而 应该是子孙叶节点才对,也就是树最边上的节点啦。这样理解起来也自然,也不会有歧义。然后对照红黑树的图(下图一)一比较,果然是这样。也不晓得是不是自己的语文差了,反正这里顺便鄙视下《算法导论》的翻译吧。也就是说从根节点(如下图 13根节点)到其所有的nil黑节点路径里的黑节点数就是一样的。


图一
    好吧,红黑树的性质就理解到这里。也许大家看书的话就会继续往下看了,当然我也是这样的。但是当我读第二遍的时候,我就想为什么这简简单单的5条性质就能让红黑树有如此好的性质。AVL树我还可以理解,毕竟有看得见摸得着的定义和balance代码,但红黑树我就不理解了,因为他的定义是如此的简单,也不可能看到定义就能想象它是如何调整树结构达到动态balance的,搞得我很恼火。我曾经试图搜索下 红黑树本质,但发现没有这方面的信息。o(╯□╰)o,我也只好自己思考下了。


二  引理

    估计有很多人对书上13.1 引理不是很在意,但是我想说,这正是理解红黑树精髓的地方之一。 这条引理也是红黑树为什么效率这么高的原因。不晓得是语文差还是啥的,我看书上的介绍也没看懂,写得太简洁了,菜鸟看不懂表示很蛋疼。后来在网上看了别人的资料,终于弄懂了。(⊙o⊙)…
 
下面我就仔仔细细的介绍下这条引理到底是怎么得到的。
引理:一棵有n个内结点的红黑树的高度至多为2lg(n+1)。
    这个引理怎么证明呢,这里需要一个工具  对以x为根的子树,它所包含的内部结点数至少为2^[bh(x)]-1。这里bh(x)(bh嘛,black height)被定义为结点x的黑高度,就是说,从结点x(不包括它本身)到它任一个叶结点的路径上所有黑色结点的个数。 
下面用归纳法证明:
    1)若x高度为0,那么它就是一叶子结点,它确实至少包含2^0-1=0个内部结点

    2)假设x为红黑树的某一内部结点,且它高度h>0,那么它的黑高度就是bh(x),但是它的两个孩子结点呢?这个就根据它们的颜色来判断了:
       如果x有一个红色的孩子y,那么y的黑高度bh(y)=bh(x),看看上面对黑高度的定义你就明白了——既然它是红色的,那么它的黑高度就应该和它父亲的黑高度是一样的;
       如果x有一个黑色的孩子z,那么z的黑高度bh(z)=bh(x)-1,这个怎么解释呢,因为它自己就是个黑结点,那么在计算它的黑高度时,必须把它自己排除在外(还是根据定义),所以它是bh(x)-1。

    3)x的孩子结点所构成的子树的高度肯定小于x这颗子树,那么对于这两个孩子,不管它们颜色如何,一定满足归纳假设的是至少hb 高度为 bh(x)-1。所以,对x来说,它所包含的内部结点个数“至少”为两个孩子结点所包含的内部结点数,再加上它自己,于是就为2^ [bh(x)-1]-1+2^ [bh(x)-1]-1+1=2^ [bh(x)]-1,归纳证明完毕。
也就是说n>=2^ [bh(x)]-1---------①

     把一 中红黑树性质中 4)、5)两个特性结合起来,其实我们可以得到黑节点至少是红节点的2倍。用一句话来说就是“有红必有黑,但有黑未必一定有红”。为什么这么说呢,因为从特性4)我们知道,如果有一个红结点存在,那么它的儿子结点一定是黑的,最极端的情况下,该路径上所有的结点就被红、黑两种结点给平分了那就是 黑节点至少是红节点的2倍。不知这个问题我解释清楚没有,因为这是往下理解的关键。
 
    如果一棵红黑树的高为h,那么在这个高度上(不包括根结点本身)至少有1/2h的黑结点,再结合上面对“黑高度”的定义,我们说,红黑树根结点的黑高度至少是1/2h,好了,我们拿出公式 ①,设n为该红黑树所包含的内部结点数,我们得出如下结论: n>=2^(1/2h)-1。 我们把它整理整理,就得到了h<=2lg(n+1),就是我们要证明的结论:红黑树的高度最多也就是2lg(n+1)。(⊙o⊙)
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ws891033655/article/details/18306719

智能推荐

2008-2020年上市公司能源消耗数据-程序员宅基地

文章浏览阅读581次。2008-2020年上市公司能耗数据/上市公司能源消耗数据_上市公司能源消耗数据

蓝桥杯第十届省赛真题解析--填空--不同字串_字符串0100110001010001有多少个不同的子窜-程序员宅基地

文章浏览阅读343次。蓝桥杯第十届省赛真题解析--填空--不同字串比赛记录问题描述答案提交解析比赛记录本人于2020年4月,重温了去年第十届蓝桥杯省赛的试题 。本次重温的感受较好,我觉得第十届的难度适中。问题描述一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成 的串。例如,字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab,一共 7 个。注意在计算..._字符串0100110001010001有多少个不同的子窜

JS事件冒泡、停止冒泡、addEventListener--实例演示-程序员宅基地

文章浏览阅读815次。前面说到的事件冒泡不是很明了,接上节问题,再记录一下 <div class='item' id='outer' onclick="alert('outer')"> <div class='item' id='inner' onclick="alert('inner');"> <div class='item' id='core..._addeventlistener 停止

Mac搭建redash开发环境使用MongoDB源(四)_redash mongo-程序员宅基地

文章浏览阅读725次。Mac搭建redash开发环境的使用MongoDB源(四)MongoDB安装正确的安装启动:使用MongoDB这里需要一句话。安装不想让brew安装的时候updating可以conrtol+c取消,然后就回到安装进程了brew install mongodbError: No available formula with the name "mongodb"直接报错,查了一下,我慌了…..._redash mongo

Oracle中递归查询父节点及其所属子节点(Connect By)_oracle递归 父节点减去子节点-程序员宅基地

文章浏览阅读1.1k次。1.需求 递归查询父节点及其所属子节点2.实现SELECT rofyxm.rofyxm_fjnm,rofyxm.rofyxm_mc,PRIOR rofyxm.rofyxm_fjnm,PRIOR rofyxm.rofyxm_mc,LEVEL lev FROM rofyxmSTART WITH LEN(ROFYXM_FJNM)=4--父级编号起始条件CONNECT BY NOCYCLE SU..._oracle递归 父节点减去子节点

Quartz2D详解_quartz 2d 3d-程序员宅基地

文章浏览阅读502次。iOS开发之Quartz2D详解2014-04-18 11:52:31cnblogs.com-求真求道-点击数:5911. 什么是Quartz2D? _quartz 2d 3d

随便推点

基于AI恶意软件分类技术(5)_malware classification-程序员宅基地

文章浏览阅读2k次。2021年malware分类技术综述,提到各种特征提取方法及现有的分类算法。_malware classification

python+opencv实现的图像直方图、直方图均衡以及图像高斯滤波_绘制栅格数据直方图,并对直方图进行滤波处理-程序员宅基地

文章浏览阅读1.1k次。1. 图像轮廓和直方图下面来看两个特别的绘图实例,图像的轮廓和直方图。绘制图像的轮廓(或者其他二位函数的等轮廓线)在工作中非常常用。因为绘制轮廓需要对每个坐标【x,y】的像素值施加同一个阔值,所以首先需要将图像灰度化:图像的直方图用来表征该图像像素值的分布情况。用一定数目的小区间(bin)来指定表征像素值的范围,每个小区间会得到落入该小区间来表示范围的像素数目。该(灰度)图像的直方图可以使用h..._绘制栅格数据直方图,并对直方图进行滤波处理

【软件安装】MacBook 安装 MATLAB 2020a_macbook安装matlab-程序员宅基地

文章浏览阅读1.5k次。记录一下安装方法:MacBook 安装 Matlab 2020 a_macbook安装matlab

使用如下代码将所有文件后缀名添加.jpg,然后可以按名称分组,打印成pdf-程序员宅基地

文章浏览阅读504次,点赞11次,收藏9次。使用如下代码将所有文件后缀名添加.jpg。

联想黑苹果找不到触摸板_联想V330-15IKB完美黑苹果,和笔记本各类常见问题解决办法...-程序员宅基地

文章浏览阅读5k次。本帖最后由 rclhxm 于 2020-9-17 20:31 编辑前言最近用了一周的时间把我的联想V330-15IKB给装上了10.15.6的黑苹果,并完美驱动(完善程度90%以上,因为可能有些领域我没有用到过,不能确保一定完美,但常用功能基本都正常),特来分享资源和自己笔记本装黑苹果时遇到的一些棘手问题的解决办法。首先说明一点,就算和我同型号的笔记本也不保证你就能百分百完美兼容,因为我加了一根4..._lenovo v330-15ikb 电池只能充电45%

SparkStreaming-架构与抽象_sparkstreaming架构图-程序员宅基地

文章浏览阅读191次。1.说明 SparkStreaming使用“微批次”的架构,把流式计算当做一系列连续的小规模批次处理来对待。SparkStreaming从各种输入源中读取数据,并把数据分组为小的批次。新的批次按均匀的时间间隔创建出来。在每个时间区间开始的时候,一个新的批次创建出来,在该区间内收到的数据都会被添加到这个批次中。在时间区间结束时,批次停止增长。时间区间的大小是由批次间隔这个参数决定的。批次间隔一般设在500毫秒到几秒之间,由应用开发者配置。每个输入批次都形成一个RDD,以Spark作业的方式处..._sparkstreaming架构图

推荐文章

热门文章

相关标签