我所理解的红黑树(RBT)

红黑树(Red–Black Tree)是一种自平衡二叉查找树,用于实现关联数组。它在1972年由鲁道夫·贝尔(Rudolf Bayer)发明,被称为"对称二叉B树"。

2-3树

由于红黑树过于复杂,因此在讲述之前我们先来大致了解一下2-3树,2-3树类似红黑树,也是平衡树,时间复杂度均为O(logn)O(\log n)
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个子节点eg[i j],且 e<ff<g<h[i j]>h

查找

2-3树的查找类似bst,比如查找上图的g

  1. 首先g和d比较,g>d,查找右子树
  2. f<g<h,进入中子树
  3. 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年写的一篇论文。红黑树的结构复杂,但它的操作有着良好的最坏情况运行时间,并且在实践中高效:它可以在 logN\log N 时间内完成查找,插入和删除,这里的 NN 是树中元素的数目。

红黑树相对于AVL树来说,牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作,整体来说性能要优于AVL树。

根据2-3树转化为红黑树可以这样定义红黑树,或者是规则

  • 红黑树一定是二叉搜索树,因为2-3树也是二叉搜索树;
  • 根节点和所有外部节点(Nil)都是黑色,根据2-3树转化为左偏红黑树可看出来;
  • 在根至外部节点(Nil)路径上,没有连续两个节点是红色的;
  • 在所有根至外部节点的路径上,黑色节点的数目相同,即黑高相等。

如果再添加这一规则红色节点位于左侧,那么这个红黑树是一棵左偏红黑树。不过本文主要是介绍普通的红黑树。
上述规则3和规则4是极其重要的,但凡涉及插入和删除操作都是要使红黑树满足这两条规则。

本文红黑树C++类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class RedBlackTree{
private:
RBNodeEntry *m_RB_Root;
RBNodeEntry *m_Nil;
public:
RedBlackTree();
RedBlackTree(int key,int data);
~RedBlackTree();
bool Insert(int key,int data);
bool Remove(int key);
RBNodeEntry* Search(RBNodeEntry* pNode,int key);

void ClearAll(RBNodeEntry*& root);
RBNodeEntry* successor(RBNodeEntry* pnode);
RBNodeEntry* predecessor(RBNodeEntry* pnode);
int Height(RBNodeEntry* pnode){
if(pnode==m_Nil)return 0;
int hl= Height(pnode->leftChild);
int hr= Height(pnode->rightChild);
return std::max(hl,hr)+1;
}
RBNodeEntry* &root(){return this->m_RB_Root;}
void PreOrder(RBNodeEntry* pnode);
void InOrder(RBNodeEntry* pnode);
void PostOrder(RBNodeEntry* pnode);
void LevelOrder(RBNodeEntry* pnode);

void leftRotate(RBNodeEntry *pnode);
void rightRotate(RBNodeEntry *pnode);

void RedBlack_insertFixup(RBNodeEntry* pnode);
void RedBlack_removeFixup(RBNodeEntry* pnode);
};

哨兵节点

本文红黑树利用了哨兵节点技巧,省去了判断nullptr的麻烦,不过BST部分代码需要稍微修改。

由于哨兵节点也是RBNodeEntry结构,但哨兵节点无父节点,因此设置为nullptr;同时还需要设置其leftChildrightChild指向自身。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
RedBlackTree::RedBlackTree(){
this->m_RB_Root=nullptr;
// 哨兵节点
this->m_Nil=new RBNodeEntry;
this->m_Nil->color=BLACK;
this->m_Nil->key=-1;
this->m_Nil->data=0xffffff;
this->m_Nil->leftChild=this->m_Nil;
this->m_Nil->rightChild=this->m_Nil;
}
RedBlackTree::RedBlackTree(int key,int data):RedBlackTree{}{
this->m_RB_Root=new RBNodeEntry(key,data);
this->m_RB_Root->parent=nullptr;
this->m_RB_Root->leftChild=this->m_Nil;
this->m_RB_Root->rightChild=this->m_Nil;
this->m_RB_Root->color=BLACK;
}

查找

