Red-Black-Tree又叫红黑树,各操作都为O(logn)因为加入左特殊ge规则,最大高度可以控制到2*logn且最长路径最大为最短路径ge2倍。个人认为,系一种剩适合练习但唔系好实用ge结构,因为好复杂,但系又系好多树ge基础数据结构窝,所以就睇下咯。
首先介绍距ge5种性质:
1)每个结点系红色或者黑色。
2)根必须系黑色。
3)每个叶结点必为黑色。
4)红色结点必有两个黑色儿子。(保证无两个红色节点相连)
5)从树中每个节点开始到其所有叶子所经过ge黑结点个数相同。
(因为性质4,所以最坏情况就系两个黑结点之间都有一个红结点,所以最长路径为最短路径两倍)
跟住就说明下RB-Delete-Fixed(删除操作后恢复红黑性质)咯,以下内容十分似扭魔方,哈哈。
以下情况只系删除结点y为黑色ge时候发生,考察儿子x,且被删结点y最多只有一个儿子(自己查下基本二叉树删除操作啦哈哈)。
首先假设x系当前结点指针,且为y左儿子(右儿子操作对称),w系x兄弟ge指针,p[x]系x老豆ge指针,呢个操作首先系假设x有多一重黑色,既将被删黑色结点ge黑色往下推,使其保证性质5,但系破坏左性质1(前提),因为根据假设,x结点系红黑或者双重黑色,以下证明操作回复红黑性质1,2,4,5,唔洗理3,因为红黑树用左哨兵。{= =}
定义x所指向结点多一层黑色(假设ge黑色,最后镀系边个点吾一定),并不是x本身color属性变化(color属性只有红色或黑色)。
情况1)xcolor属性系红色。
一、x系根部,只有可能破坏性质性质2,只需要直接镀上黑色就回复左。
二、x唔系根部,无破坏性质2,有可能破坏性质4(p[x]有可能红色),只需直接将黑色镀上,回复性质1,4,5。
情况2)xcolor属性系黑色,考察其兄弟w。
一、w为红色(即p[x]color必为黑色)
将p[x]color改为红色,w改为黑色,对p[x]做左旋后,w变为p[x]父结点,
w左儿子变成x兄弟,且必定为黑色(因为w本来红色),无破坏性质,2,3,4,5,未回复性质1.进入下一次循环,(注意此时p[x]为红色,新w为黑色。)
二、w为黑色(因为性质4,通常系红色,除左p[x]系根)
小情况1)w两个儿子都为黑色。
注意x同埋w都系黑色,只需要将黑色往p[x]推就ok啦。即将wcolor改为红色,x指针指向p[x],尼几个操作无破坏2,3,4,5。呢个时候有两种情况:
1、p[x]本来color为红色,将x指针黑色镀上后,就可以回复性质1,循环结束。
(注意到如果从“一”进入到呢种情况,循环必定结束)
2、p[x]本来color为黑色,吾可以将黑色镀上,因为宜家p[x]系双重黑色,未回复性质1,继续下一次循环。
小情况2)w左儿子为红色,右儿子为黑色。
将w左儿子着黑色,w着色红色,w做右旋,新w为原w左儿子,等价于原w左子树少一红结点,右子树多一红结点,不破坏性质2,3,4,5。未回复性质1,继续下一次循环。
小情况3)w右儿子为红色。
将w着色为红色,p[x]同w右儿子着色为黑色,对p[x]做左旋后,x可以吾捞,因为已经回复左性质1。其他红黑属性无被破坏。
9up完啦~~~。
分享到:
相关推荐
4.RB-10-001-6轴机器人.zip非标自动化设备solidworks3D图纸机械设计素材资料 4.RB-10-001-6轴机器人.zip非标自动化设备solidworks3D图纸机械设计素材资料 4.RB-10-001-6轴机器人.zip非标自动化设备solidworks3D图纸...
常用电容封装 RB.2/.4、RB.3/.6、RB.4/.8、RB.5/1.0 protel 格式 可以导入到dxp或更高版本
RE-RB-OFDM-SB-符号详解.pdfRE-RB-OFDM-SB-符号详解.pdfRE-RB-OFDM-SB-符号详解.pdfRE-RB-OFDM-SB-符号详解.pdfRE-RB-OFDM-SB-符号详解.pdfRE-RB-OFDM-SB-符号详解.pdfRE-RB-OFDM-SB-符号详解.pdfRE-RB-OFDM-SB-符号...
RE-RB-OFDM-SB-符号详解.docxRE-RB-OFDM-SB-符号详解.docxRE-RB-OFDM-SB-符号详解.docxRE-RB-OFDM-SB-符号详解.docxRE-RB-OFDM-SB-符号详解.docxRE-RB-OFDM-SB-符号详解.docxRE-RB-OFDM-SB-符号详解.docxRE-RB-OFDM-...
redis集群windows下脚本redis-trib.rb
RTL8367RB-CG LAYER 2 MANAGED 5+2-PORT 10/100/1000M SWITCH CONTROLLER
用来构建redis集群的执行脚本, 执行方式 redis-trib.rb create --replicas 1 127.0.0.1:7000 127.0.0.1:7001 127.0.0.1:7002 127.0.0.1:7003 127.0.0.1:7004 127.0.0.1:7005 --replicas 1 为每一个主节点配置一个...
搭建redis集群的工具,先试试下面的方法...打开该链接如果没有下载,而是打开一个页面,那么将该页面保存为redis-trib.rb 建议保存到Redis的目录下
安装redis集群所需文件,5.0版本以下redis。windows 环境安装。
bnet-mashery-rb-源码.rar
Percona-Server-5.5.60-38.12-r26ef816-el7-x86_64-bundle.tar linux版,优化数据库,含有高效XtraDB引擎
msfconsole中,webdav漏洞,iis服务提权工具。
redis-trib.rb是官方提供的Redis Cluster的管理工具,无需额外下载,默认位于源码包的src目录下,但因该工具是用ruby开发的,所以需要准备相关的依赖环境。
最新检测机构质量手册(RB-T214-2017)最新版.pdf
资源分类:Python库 所属语言:Python 资源全名:rbpy-rb-0.6.11.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
资源分类:Python库 所属语言:Python 资源全名:rbpy-rb-0.7.10.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
资源分类:Python库 所属语言:Python 资源全名:rbpy-rb-0.9.16.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
gcc编译器20220506 082534 版本为:gcc-arm-none-eabi-10.3-2021.10-win32 配合文章:nordic52832 nordic使用gcc编译环境搭建和使用说明
ttt-5-move-rb-online-web-sp-000-源码.rar