我所理解的红黑树(RBT)
红黑树(Red–Black Tree)是一种自平衡二叉查找树,用于实现关联数组。它在1972年由鲁道夫·贝尔(Rudolf Bayer)发明,被称为"对称二叉B树"。
2-3树
由于红黑树过于复杂,因此在讲述之前我们先来大致了解一下2-3树
,2-3树类似红黑树,也是平衡树,时间复杂度均为。
2–3树早于红黑树出现,由约翰·霍普克洛夫特于1970年发明。2-3树也称为3阶B-树
、3叉搜索树
。
2-3树中的一个父节点可以有2个子节点也可以有3个子节点。
有2个子节点的父节点称为2-
节点,该节点有1个key。这类似二叉树的节点
有3个子节点的父节点称为3-
节点,该节点有2个key。假设父节点键为key1和key2且key1 < key2,左子树L、中子树M、右子树R。则左子树L < key1,key1 < 中子树M < key2 ,右子树 > key2。
2-3树是一棵完全3叉搜索树
。每个节点要么是叶子节点
,要么是2-节点
或3-节点
,,而且每个节点的子树一定是等高
的。
如上图,关键字为 [f h]
的3-节点
有3个子节点e
、g
、[i j]
,且 e<f
、f<g<h
、[i j]>h
查找
2-3树的查找类似bst,比如查找上图的g
- 首先g和d比较,g>d,查找右子树
- f<g<h,进入中子树
- g=g,返回节点,查找结束
插入
插入操作只需在叶子节点
处插入一个新节点,不过由于2-3树的定义需要调整树的结构,使其平衡。
在叶子节点而不是空节点处插入节点的好处是以后维护平衡就简单了,而且树的高度也是尽可能的低。
插入新节点处的叶子节点可为2-节点
或3-节点
如上图就是在2-节点位置i
直接插入一个新节点j
而变成一个3-节点,这种情况下无需调整树结构就已经平衡。
在3-节点处插入新节点同样也是在叶子节点插入,不过这样会导致形成一个4-节点
,在2-3树中这是不允许的,因此需要调整。调整方式为就是将4-节点
分裂与合并。
节点分裂
是将一个4-节点的中间值key节点提取处来作为父节点,左边key作为左节点,右边key作为右节点。
若该4-节点存在子节点,那么将左边key作为最左边两个子节点父节点,将右边key作为最右边两个子节点父节点。
节点分裂一般伴随着节点合并
,也就是将分裂后的父节点与之前未分裂4-节点的父节点合并成一个新的节点,如果新节点依旧是4-节点,那么继续向上分裂合并直到满足平衡。
举个例子:
向这棵2-3树插入k
节点后成为4-节点,不符合定义,需要分裂该节点。
将节点[i j k]
中的j
提取出来与与父节点[f h]
合并成[f h j]
,发现该节点依然是一个4-节点,因此需要继续分裂+合并。
此时[d h]
已经是一个3-节点了,而且整个2-3树也是等高的,调整结束。
插入a-k
的整个过程如下
删除
2-3树的删除虽然较为复杂,但大致可分为两类:删除叶子节点和删除非叶子节点。
删除叶子节点
删除叶子节点又可以分为删除2-节点
和删除3-节点
。
删除3-节点的情况最简单,直接删除即可。如下删除key为k的情况
删除2-节点不能简单的删除该节点,因为这样一删除后,该位置为空,2-3树是不允许存在这种情况的。此时可分为如下几类情况来处理:
- 待删除节点的
临近兄弟节点
是3-节点
- 待删除节点的
临近兄弟节点
是2-节点
,但父节点
是3-节点
- 待删除节点的
临近兄弟节点
和父节点
均是2-节点
对于第一种情况,删除该节点后只需向临近兄弟节点
“借”一个key与待删除节点相近作为新的节点并调整其与父节点
,此时树的高度不变。
如下图,删除i
节点,而且兄弟是3-节点,将兄弟节点中keyk
与删除节点相近的keyj
而不是l
作为已删除节点。由于k>j
,因此需要调整父子节点键值
对于第二种情况,首先删除该节点后,发现临近兄弟节点g
是一个2-节点且父节点[f h]
为3-节点。因此将父节点分解为2-节点,由于e<f<g
,于是将f
与临近兄弟节点g
合并成3-节点,并作为一个新的左孩子
演示过程如下
第三种情况待删除节点的兄弟节点和父节点均是2-节点,删除节点后将父节点b
和兄弟节点c
合并成3-节点。
1.若此时兄弟节点f和父节点d又是2-节点
,故继续合并d、f直到平衡,最终的结构如下。图中空位置只是直观上表示一棵等高的2-3树且该节点被“删除”了。
2.若此时临近兄弟节点是2-节点、父节点是3-节点
,则可看作是上述第二种删除情况。
如下,删除2-节点a
,此时兄弟节点c和父节点b均为2-节点,因此合并成3-节点[b c]
,此时仍然未平衡,且临近兄弟节f点是2-节点、父节点[d h]是3-节点
,因此分解父节点[d h]
,将d
与临近兄弟节f
合并为3-节点[d-f]
演示过程如下
3.若此时临近兄弟节点是3-节点
,该过程也可看作是上述第一种删除情况,此处不再叙述。
演示过程如下
删除非叶子节点
删除非叶子节点首先也需要找到一个前驱/后继节点
,有点类似BST。
总之简单来说,前驱节点就是节点的左子树的最右节点,后继节点就是节点的右子树的最左节点。
如下删除key=d
的节点,该key位于3-节点,不过没关系。找到其前驱节点c
,将键值替换后删除前驱节点c
,删除操作就转化为上述3种情况之一。
演示过程如下
以上大致是关于2-3树的一些基本操作了。说了这么多,就是为了2-3树和为红黑树之间的转化。
先来看这张图,将2-3树的3-节点
拆解成父子节点,且用红色箭头表明两者父子关系,将子节点染成红色,父节点染成黑色;再将其余2-节点
全部染成黑色。经过适当调整树结构后发现这是一棵红黑树!实际上,这是红黑树的变体——左偏红黑树
。
实际上向一棵普通的红黑树插入key为a-l
应该是这样的:
2-3树一定能转化为红黑树(左偏红黑树),而红黑树不一定能转化为2-3树!
由于2-3-4树
是红黑树的一种等同,故2-3-4树一定能转化为红黑树,而红黑树也一定能转化为2-3-4树!
红黑树
基本概念
红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它在1972年由鲁道夫·贝尔发明,被称为"对称二叉B树",它现代的名字源于Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文。红黑树的结构复杂,但它的操作有着良好的最坏情况运行时间,并且在实践中高效:它可以在 时间内完成查找,插入和删除,这里的 是树中元素的数目。
红黑树相对于AVL树来说,牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作,整体来说性能要优于AVL树。
根据2-3树转化为红黑树可以这样定义红黑树,或者是规则
:
- 红黑树一定是二叉搜索树,因为2-3树也是二叉搜索树;
- 根节点和所有外部节点(Nil)都是
黑色
,根据2-3树转化为左偏红黑树可看出来; - 在根至外部节点(Nil)路径上,没有连续两个节点是
红色
的; - 在所有根至外部节点的路径上,
黑色
节点的数目相同,即黑高
相等。
如果再添加这一规则红色节点位于左侧
,那么这个红黑树是一棵左偏红黑树。不过本文主要是介绍普通的红黑树。
上述规则3和规则4是极其重要的,但凡涉及插入和删除操作都是要使红黑树满足这两条规则。
本文红黑树C++类
1 |
|
哨兵节点
本文红黑树利用了哨兵节点
技巧,省去了判断nullptr的麻烦,不过BST部分代码需要稍微修改。
由于哨兵节点也是RBNodeEntry
结构,但哨兵节点无父节点,因此设置为nullptr
;同时还需要设置其leftChild
和rightChild
指向自身。
1 |
|
查找
由于红黑树也是平衡树,其查找也为,查找过程与普通的二叉查找树没有太大区别。不过红黑树和AVL树相比,在最坏情况下却是AVL树占优势。这是因为AVL树是严格的自平衡树,在最坏情况下同样多的节点,其高度小于红黑树,这就导致其查找效率高于红黑树。
旋转
红黑树的旋转操作只有左旋和右旋,而且也是核心。
以这张图为例,插入红色节点42后无需进行任何操作就满足红黑树性质。
下面这个例子就是典型的LLb
型,至于什么是LLb,此处简单介绍下。
图中u表示pu的左孩子、pu表示gu的左孩子、gr表示gu的右孩子,也就是pu的兄弟,u的叔叔。
而LLb的意思是:pu是gu的左孩子、u是pu的左孩子,且gu的另外一个孩子是黑色的(Nil节点是黑色节点
)。
首先插入节点41后违背规则3
,需要对节点45右旋,不过为了直观表示,我将图中的旋转箭头方向位置于42与45之间。旋转操作实质是对节点指针关系的修改。
而这个例子就是LRb
型,对节点42左旋
后再对节点45右旋
。这说明LRb可以转化为LLb类型,也就是说对于插入操作其实也就那几种不平衡类型。
1 |
|
插入
红黑树的插入操作类似BST插入,除此之外还要对节点进行染色
。那么问题来了,毕竟是红黑树嘛到底是染成黑色还是红色?
1.若染成黑色
,那么就会一定会违背规则4
,即黑色节点数目不相同,之后还需要重新调整红黑树,要知道红黑树调整是很复杂的,若是改写成代码那估计得累死人。
2.若染成红色
,此时一定不会违背规则4
,不过这有可能
会违背规则3
,即有连续两个节点是红色
的。虽说还需要进行调整,不过这代码量相比之前就会少很多了…基于此,染成红色
是正确的选择。
插入完成后往往需要修正Fixup
树结构,而修正过程需要旋转Rotate
。
1 |
|
InsertFixup
插入操作所引起的不平衡主要是以下8种类型(主要针对插入在红色节点之后):
LLr、LRr、RRr、RLr、LLb、LRb、RRb、RLb。
图中u表示pu的左孩子、pu表示gu的左孩子、gr表示gu的右孩子,也就是pu的兄弟,u的叔叔。而LLb的意思是:pu是gu的左孩子、u是pu的左孩子,且gu的另外一个孩子(可以是Nil节点)是黑色的。
可以总结为下面这两种类型,插入新节点后的平衡主要是对新插入节点u、其父节点pu、祖父节点gu以及叔叔节点gl/gr
来操作的。
如果叔叔节点不存在一定是Nil黑色节点
!!!
根据叔叔节点uncle
的颜色是红色或黑色,InsertFixup大致可以分为以下两种类型:
- uncle节点是
红色
,也就是LLr、LRr、RRr、RLr
类型,直接换色
即可完成红黑树平衡; - uncle节点是
黑色
,也就是LLb、LRb、RRb、RLb
类型,需要旋转和换色。
LLr、LRr、RRr、RLr
处理这类不平衡问题,只需要换色即可,这是因为父节点和叔叔节点
此时一定是红色
的,那么祖父节点
也一定是黑色
的。
这个过程是这样的:
- 若
父节点pu/parent存在且为红色
,则执行该过程;否则将根节点root
染成为黑色
并结束; - 将
父节点pu/parent和叔叔节点gl/gr/uncle
染成黑色; - 将
祖父节点gu
染成红色; - 移动当前
新插入红色节点u
到祖父节点gu
,重复执行第一步骤。
第4步的作用是确保整棵红黑树均符合其规则,因此将祖父节点gu
染成红色之后,可能祖父节点gu的父节点是红色
,那么还需要再次向上修正,直到某个节点的父节点不存在(根节点)或其父节点是黑色节点。
例子:
插入节点30,导致形成LLr不平衡,将父节点和叔叔节点
与祖父节点
换色后移动u到gu,此时再判断其父节点为nullptr表示达到了根节点root,因此修正结束,并将根节点root染成黑色。
其他3种情况处理类似。
LLb、LRb、RRb、RLb
这4种情况只需解释其中一种就能够举一反三了。
处理过程如下:
- 若
父节点pu/parent存在且为红色
,则执行该过程;否则将根节点root
染成为黑色
并结束; - 根据
插入节点u
位于父节点pu
的哪一侧对父节点pu
旋转:若u在pu左边,对pu右旋;否则左旋; - 旋转完成后对
父节点pu/parent和叔叔节点gl/gr/uncle(如果存在)
与祖父节点gu
交换颜色;(实际上,只需要对父节点和祖父节点换色) - 根据
祖父节点gu
位于祖父节点gu父节点pgu
的哪一侧对祖父节点gu
旋转:若gu在pgu左边,对gu右旋;否则左旋。
注意,这种类型无需向上修正:移动当前新插入红色节点u到祖父节点gu,再重复执行第一步骤
,这是因为经过第2步旋转换色后,此时父节点pu
一定是黑色
的,那么下一次再旋转后,此时新的祖父节点gu
也一定是黑色的。
例子:
向这棵红黑树插入节点35,可以看出这是LRb型,虽然祖父节点40的右孩子是Nil节点。先是对父节点30左旋后再交换祖父节点40(黑)和父节点35(红)的颜色(此处叔叔节点为Nil,因此没有换色),然后对祖父节点40右旋后完成了修正。
实际上,LRb型经过左旋
转化为LLb型,同样RLb型经过右旋
转化为RRb型。
再看一个例子,其大致过程:插入节点41后形成LLr
型,那么交换祖父节点45
和父节点44、叔叔节点46
的颜色;移动u到gu位置后发现此时u存在父节点且为红色
,那么还得继续修正;而此时是LRb
型,故先对父节点40
左旋后还要交换祖父节点50
和父节点45、叔叔节点60
的颜色;之后再对祖父节点45
右旋;最后还要将根节点root
染成黑色,至此红黑树平衡,修正结束。
演示过程
C++代码
1 |
|
删除
红黑树删除类似BST,删除操作的前半部分代码一样,差别在于删除后红黑树的修正。事实上删除操作的修正要十分复杂,要考虑的情况较多。
- 在红黑树中查找该节点是否存在;
- 若存在左子树和右子树,寻找
前驱/后继节点
将其转化为只有一个子树/叶子
情况; - 根据
child节点
、child的兄弟节点
、child的父节点
修正删除后的红黑树; - 删除该节点。
1 |
|
RemoveFixup
给出下图的删除操作所引起的不平衡情况模板
其中白色节点
处于未定型状态
,表示可以为黑/红/节点甚至Nil节点,但根节点一定是黑色节点。节点u
表示删除节点的child节点
。
我们首先讨论删除黑色节点
的复杂情况。而且是上图的第一个模板,另一个也是类似的(旋转方向相反)。
删除黑色节点
删除黑色节点引起的不平衡大致有4种情况:
- Case1:
兄弟节点brother
为红色
; - Case2:
兄弟节点brother
为黑色
,而且brother
的两个child
也都是黑色; - Case3:
兄弟节点brother
为黑色
,而且brother
的leftchild
是红色,rightchild
是黑色; - Case4:
兄弟节点brother
为黑色
,而且brother
的rightchild
是红色。
Case1
这种情况下是兄弟节点brother
为红色
,那么parent节点
一定黑色。修正过程为:
- 将
兄弟节点brother
染成黑色
; - 将
u的父节点parent
染成红色
; - 对
parent
进行左旋
; - 移动
brother
到u的父节点parent
的右孩子rightchild
。
注意,这种情况下修正还没有结束!
假设存在如下红黑树,删除节点a后为case 1
情况,然而经过第一次修正发现并没有完全平衡,不过经过case 1
却意外的进入了case 2/3/4
,那么就继续修正。
Case2
这种情况是:brother
为黑色
,而且brother
的两个child
也都是黑色。修正的方法如下:
- 将
brother
染成红色
; - 移动
u
到其父节点parent
;
至此,再根据u
(图中的B
)的颜色可以分两种情况:
u
是红色
,结束修正同时把u
染成黑色
;u
是黑色且不是根节点root
,则继续下一轮修正过程,再根据不同情况进行修正。
Case3
这种情况是:brother
为黑色
,而且brother
的leftchild
是红色,rightchild
是黑色。修正的方法如下:
- 将
brother
的左孩子leftchild
染成黑色
; - 将
brother
染成红色
; - 对
brother
右旋; - 移动
brother
到u的父节点parent
的右孩子rightchild
。
Case4
这是最后一种情况了:brother
为黑色
,而且brother
的rightchild
是红色。修正方法:
- 将
brother
染成u的父节点parent
的颜色(黑或红); - 将
parent
染成黑色; - 将
brother
的右孩子rightchild
染成黑色; - 对
parent
左旋; - 移动
u
移至根节点root
,用于结束修正循环(图中节点b只是起演示作用,不一定为root); - 最后修改根节点root颜色为黑色。
总结以上4种情况,它们之间的转化关系大概如下:
- Case1->Case2/3/4
- Case3->Case4
- Case1->Case3->Case4
修正完Case4就说明红黑树平衡了
Case5
其实这类情况最简单了,也就是删除一个黑色节点p
,但其子节点child
是一个红色节点
,无论黑色节点p的父节点是黑色还是红色。这样的话根本没必要再去考虑上述4种情况了。
- 删除黑色节点,如果存在
红色child节点
,那么将其染成黑色
。
删除红色节点
删除红色节点可能是删除叶子节点或者含有子树的节点。前者很容易实现,对于后者需要找到一个前驱/后继节点
,而这个前驱/后继节点可能是黑色或红色的。如果是红色,那就删除该红色前驱/后继节点并向上修正直到平衡;如果是黑色,那么就判断不同的情况case1/2/3/4/5
并进行修正;
删除红色节点55,前驱节点53也是红色节点
删除红色节点65,前驱节点60是黑色节点,需要进入case3
和case4
修正过程;
删除红色节点65,后继节点67是红色节点。
例子
为了说明情况,现在以下面这棵红黑树为例子来说明删除操作。
删除黑色节点55
,由于其子节点为Nil
,故形成如下的case4
:
- 将
兄弟节点57
染成u节点Nil
的父节点56
的红色
; - 将
父节点56
染成黑色
和兄弟节点57
的右节点58
染成黑色
; - 对
父节点56
左旋; - 移动
u
移至根节点root,结束修正循环; - 修改
根节点root
颜色为黑色。
最终效果
删除黑色节点58
,由于其子节点也为Nil
,故形成如下的case2
:
- 将
兄弟节点56
染成红色
; - 移动
u
到其父节点57
; - 由于
u
是红色
的,因此把父节点57
染成黑色
; - 结束修正。
最终效果
现在删除黑色节点60
,由于其存在左右子树,因此需要寻找前驱/后继节点,此处寻找得前驱黑色节点57
,替换前驱黑色节点57
键值到黑色节点60
。此时转化为删除前驱黑色节点57
后形成case5
,由于其子节点56
为红色,故删除了前驱黑色节点57
后,将子节点56
染成黑色
并结束修正。
上述演示过程
C++代码
1 |
|
结尾
红黑树实在是太复杂了,还得慢慢来~关于红黑树和AVL树差别,可以看看 https://stackoverflow.com/questions/13852870/red-black-tree-over-avl-tree
篇幅有限,红黑树全部源码就不全放出来了,毕竟也参考了别人写的,仅供学习罢了~
有兴趣的可以去看看本文红黑树大概实现源码:源码链接
总之,红黑树上红黑果,红黑树下你和我~
bye~
参考
红黑树-维基百科
Red Black Tree: Intro(簡介)
2-3树与红黑树
《数据结构、算法与应用 C++语言描述》
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!