由于红黑树也是平衡树,其查找也为O(logN)O(\log N),查找过程与普通的二叉查找树没有太大区别。不过红黑树和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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
enum COLOR{
RED,
BLACK
};
// 红黑树节点
struct RBNodeEntry{
int key;
int data;
int color;
RBNodeEntry *parent;
RBNodeEntry *leftChild;
RBNodeEntry *rightChild;
RBNodeEntry(){}
RBNodeEntry(int k,int d){
this->key=k;
this->data=d;
this->color=RED;
}
};
void RedBlackTree::leftRotate(RBNodeEntry *pnode){
RBNodeEntry *right = pnode->rightChild;
pnode->rightChild = right->leftChild;

if (right->leftChild != m_Nil)
right->leftChild->parent = pnode;
right->parent = pnode->parent;

// 表示根节点
if (pnode->parent == NULL){
root = right;
/*
parent parent
/ \ / \
pnode brother right brother
/ \ ---> / \
l right pnode y
/ \ / \
x y l x
*/
}else if (pnode->parent->leftChild == pnode){
pnode->parent->leftChild = right;
/*
parent parent
/ \ / \
brother pnode brother right
/ \ ---> / \
l right pnode y
/ \ / \
x y l x
*/
}else{
pnode->parent->rightChild = right;
}
right->leftChild = pnode;
pnode->parent = right;
}

void RedBlackTree::rightRotate(RBNodeEntry *pnode){
RBNodeEntry *left = pnode->leftChild;
pnode->leftChild=left->rightChild;

if(left->rightChild!=m_Nil){
left->rightChild->parent=pnode;
}
left->parent=pnode->parent;
// 根节点
if(pnode->parent==nullptr){
this->m_RB_Root=left;
/*
parent parent
/ \ / \
pnode brother left brother
/ \ ---> / \
left r x pnode
/ \ / \
x y y r
*/
}else if(pnode->parent->leftChild==pnode){
pnode->parent->leftChild=left;
/*
parent parent
/ \ / \
brother pnode brother left
/ \ ---> / \
left r x pnode
/ \ / \
x y y r
*/
}else{
pnode->parent->rightChild=left;
}
left->rightChild=pnode;
pnode->parent=left;
}

插入

红黑树的插入操作类似BST插入,除此之外还要对节点进行染色。那么问题来了,毕竟是红黑树嘛到底是染成黑色还是红色?
1.若染成黑色,那么就会一定会违背规则4,即黑色节点数目不相同,之后还需要重新调整红黑树,要知道红黑树调整是很复杂的,若是改写成代码那估计得累死人。
2.若染成红色,此时一定不会违背规则4,不过这有可能会违背规则3,即有连续两个节点是红色的。虽说还需要进行调整,不过这代码量相比之前就会少很多了…基于此,染成红色是正确的选择。

