最新要闻
- AI也有焦虑症?专家:微调模型AI可供医生研究“精神病人” 每日短讯
- 当前播报:专家:印度人口将是中国三倍 成全球第一人口大国
- 余承东:华为必须造车 是和车企一起造最好的车 快看点
- 环球热文:接连失效!西丽、西乡旧改都未获批!
- 泺怎么读什么意思(泺怎么读)
- 头条:司机担心违法被拍拒给救护车让路 回应扣分怎么办引热议:网友吵翻
- 韩方称要做好亚运会不公平待遇准备 国内选手吐槽:不配说公平 韩服笑死人
- 环球热消息:科技股票十年回报率:英伟达105倍第一 马斯克四字回应
- 特斯拉车顶维权女车主回应败诉:有一案胜诉 获赔2万元
- 很是震撼!古人吃剩的螺蛳壳堆成一座山 13个足球场大小
- 世界通讯!杨紫琼版观音菩萨引热议!《西游ABC》差评不断:豆瓣已5.6分
- 全球即时:越南大牌:Lipo柠檬味面包干8.9元/包抄底
- 夏日炎炎过夏“神裤”!匹克冰丝裤2.6折狂促:到手64-每日热讯
- 当前最新:蚂蚁庄园支付宝问答:钙片含钙量越高补钙效果越好吗
- 天天热点评!中国手机市场连续5个季度暴跌 越来越多手机卖不动!为啥年轻人不换新手机了?
- 每日时讯!4G成熟 你会升5G吗?中国移动喊话不缩减5G投入:华为等中新集采大单
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
红黑树_每日资讯
红黑树
杂话
最近闲来无事去学了学红黑树,《算法导论》和维基百科都讲的很详细。
(资料图片仅供参考)
红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明,被称为“对称二叉B树”,它现代的名字源于Leo J. Guibas和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂,但它的操作有着良好的最坏情况运行时间,并且在实践中高效:它可以在\(O(\log n)\)时间内完成查找、插入和删除,这里的 \(n\) 是树中元素的数目。————维基百科
关于红黑树名字的来源也有一个不错的故事(奇怪的名字总会引人遐想:在一篇1972年的论文〈A Dichromatic Framework for Balanced Trees〉中,Leonidas J. Guibas 和 Robert Sedgewick从对称二元B树(symmetric binary B-tree)中推导出了红黑树。之所以选择“红色”是因为这是作者在帕罗奥多研究中心公司(Xerox PARC)工作时用彩色激光打印机可以产生的最好看的颜色。另一种说法来自Guibas,是因为红色和黑色的笔是他们当时可用来绘制树的颜色。故事依旧来自维基百科。
我主要只看了《算法导论》,维基百科只是掠过一眼,所以如果算导和维基上有不一样的我只能按算导来写,不过算导上那个删除操作我看的时候就很惊奇于算导的谜之解释,所以这里按维基上的来,这也是我看算导时想的,不过解释不一样代码都是一样的。
通过本身的性质来维护平衡性,真的tql
性质
红黑树的基本属性有五个:\(key\)值,左儿子地址,右儿子地址,父亲地址和它的颜色(红或黑)。
红黑树需要满足以下几点性质:
- 每个点是红色的,或者是黑色的
- 根结点是黑色的
- 每个叶结点(\(NIL\))是黑色的
- 如果一个结点是红色的,那么它的两个子结点都是黑色的
- 对于每个结点,其到其所有后代叶结点的简单路径上黑色结点的个数是相等的
为了便于处理边界条件,使用一个哨兵结点来代替所有 \(NIL\)
那么,为什么只要维持这几点性质就可以维持树的平衡呢?因为满足红黑性质的树一定是一棵比较平衡的树,对于一个具有 \(n\) 个内部结点的树,它的高度至多有 \(2\lg(n+1)\)。算导上有严谨的解释,我在这里简单说一下我的理解:首先我们先不看红色结点,那么黑高是一定的,如果去掉所有红色结点,那么这棵树就是高度平衡的,就算往里添加红色结点,死劲按着一条路径加,根据性质四,这条路径的高度至多变成原来的两倍。因此,平衡树的各种操作在红黑树的执行时间都是 \(O(\lg n)\)。
旋转
和其他平衡树的旋转一样,分为左旋右旋。
(抠图永无止境……)
直接贴代码了:
void left_rotate(int x) { int y = t[x].r; t[x].r = t[y].l; if (t[y].l != -1) t[t[y].l].p = x; t[y].p = t[x].p; if (t[x].p == nil) root = y; //特殊设定的nil结点,让nil = maxn - 1; else if (t[t[x].p].l == x) t[t[x].p].l = y; else t[t[x].p].r = y; t[x].p = y; t[y].l = x;}void right_rotate(int x) { int y = t[x].l; t[x].l = t[y].r; if (t[y].r != -1) t[t[y].r].p = x; t[y].p = t[x].p; if (t[x].p == -1) root = y; else if (t[t[x].p].l == x) t[t[x].p].l = y; else t[t[x].p].r = y; t[x].p = y; t[y].r = x;}
插入
插入操作与二叉搜索树的插入操作差不多,将插入结点插入到叶结点,然后左右结点设为 \(nil\) ,并且将颜色设为红色。操作会破坏红黑性质,所以后来又进行红黑性质的维护。
为什么要设为红色呢?直接设为黑色不久不用违反性质4了吗?但是如果直接设为黑色会影响性质5,在不改变其他结点颜色的情况下性质5是不可能被修复的,窃以为这样较为复杂所以不采用。而且决定红黑树的时间复杂度的关键是黑高,若设定为黑色可能会有多增黑高的可能,这些是个人理解,可能不对。
void insert(int z) { int y = nil, x = root; while (x != -1) { y = x; if (t[z].k < t[x].k) x = t[x].l; else x = t[x].r; } t[z].p = y; if (y == -1) root = z; else if (t[z].k < t[y].k) t[y].l = z; else t[y].r = z; t[z].l = -1; t[z].r = -1; t[z].c = 0; insert_fixup(z);}
注意到结尾的 \(insert\_fixup\) 函数,这个就是用来修复红黑性质的函数。
void insert_fixup(int z) { while (t[t[z].p].c == 0) { if (t[z].p == t[t[t[z].p].p].l) { int y = t[t[t[z].p].p].r; if (t[y].c == 0) {//case 1 t[t[z].p].c = 1; t[y].c = 1; t[t[t[z].p].p].c = 0; z = t[t[z].p].p; } else if (z == t[t[z].p].r) { //case 2 z = t[z].p; left_rotate(z); } t[t[z].p].c = 1;//case 3 t[t[t[z].p].p].c = 0; right_rotate(t[t[z].p].p); } else { int y = t[t[t[z].p].p].l; if (t[y].c == 0) { t[t[z].p].c = 1; t[y].c = 1; t[t[t[z].p].p].c = 0; z = t[t[z].p].p; } else if (z == t[t[z].p].l) { z = t[z].p; right_rotate(z); } t[t[z].p].c = 1; t[t[t[z].p].p].c = 0; left_rotate(t[t[z].p].p); } } t[root].c = 1;}
共分为6种情况,其中 \(z\) 的父结点是左儿子还是右儿子是对称的,把 \(right\) 和 \(left\) 对换就行,以左儿子为例,分为三种情况:
情况一:插入结点的叔叔存在,且叔叔的颜色是红色。
为了避免出现连续的红色结点,我们可以将父结点和叔结点变黑,将祖父结点变红。这样一来既保持了每条路径黑色结点的数目不变,也解决了连续红色结点的问题。
但是这样就出现一个新的问题:祖父结点就可能不满足红黑性质了,于是我们将祖父结点设为新的 \(z\) 继续修改。
还有一个问题是:如果 \(g\) 正好是根结点了怎么办?所以在每次循环的末尾都要将根结点设为黑色,只有这个时候红黑树的黑高才会增加。
情况二:插入结点的叔结点存在,且叔结点的颜色是黑色,并且 \(z\) 是一个右孩子。
我们直接左旋一下,使它变成情况三
情况三:插入结点的叔结点存在,且叔结点的颜色是黑色,并且 \(z\) 是一个左孩子。
出现叔叔存在且为黑时,单纯使用变色已经无法处理了,这时我们需要进行旋转处理。祖孙三代的关系是直线(x、父亲、祖父这三个结点为一条直线),正是情况三,则我们需要先进行单旋操作,再进行颜色调整,颜色调整后这棵被旋转子树的根结点是黑色的,因此无需继续往上进行处理。
因为只有一条直线才能旋起来,所以情况二就先处理成情况三。
有的博客将叔结点不存在还算成了一种情况,其实是多余的,因为叔结点不存在既是 \(nil\) ,而 \(nil\) 的颜色是黑的,等同于情况二和情况三。
对于 \(fixup\) 操作维持红黑树性质的严谨证明,算法导论上说的很详细,但奈何我非常懒不想再抄一遍并且找不到电子书来截图……
时间复杂度是 \(log\)
并且我们注意到插入实际上是原地算法,因为上述所有调用都使用了尾部递归。
删除
RB-delete删除 = 二叉树的删除+删除修复(delete_fixup)做二叉树删除时,需要记录被调整节点的颜色。二叉搜索树删除的四种情况
void rb_delete(int z) { int y = z; bool delcol = t[y].c; int x = z; if (t[z].l == nil) { x = t[z].r; rb_transplant(z, t[z].r); } else if (t[z].r == nil) { x = t[z].l; rb_transplant(z, t[z].l); } else { y = find_min(t[z].r); delcol = t[y].c; x = t[y].r; if (t[y].p == z) t[x].p = y; else { rb_transplant(y, t[y].r); t[y].r = t[z].r; t[t[y].r].p = y; } rb_transplant(z, y); t[y].l = t[z].l; t[t[y].l].p = y; t[y].c = t[z].c; } if (delcol == 1) rb_delete_fixup(x);}
为什么要记录被调换的那个 \(y\) 结点的颜色呢?而且我们注意到只有被调整结点颜色为黑色时才会进行调整操作,这是因为删除节点之前性质5是满足的,但是如果在一条路径上去掉一个结点,并且这个结点是黑色的,那么性质5显然就不满足了,所以要进行调整。算法导论上将修改操作解释为“认为改变后的结点有双重颜色,破坏了性质1,故进行修复操作来恢复性质1、性质2、性质4”,窃以为多此一举,不如按维基百科上破坏性质5解释来的自然。
先给出 \(fixup\) 代码:
void rb_delete_fixup(int x) { while (x != root && t[x].c == 1) { if (x == t[t[x].p].l) { int w = t[t[x].p].r; if (t[w].c == 0) { //A: CASE 1 t[w].c = 1; t[t[x].p].c = 0; left_rotate(t[x].p); w = t[t[x].p].r; } if (t[t[w].l].c == 1 && t[t[w].r].c == 1) { //A: CASE 2 t[w].c = 0; x = t[x].p; } else { if (t[t[w].r].c == 1) { //A: CASE 3 t[t[w].l].c = 1; t[w].c = 0; right_rotate(w); w = t[t[x].p].r; } t[w].c = t[t[x].p].c; //A: CASE 4 t[t[x].p].c = 1; t[t[w].r].c = 1; left_rotate(t[x].p); x = root; } } else { int w = t[t[x].p].l; if (t[w].c == 0) { //B: CASE 1 t[w].c = 1; t[t[x].p].c = 0; right_rotate(t[x].p); w = t[t[x].p].l; } if (t[t[w].r].c == 1 && t[t[w].l].c == 0) { //B: CASE 2 t[w].c = 0; x = t[x].p; } else { if (t[t[w].l].c == 1) { //B: CASE 3 t[t[w].r].c = 1; t[w].c = 0; left_rotate(w); w = t[t[x].p].l; } t[w].c = t[t[x].p].c; //B: CASE 4 t[t[x].p].c = 1; t[t[w].l].c = 1; right_rotate(t[x].p); x = root; } } } t[x].c = 1;}
分为4种情况:
情况一:\(X\) 的兄弟结点 \(w\) 是红色的
当待删除结点的兄弟为红色时,我们先以父亲为旋转点进行一次左单旋,再将兄弟的颜色变为黑色,将父亲的颜色变为红色,此时我们再对结点 \(x\) 进行情况分析,情况一就转换成了情况二、三或四。
当结点 \(w\) 为黑色时,属于情况2、3、4,这些情况是由 \(w\) 的颜色来区分的。
情况二:\(x\) 的兄弟结点是黑色的,且 \(w\) 的两个子结点是黑色的
因为在删除时将 \(B-X\) 这一路的结点提上去一个,所以这一路的黑色结点显然少一个。
在该情况下,我们直接将兄弟的颜色变成红色,此时根据父亲的颜色决定红黑树的调整是否结束,若父亲的颜色是红色,则我们将父亲变为黑色后即可结束红黑树的调整;若父亲的颜色原本就是黑色,则我们需要将父亲结点当作下一次调整时的 \(x\) 结点进行情况分析,并且情况二在下一次调整时可能会是情况一、二、三、四当中的任何一种。
情况三: \(x\) 的兄弟结点是黑色的,且 \(w\) 的左儿子是红色,右儿子是黑色
出现该情况时,我们先以兄弟为旋转点进行一次右单旋,再将兄弟结点变为红色,将兄弟结点的左儿子变为黑色,此时我们再对 \(x\) 进行情况分析,情况三就转换成了情况四。
情况四:\(x\) 的兄弟结点是黑色的,且 \(w\) 的左儿子是黑色的,右儿子是红色的
经过情况四的处理后,红黑树就一定调整结束了。在情况四当中,我们先以父亲为旋转点进行一次左单旋,然后将父亲的颜色赋值给兄弟,再将父亲的颜色变为黑色,最后将 \(w\) 的右儿子变为黑色,此时红黑树的调整便结束了。
后记
真的是写前踌躇满志,写时痛苦面具,写后怅然若失。自己对于红黑树依旧是没有怎么掌握,只能不断地翻书查资料,书上写的有些过于严谨导致读来不畅,网上的博客大部分也只是介绍了一下操作,然而原理还是有些地方不懂,而有一些博客看上去似乎非常好但是太长了我也不敢看。
现在仍然有一些缺陷:
首先是代码,网上的都是用指针实现的,但是我对于指针实在是不太熟练,而且听说有一些地方用指针反而会慢一些,所以用的是数组,但是我太烂了,写了几个基本操作就放弃了,想要测试一下代码对不对总不能手推树的结构然后输出检验吧,那样太繁琐了,我竟没有知道这代码对不对了
然后则是一些原理仍不是很明白,反应在这篇博客中也是语焉不详,譬如,fixup操作,为什么要那样做?尤其是delete_fixup的解释,是解释成破坏性质1还是性质5?算导的固然不自然,在解释时似乎能自圆其说,但推敲一番觉得情况二“同时去掉一重黑色”的解释很怪异,似乎在说底色是红色,然后x染了两重黑,w是一层,但是去掉后w岂不就无色了?底色可以看作红黑色,那我两重黑色就不是红黑色了?然而如果用性质5我却无法证明。
还有一点是对于那些操作的描述,由于都是相同的,我自己懒得写,于是只能搬一下了,还有图也是,这导致这篇文章像一个缝合怪,有的地方颇不自然
关键词:
红黑树_每日资讯
未来边缘计算:趋于分布式智能
AI也有焦虑症?专家:微调模型AI可供医生研究“精神病人” 每日短讯
当前播报:专家:印度人口将是中国三倍 成全球第一人口大国
余承东:华为必须造车 是和车企一起造最好的车 快看点
环球热文:接连失效!西丽、西乡旧改都未获批!
x86游戏逆向之实战游戏线程发包与普通发包的逆向 快看
全球热门:理解JS中数组的常见应用
索引与分片|今日看点
泺怎么读什么意思(泺怎么读)
头条:司机担心违法被拍拒给救护车让路 回应扣分怎么办引热议:网友吵翻
韩方称要做好亚运会不公平待遇准备 国内选手吐槽:不配说公平 韩服笑死人
环球热消息:科技股票十年回报率:英伟达105倍第一 马斯克四字回应
23 Windows Sever 201服务器系统的安装以及远程控制的设置与使用
特斯拉车顶维权女车主回应败诉:有一案胜诉 获赔2万元
很是震撼!古人吃剩的螺蛳壳堆成一座山 13个足球场大小
世界通讯!杨紫琼版观音菩萨引热议!《西游ABC》差评不断:豆瓣已5.6分
全球即时:越南大牌:Lipo柠檬味面包干8.9元/包抄底
夏日炎炎过夏“神裤”!匹克冰丝裤2.6折狂促:到手64-每日热讯
当前最新:蚂蚁庄园支付宝问答:钙片含钙量越高补钙效果越好吗
《安富莱嵌入式周报》第313期:搬运机器人,微软出的C语言手册,开源生物信号采集板,开源SMD回流焊,开源SDR无线电,汽车级机器人评估板|天天即时
天天要闻:13-分频器-奇分频
天天热点评!中国手机市场连续5个季度暴跌 越来越多手机卖不动!为啥年轻人不换新手机了?
每日时讯!4G成熟 你会升5G吗?中国移动喊话不缩减5G投入:华为等中新集采大单
定边县冯地坑镇冯地坑村扶贫互助资金协会 天天时讯
在这片生态走廊,孩子们探究生物多样性…… 即时
环球微资讯!Go 语言 map 如何顺序读取?
全球信息:DataGridView完美解决复制粘贴功能
每日热门:【环球财经】美财长把最早债务违约日期推迟到6月5日
万吨海上巨无霸!渤海湾首个千亿方大气田中心平台建成
35岁模特患厌食症去世时仅23公斤:都是为控制体重 世界播报
【天天速看料】首发3999元!小米电视音响5.1.4发布:200W低音炮、杜比全景声
当前热点-半年都不消停?你的湿疹“不一般”
获取门禁记录方式-实时获取|世界时快讯
《狂飙》片方没有为高启强报名“最佳男主角”引热议:影迷直呼可惜 到底为啥? 环球最资讯
林志颖车祸后再度开法拉利赛车 网友大赞心理素质真强大
垃圾分类全覆盖-环球聚焦
iPhone 15系列四款机模上手:全系USB-C 接口、标配灵动岛-环球滚动
SQL进阶教程读后总结与感想|全球讯息
希荻微:子公司拟减持NVTS股票-环球热讯
mol是什么单位等于多少毫克_mol是什么单位
一季度全球汽车销冠出炉:特斯拉史无前例!Model Y力压丰田卡罗拉
惠普战66六代上手:2.5k 120Hz屏真香|每日信息
全球短讯!日本人把安卓手机做成了翻盖!极致工匠 只要100多元
2018年菲尔兹奖得主:中国这么大 需要至少50个清华-当前速递
NVIDIA市值无限逼近1万亿美元!老黄一夜赚了65亿刀 世界新消息
世界热讯:中位数怎么求_中位数
微速讯:阿扎尔换凯恩!皇马热刺重磅互换,本泽马接班人敲定,扎球王走人
世界看热讯:三亚一刑释人员砍伤2人潜逃 现已被抓获归案
2023王源演唱会重庆站直播时间+入口
证券期货业网络和数据安全实验室今日授牌 全球新资讯
乐享云南|美景·西双版纳原始森林公园
世界焦点!Node翻译i18n多语言文件,1分钟生成100种语言包
因高度计算出错 导致日本“白兔号”撞上月球摔个稀碎
著名演员罗京民老师因病去世 曾出演高分电视剧《士兵突击》
舅舅党爆料 微软Xbox将在未来推出《星空》主题限定手柄与无线耳机
育碧天猫旗舰店将于6月7号停止运营 不再经营国内的衍生品销售业务
五月天演唱会于今日晚间在鸟巢举行 不少歌迷在场外听起演唱会
湖北多地遭遇暴雨 一高校学生宿舍内居然有鱼儿出没
特斯拉或向其他制造商开放部分汽车操作系统代码 与谷歌和苹果展开竞争
米哈游《崩坏:星穹铁道》手机版全球总营收已超1亿美元 超过《原神》
印度一新郎临阵脱逃 新娘狂追到20多公里外找到新郎
路过的小学生顺手把火灭了 网友:点赞机智勇敢的小少年
环球热门:骁龙影像旗舰“百花齐放”:哪一款是你的菜?
热消息:索尼Xperia 1 V为何不用一英寸主摄?背后原因揭开
环球热消息:桌面版RTX 4060 Ti啥水平?实测表现差强人意
《英雄联盟手游今日更新4.2版本 无限火力模式正式上线
《魔戒咕噜》Steam多半差评 首日仍有800人在线受苦
高精度加法(含代码)|天天快播报
《国家水网建设规划纲要》要点速览_全球微资讯
理想L系列车型推送更新:“小主人模式”上线 通讯
【聚看点】满意率超99%!小米13 Ultra站稳高端:雷军摆庆功宴
瑞松科技因信息披露违规等违规行为被上海证券交易所采取监管措施|新动态
PC、手机生态融合!Intel、腾讯一起找到了最好的路子
AMD RX 7600公版卡小翻车:6+2针电源线插不上 全球热点
99元 联想拯救者M5鼠标上架:8000 DPI、5档调节
00后折叠男孩首次手术成功:矫正脊柱至少90度
【新要闻】真人《芭比》曝美女足部特写:暴雪高管不淡定了
神马股份: 神马股份关于向不特定对象发行可转换公司债券2023年跟踪评级结果的公告
机械硬盘可以淘汰了 梵想4TB SSD硬盘1099元(满血性能+国产闪存)|每日视点
央视曝光李鬼搬家公司:说好1700元路上疯狂加价到9000! 天天热头条
刚出生就要上绞肉机 公鸡连生存的权利都没了
全球通讯!福特CEO:超长续航电动车很难赚钱 大电池成本太高了
今日报丨7)where子句
每日消息!记录--前端小票打印、网页打印
[ESP] ESP-IDF WiFi配网(SoftAP+HTTPD)代码备注_环球看点
用好Prompt 可以让AI更智能
宕昌县南阳镇综合养老服务中心改建项目中标公示|天天观热点
日本白兔航天器月球着陆撞个稀碎 原因公布:一个错误引发惨案
资讯推荐:消除汉字“数字鸿沟”!蚂蚁“汉字拾光计划”解决生僻字输入难题
环球观速讯丨退出手机市场已有两年!LG SmartWorld服务即将停止运营
男生炫酷“海胆头”参加毕业典礼:嗨翻全场
不必过分担忧大米产需缺口 |当前速讯
获取门禁记录方式-主动获取
软件开发全部文档下载(超过三百份)
天天观天下!一文看懂GPT风口,都有哪些创业机会?
今日要闻!如何把数据从 TDengine 2.x 迁移到 3.x ?
总结Vue3 的一些知识点:Vue3 计算属性
首次10nm以下!三星研发全新4F2内存芯片:面积缩减30% 每日讯息
3199元 铭凡UM790 Pro迷你主机上架:锐龙9 7940HS_每日速讯