插入完成后往往需要修正Fixup树结构,而修正过程需要旋转Rotate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
bool RedBlackTree::Insert(int key,int data){
if(this->m_RB_Root==nullptr){
this->m_RB_Root=new RBNodeEntry(key,data);
this->m_RB_Root->leftChild=m_Nil;
this->m_RB_Root->rightChild=m_Nil;
this->m_RB_Root->parent=nullptr;
this->m_RB_Root->color=BLACK;
return true;
}
RBNodeEntry *x=this->m_RB_Root;
RBNodeEntry *p=nullptr;

while (x!=m_Nil){
// 保存父节点p
p=x;
if(key < x->key)
x=x->leftChild;
else if(key > x->key)
x=x->rightChild;
// 已经存在
else{
x->data=data;
return true;
}
}

RBNodeEntry *pnode=new RBNodeEntry(key,data);
pnode->leftChild=m_Nil;
pnode->rightChild=m_Nil;
pnode->color=RED;
pnode->parent=p;

// 判断插入节点位于父节点的哪边
if(key < p->key)
p->leftChild=pnode;
else
p->rightChild=pnode;
// 检查是否满足红黑树的平衡条件并重新平衡
RedBlack_insertFixup(pnode);
return true;
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
void RedBlackTree::RedBlack_insertFixup(RBNodeEntry *pNode){
// 父节点
RBNodeEntry *parent=nullptr;
// 祖父节点
RBNodeEntry *gparent=nullptr;

// 如果父节点存在且为红色
while((parent=pNode->parent) && parent->color==RED){
gparent=parent->parent;
// L-型
if(parent==gparent->leftChild){
RBNodeEntry * uncle=gparent->rightChild;
// LLr/LRr型 叔叔节点是红色,那么直接换色
if(uncle!=m_Nil && uncle->color==RED){
parent->color=BLACK;
uncle->color=BLACK;
gparent->color=RED;
// 从当前祖父节点开始继续向上调整
pNode=gparent;
continue;
// LRb,叔叔节点gr是黑色节点(可以Nil),且当前节点是父节点的右孩子
// 将LRb转化为LLb型
}if(pNode==parent->rightChild){
// 对父节点左旋
leftRotate(parent);
}
// 处理LLb的情况
// 先换色,在旋转
parent->color=BLACK;
gparent->color=RED;
rightRotate(gparent);
}
// R-型
else{
RBNodeEntry *uncle=gparent->leftChild;
// RLr/RRr型 叔叔节点是红色
if (uncle!=m_Nil && uncle->color==RED){
uncle->color=BLACK;
parent->color=BLACK;
gparent->color=RED;
// 继续向上调整
pNode=gparent;
continue;
// RLb型 叔叔是黑色,且当前节点是左孩子
// 转化为 RRb
} if(pNode==parent->leftChild){
rightRotate(parent);
}
// RRb型
parent->color=BLACK;
gparent->color=RED;
leftRotate(gparent);
}
}
// 根节点必须为黑色!
this->m_RB_Root->color=BLACK;
}

删除

红黑树删除类似BST,删除操作的前半部分代码一样,差别在于删除后红黑树的修正。事实上删除操作的修正要十分复杂,要考虑的情况较多。

  • 在红黑树中查找该节点是否存在;
  • 若存在左子树和右子树,寻找前驱/后继节点将其转化为只有一个子树/叶子情况;
  • 根据child节点child的兄弟节点child的父节点修正删除后的红黑树;
  • 删除该节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
bool RedBlackTree::Remove(int key) {
RBNodeEntry *node=Search(this->m_RB_Root,key);
if(!node)return false;

RBNodeEntry *child=m_Nil;
RBNodeEntry *parent=nullptr;

// 存在左子树和右子树,将其转化为只有一个子树/叶子情况
if (node->leftChild!=m_Nil && node->rightChild!=m_Nil) {
// 后继节点,即将是要被删除的节点
RBNodeEntry *successor = this->successor(node);
// 数据替换
node->key=successor->key;
node->data=successor->data;
// 删除后继节点
node=successor;
}
// 若node是叶子节点那么leftChild=rightChild=m_Nil
if(node->leftChild!=m_Nil){
child=node->leftChild;
}else{
child=node->rightChild;
}
// 即使child是Nil也要设置child的parent。因为removeFixup需要parent来修正
child->parent=node->parent;

// 删除的是根节点
if(node->parent==nullptr){
this->m_RB_Root=child;
}else if(node->parent->leftChild==node){
node->parent->leftChild=child;
}else {
node->parent->rightChild=child;
}
if(node->color==BLACK){
RedBlack_removeFixup(child);
}
// 直接删除节点即可
delete node;
node=nullptr;

return true;
}

RemoveFixup

给出下图的删除操作所引起的不平衡情况模板

其中白色节点处于未定型状态,表示可以为黑/红/节点甚至Nil节点,但根节点一定是黑色节点。节点u表示删除节点的child节点

我们首先讨论删除黑色节点的复杂情况。而且是上图的第一个模板,另一个也是类似的(旋转方向相反)。

删除黑色节点

删除黑色节点引起的不平衡大致有4种情况:

  • Case1:兄弟节点brother红色
  • Case2:兄弟节点brother黑色,而且brother两个child也都是黑色;
  • Case3:兄弟节点brother黑色,而且brotherleftchild是红色,rightchild是黑色;
  • Case4:兄弟节点brother黑色,而且brotherrightchild是红色。

Case1

这种情况下是兄弟节点brother红色,那么parent节点一定黑色。修正过程为:

  • 兄弟节点brother染成黑色
  • u的父节点parent染成红色
  • parent进行左旋
  • 移动brotheru的父节点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黑色,而且brotherleftchild是红色,rightchild是黑色。修正的方法如下:

  • brother左孩子leftchild染成黑色
  • brother染成红色
  • brother右旋;
  • 移动brotheru的父节点parent右孩子rightchild

Case4

这是最后一种情况了:brother黑色,而且brotherrightchild是红色。修正方法:

  • 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是黑色节点,需要进入case3case4修正过程;
删除红色节点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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
void RedBlackTree::RedBlack_removeFixup(RBNodeEntry*node) {
// case5:
// 若node是红色,那么把子节点node直接染黑
// 若node是root,那么也把它直接染黑
while (node!=m_RB_Root && node->color==BLACK) {
// node是左节点
if (node==node->parent->leftChild) {
RBNodeEntry *brother=node->parent->rightChild;
/*
case1:
case1最终转化为case2/3/4
1.将兄弟节点brother染成黑色;
2.将node的父节点parent染成红色;
3.对parent进行左旋;
4.移动brother到node的父节点parent的右孩子rightchild。
*/
if(brother->color==RED){
brother->color=BLACK;
node->parent->color=RED;
leftRotate(node->parent);
brother=node->parent->rightChild;
}

/*
case2:(单独处理)
1.将brother染成红色;
2.移动node到其父节点parent;
*/
if(brother->leftChild->color==BLACK&&brother->rightChild->color==BLACK){
brother->color=RED;
node=node->parent;
}
// case3->case4
else {
/*
case3:
1.将brother的左孩子leftchild染成黑色;
2.将brother染成红色;
3.对brother右旋;
4.移动brother到node的父节点parent的右孩子rightchild。
*/
if(brother->rightChild->color==BLACK){
brother->leftChild->color=BLACK;
brother->color=RED;
rightRotate(brother);
brother=node->parent->rightChild;
}
/*
case4:
1.将brother染成node的父节点parent的颜色(黑或红);
2.将parent染成黑色;
3.将brother的右孩子rightchild染成黑色;
4.对parent左旋;
5.移动node移至根节点root,用于结束修正循环。
*/
brother->color=node->parent->color;
node->parent->color=BLACK;
brother->rightChild->color=BLACK;
leftRotate(node->parent);
node=this->m_RB_Root;
}
// node是右节点
}else{
RBNodeEntry *brother=node->parent->leftChild;
// case1->case2/3/4:
if (brother->color == RED) {
brother->color = BLACK;
node->parent->color = RED;
rightRotate(node->parent);
brother = node->parent->leftChild;
}
// case2:
if (brother->leftChild->color == BLACK&&brother->rightChild->color == BLACK) {
brother->color = RED;
node = node->parent;
}else {
// case3:
if (brother->leftChild->color == BLACK){
brother->rightChild->color = BLACK;
brother->color = RED;
leftRotate(brother);
brother = node->parent->leftChild;
}
// case4:
brother->color = node->parent->color;
node->parent->color = BLACK;
brother->leftChild->color = BLACK;
rightRotate(node->parent);
node = this->m_RB_Root;
}
}
}
// 即使node是Nil也染黑
node->color=BLACK;
}

结尾

红黑树实在是太复杂了,还得慢慢来~关于红黑树和AVL树差别,可以看看 https://stackoverflow.com/questions/13852870/red-black-tree-over-avl-tree
篇幅有限,红黑树全部源码就不全放出来了,毕竟也参考了别人写的,仅供学习罢了~
有兴趣的可以去看看本文红黑树大概实现源码:源码链接

总之,红黑树上红黑果,红黑树下你和我~

bye~

参考

红黑树-维基百科
Red Black Tree: Intro(簡介)
2-3树与红黑树
《数据结构、算法与应用 C++语言描述》