数据结构之高级树

线索二叉树、哈夫曼树、AVL树、伸展树、B树、B+树、B*树、R树、红黑树概念与总结


线索二叉树

线索二叉树主要用来解决树的遍历问题,普通的二叉树遍历时,需要使用栈结果来做重复的操作。线索二叉树不需要如此,在遍历的同时,使用二叉树中空闲的内存空间记录某些结点的前趋和后继元素的位置(不是全部)。这样在算法后期需要遍历二叉树时,就可以利用保存的结点信息,提高了遍历的效率。使用这种方法构建的二叉树,即为“线索二叉树”。
接点结构体:

1
2
3
4
5
6
7
8
9
10
11
12
typedef enum {
Link,
Thread
} PointTag;
struct BiThrNode {
BiThrNode *left;
BiThrNode *right;
int val;
PointTag Ltag;
PointTag Rtag;
};

对二叉树进行线索化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
BiThrNode *pre = NULL;
void InThreading(BiThrNode *p) {
if (p != NULL) {
InThreading(p->left);
if (p->left == NULL) {
p->Ltag = Thread;
p->left = pre;
}
if (pre && (pre->right == NULL)) {
p->Rtag = Thread;
pre->right = p;
}
pre = p;
InThreading(p->right);
}
}

进行线索化的树结构如下所示:
线索二叉树

线索二叉树

中序遍历线索二叉树:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InOrderThreading(BiThrNode *p) {
BiThrNode *next = p;
while (next != NULL) {
while (next != NULL) next = p->left;
cout << next->val << " ";
while (next->Rtag == Thread && next->right != NULL) {
next = next->right;
cout << next->val << " ";
}
next = next->right;
}
}


哈夫曼树

首先介绍几个名词。

  • 路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。
  • 路径长度:在一条路径中,每经过一个结点,路径长度都要加 1 。
  • 结点的权:给每一个结点赋予一个新的数值,被称为这个结点的权。
  • 结点的带权路径长度:指的是从根结点到该结点之间的路径长度与该结点的权的乘积。
  • 树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。

什么是哈夫曼树?

当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为“最优二叉树”,有时也叫“赫夫曼树”或者“哈夫曼树”。
在构建哈弗曼树时,要使树的带权路径长度最小,只需要遵循一个原则,那就是:权重越大的结点离树根越近。

构建哈夫曼树

对于给定的有各自权值的 n 个结点,构建哈夫曼树有一个行之有效的办法:
1.在 n 个权值中选出两个最小的权值,对应的两个结点组成一个新的二叉树,且新二叉树的根结点的权值为左右孩子权值的和;
2.在原有的 n 个权值中删除那两个最小的权值,同时将新的权值加入到 n–2 个权值的行列中,以此类推;
3.重复 1 和 2 ,直到所以的结点构建成了一棵二叉树为止,这棵树就是哈夫曼树。
哈夫曼树

哈夫曼树

哈夫曼树算法

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
#include <iostream>
using namespace std;
typedef struct {
int weight; // 权重
int parent; // 父节点在数组中的位置下标
int left; // 左节点在数组中的位置下标
int right; // 右节点在数组中的位置下标
}HTNode, *HuffmanTree;
void Select(HuffmanTree HT, int *m1, int *m2, int n) {
int min1 = INT8_MAX;
int min2 = INT8_MAX;
for (int i=1; i<=n; i++) {
if (HT[i].parent != 0) continue;
if (HT[i].weight < min1) {
min2 = min1;
min1 = HT[i].weight;
*m2 = *m1;
*m1 = i;
} else if (HT[i].weight >= min1 && HT[i].weight < min2) {
min2 = HT[i].weight;
*m2 = i;
}
}
}
void createHuffmanTree(HuffmanTree *HT, int w[], int n) {
if (n <= 1) return;
int m = 2*n-1; // 总节点数
*HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
HuffmanTree p = *HT;
for (int i=1; i<=m; ++i) {
p[i].weight = i<=n?w[i-1]:0;
p[i].parent = 0;
p[i].right = 0;
p[i].left = 0;
}
// 构建哈夫曼树
for (int i=n+1; i<=m; ++i) {
int m1, m2;
Select(*HT, &m1, &m2, i-1);
p[m1].parent = p[m2].parent = i;
p[i].left = m1;
p[i].left = m2;
p[i].weight = p[m1].weight + p[m2].weight;
}
}
void print(HuffmanTree HT, int n) {
int m = 2*n-1;
for (int i=1; i<=m; ++i) {
cout << (HT+i)->weight << " ";
}
cout << endl;
}
int main() {
int w[5] = {2, 8, 7, 6, 8};
HuffmanTree HT;
createHuffmanTree(&HT, w, 5);
print(HT, 5);
return 0;
}

哈夫编码

哈夫曼编码就是在哈夫曼树的基础上构建的,这种编码方式最大的优点就是用最少的字符包含最多的信息内容。文本中字符出现的次数越多,在哈夫曼树中的体现就是越接近树根。编码的长度越短。


AVL树

AVL树又称为高度平衡的二叉搜索树。它能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度。
AVL树的性质:

  • 左子树和右子树的高度之差的绝对值不超过1;
  • 树中的每个左子树和右子树都是AVL树;
  • 每个节点都有一个平衡因子(balance factor),任一节点的平衡因子是-1,0,1。(每个节点的平衡因子等于左子树的高度减去右子树的高度 ) 。

    基本术语和操作

    有四种情况可能会导致AVL树失衡,分别为:
    (1)LL:插入一个新节点到根节点的左子树(Left)的左子树(Left),导致根节点的平衡因子由1变为2;
    (2)RR:插入一个新节点到根节点的右子树(Right)的右子树(Right),导致根节点的平衡因子由-1变为-2;
    (3)LR:插入一个新节点到根节点的左子树(Left)的右子树(Right),导致根节点的平衡因子由1变为2;
    (4)RL:插入一个新节点到根节点的右子树(Right)的左子树(Left),导致根节点的平衡因子由-1变为-2;


    针对四种种情况可能导致的不平衡,可以通过旋转使之变平衡。有两种基本的旋转:
    (1)左旋转:将根节点旋转到(根节点的)右孩子的左孩子位置;
    (2)右旋转:将根节点旋转到(根节点的)左孩子的右孩子位置;
    旋转方式一共有四种:左旋转,右旋转,左右旋转,右转旋转

    LL左旋转

    RR右旋转

    LR左右旋转

    RL右左旋转

    实现

    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
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    struct AVLTreeNode {
    AVLTreeNode *left;
    AVLTreeNode *right;
    int val;
    int height;
    AVLTreeNode(int val) : val(val), left(NULL),
    right(NULL), height(0) {}
    };
    int height(const AVLTreeNode *node) {
    if (node == NULL) return 0;
    return node->height;
    }
    AVLTreeNode *leftRotate(AVLTreeNode *node) {
    AVLTreeNode *tmp = node->left;
    node->left = tmp->right;
    tmp->right = node;
    node->height = max(height(node->left), height(node->right)) + 1;
    tmp->height = max(height(tmp->left), height(tmp->right)) + 1;
    return tmp;
    }
    AVLTreeNode *rightRotate(AVLTreeNode *node) {
    AVLTreeNode *tmp = node->right;
    node->right = tmp->left;
    tmp->left = node;
    node->height = max(height(node->left), height(node->right)) + 1;
    tmp->height = max(height(tmp->left), height(tmp->right)) + 1;
    return tmp;
    }
    AVLTreeNode *leftRightRotate(AVLTreeNode *node) {
    node->left = leftRotate(node->left);
    return rightRotate(node);
    }
    AVLTreeNode *rightLeftRotate(AVLTreeNode *node) {
    node->right = rightRotate(node->right);
    return leftRotate(node);
    }
    AVLTreeNode *insertNode(AVLTreeNode *root, int val) {
    if (root == NULL) {
    root = new AVLTreeNode(val);
    } else if (val < root->val) {
    root->left = insertNode(root->left, val);
    if (height(root->left) - height(root->right) == 2) {
    if (val < root->left->val) {
    root = leftRotate(root);
    } else {
    root = leftRightRotate(root);
    }
    }
    } else if (val > root->val){
    root->right = insertNode(root->right, val);
    if (height(root->right) - height(root->left) == 2) {
    if (val > root->right->val) {
    root = rightRotate(root);
    } else {
    root = rightLeftRotate(root);
    }
    }
    }
    root->height = max(height(root->left), height(root->right)) + 1;
    return root;
    }
    AVLTreeNode *maxNode(AVLTreeNode *root) {
    AVLTreeNode *maxAN = NULL;
    while (root != NULL) {
    maxAN = root;
    root = root->right;
    }
    return maxAN;
    }
    AVLTreeNode *minNode(AVLTreeNode *root) {
    AVLTreeNode *maxAN = NULL;
    while (root != NULL) {
    maxAN = root;
    root = root->left;
    }
    return maxAN;
    }
    AVLTreeNode *deleteNode(AVLTreeNode *root, int val) {
    if (root == NULL) return NULL;
    if (val < root->val) {
    root->left = deleteNode(root->left, val);
    if (height(root->right) - height(root->left) == 2) {
    AVLTreeNode *r = root->right;
    if (height(r->right) > height(r->left)) {
    root = rightLeftRotate(root);
    } else {
    root = rightRotate(root);
    }
    }
    } else if (val > root->val){
    root->right = insertNode(root->right, val);
    if (height(root->left) - height(root->right) == 2) {
    AVLTreeNode *r = root->right;
    if (height(r->right) > height(r->left)) {
    root = leftRightRotate(root);
    } else {
    root = leftRotate(root);
    }
    }
    } else {
    if (root->left != NULL && root->right != NULL) {
    if (height(root->left) > height(root->right)) {
    AVLTreeNode *maxAN = maxNode(root->left);
    root->val = maxAN->val;
    root->left = deleteNode(root->left, maxAN->val);
    } else {
    AVLTreeNode *maxAN = minNode(root->right);
    root->val = maxAN->val;
    root->right = deleteNode(root->right, maxAN->val);
    }
    } else {
    AVLTreeNode *tmp = root;
    root = root->left != NULL?root->left:root->right;
    free(tmp);
    }
    }
    return root;
    }

伸展树

伸展树主要特点是不会保证树一直是平衡的,但各种操作的平摊时间复杂度是O(log(n)),因而,从平摊复杂度上看,二叉查找树也是一种平衡二叉树。另外,相比于其他树状数据结构(如红黑树,AVL树等),伸展树的空间要求与编程复杂度要小得多。
伸展树的出发点是这样的:考虑到局部性原理(刚被访问的内容下次可能仍会被访问,查找次数多的内容可能下一次会被访问),为了使整个查找时间更小,被查频率高的那些节点应当经常处于靠近树根的位置。这样,很容易得想到以下这个方案:每次查找节点之后对树进行重构,把被查找的节点搬移到树根,这种自调整形式的二叉查找树就是伸展树。每次对伸展树进行操作后,它均会通过旋转的方法把被访问节点旋转到树根的位置。
为了将当前被访问节点旋转到树根,我们通常将节点自底向上旋转,直至该节点成为树根为止。“旋转”的巧妙之处就是在不打乱数列中数据大小关系(指中序遍历结果是全序的)情况下,所有基本操作的平摊复杂度仍为O(log(n))。
其旋转方式与AVL相同,对于访问的元素,通过LL,RR,LR,RL操作将其旋转到根节点位置处。


B树

动态查找树有二叉查找树(BST)、平衡二叉查找树(BBST)、红黑树(RBT)、B-Tree/B+Tree/B*-tree(B树)。
B树主要用于存储系统中,在大规模的存储系统中,文件的索引节点非常多,而如果使用平衡二叉树这样的结构做搜索,元素过多,查找可能就会退化成线性查找了,这样的二叉树由于深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下。B树是通过减少树的高度,增加节点元素,提高查询效率的。

规则

  • 树种的每个节点最多拥有m个子节点且m>=2,空树除外(注:m阶代表一个树节点最多有多少个查找路径,m阶=m路,当m=2则是2叉树,m=3则是3叉);
  • 除根节点外每个节点的关键字数量大于等于ceil(m/2)-1小于等于m-1个;
  • 所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;
  • 如果一个非叶节点有N个子节点,则该节点的关键字数等于N-1;
  • 所有节点关键字是按递增次序排列,并遵循左小右大原则。

B树查询流程

B树
比如要查找字母E,所有字母按照字典序排序,查找流程如下:

  • 获取根节点的关键字进行比较,当前根节点关键字为M,E要小于M,所以往找到指向左边的子节点(二分法规则,左小右大,左边放小于当前节点值的子节点、右边放大于当前节点值的子节点);
  • 拿到关键字D和G,D<E<G 所以直接找到D和G中间的节点;
  • 拿到E和F,因为E=E 所以直接返回关键字和指针信息(如果树结构里面没有包含所要查找的节点则返回null)。

B树插入流程

定义一个5阶树(平衡5路查找树;),现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;
遵循规则:

  • 当前是要组成一个5路查找树,那么此时m=5,关键字数必须大于等于cei(5/2)小于等于5-1(关键字数小于cei(5/2) -1就要进行节点合并,大于5-1就要进行节点拆分,非根节点关键字数>=2);
  • 满足节点本身比左边节点大,比右边节点小的排序规则。
    B树
    B树
    B树

B树删除流程

  • 当前是要组成一个5路查找树,那么此时m=5,关键字数必须大于等于cei(5/2)-1,小于等于5-1,非根节点关键字数大于2;
  • 满足节点本身比左边节点大,比右边节点小的排序规则;
  • 关键字数小于二时先从子节点取,子节点没有符合条件时就向向父节点取,取中间值往父节点放;
    B树

特点

B树
B树的结构定义:

1
2
3
4
5
6
typedef struct {
int file_num; // 文件数
char *file_name[max_file_num]; // 文件名
BTNode *BTptr[max_file_num+1]; // 指向子节点的指针
FILE_HARD_ADDR offset[max_file_num]; // 文件在硬盘中的存储位置
}

一般来说,一个磁盘块的大小是4K,磁盘进行IO请求时都是以块为单位的,也就是B树作为磁盘或者数据库的索引结构时,其关键字的个数限制在磁盘块范围,B树节点内部采用二分查找,由于其层级相对于平衡二叉树来说减少了很多,查询效率也增大了很多。


B+树

B+树是B树的一种变形,更适合应用于实际应用中操作系统的文件索引和数据库索引。定义如下:

  • 除根节点外的内部节点,每个节点最多有m个关键字,最少有ceil(m/2)个关键字,其中每个关键字对应一个子树;
  • 所有的叶子节点包含了全部的关键字以及这些关键字指向文件的指针,并且:
    • 所有叶子节点中的关键字按大小顺序排列;
    • 相邻的叶子节点顺序链接(相当于是构成了一个顺序链表);
    • 所有叶子节点在同一层。
  • 所有分支节点的关键字都是对应子树中关键字的最大(或最小)值。
    B+树

B+树相对B树来说,有以下的特点:

  • B+树的磁盘读写代价更低
    • B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
  • B+树的查询效率更加稳定
    • 由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

B*树

B*树是B+树的变体,在B+树的基础上,B*树增加了非根和非叶子结点指向兄弟结点的指针,B树关键字初始化个数为ceil(2/3\m),即磁盘块的最低使用率为2/3。
B*树
B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针。
B树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。
所以,B
树分配新结点的概率要比B+树要低,空间使用率更高。


R树

R树相对于B树或者B+树来说,主要解决的是多维空间查找问题。B树和B+树可以很好的处理一维空间存储的问题,如果涉及到多维空间上的查找,就要用到R树。R树在数据库等领域做出的功绩是非常显著的。它很好的解决了在高维空间搜索等问题。举个R树在现实领域中能够解决的例子:查找20英里以内所有的餐厅。如果没有R树你会怎么解决?一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中,一个字段记录经度,另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息,然后计算是否满足要求。如果一个地区有100家餐厅的话,我们就要进行100次位置计算操作了,如果应用到谷歌地图这种超大数据库中,这种方法便必定不可行了。
R树


红黑树

红黑树本质上也是一棵二叉查找树,但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

性质

  • (1)每个节点或者是黑色,或者是红色;
  • (2)根节点是黑色;
  • (3)每个叶子结点都是黑色(NULL结点是黑结点);
  • (4)如果一个节点是红色的,则他的子结点必须是黑色的;
  • (5)从一个节点到该结点的子孙结点的所有路径上包含相同数目的黑结点。

红黑树

时间复杂度

红黑树的时间复杂度为:O(logn)

添加

将一个节点插入到红黑树中,需要执行哪些步骤呢?首先,将红黑树当作一颗二叉查找树,将节点插入;然后,将节点着色为红色;最后,通过旋转和重新着色等方法来修正该树,使之重新成为一颗红黑树。详细描述如下:

  • 第一步: 将红黑树当作一颗二叉查找树,将节点插入。
    • 红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉查找树。也就意味着,树的键值仍然是有序的。此外,无论是左旋还是右旋,若旋转之前这棵树是二叉查找树,旋转之后它一定还是二叉查找树。这也就意味着,任何的旋转和重新着色操作,都不会改变它仍然是一颗二叉查找树的事实。
  • 第二步:将插入的节点着色为”红色”,将插入结点变为红色不会违背第(1)条性质。
  • 第三步: 通过一系列的旋转或着色等操作,使之重新成为一颗红黑树。
    • 对于”特性(1)”,显然不会违背了。因为我们已经将它涂成红色了;
    • 对于”特性(2)”,显然也不会违背。在第一步中,我们是将红黑树当作二叉查找树,然后执行的插入操作。而根据二叉查找数的特点,插入操作不会改变根节点。所以,根节点仍然是黑色;
    • 对于”特性(3)”,显然不会违背了。这里的叶子节点是指的空叶子节点,插入非空节点并不会对它们造成影响;
    • 对于”特性(4)”,是有可能违背的!
      可以将“当节点被着色为红节点,并插入二叉树”划分为三种情况处理。
  • 第一种情况:被插入的节点是根节点 –> 处理方法:直接把此节点涂为黑色;
  • 第二种情况:被插入的节点的父节点是黑色 –> 处理方法:什么也不需要做。节点被插入后,仍然是红黑树;
  • 第三种情况:被插入的节点的父节点是红色 –> 那么,该情况与红黑树的“特性(4)”相冲突。这种情况下,被插入节点是一定存在非空祖父节点的;进一步的讲,被插入节点也一定存在叔叔节点(即使叔叔节点为空,我们也视之为存在,空节点本身就是黑色节点)。理解这点之后,我们依据”叔叔节点的情况”,将这种情况进一步划分为3种情况(Case)。
现象说明 处理策略
Case1 当前节点的父节点是红色,且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色。 (01) 将“父节点”设为黑色。
(02) 将“叔叔节点”设为黑色。
(03) 将“祖父节点”设为“红色”。
(04) 将“祖父节点”设为“当前节点”(红色节点);即,之后继续对“当前节点”进行操作。
Case2 当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的右孩子 (01) 将“父节点”作为“新的当前节点”。
(02) 以“新的当前节点”为支点进行左旋。
Case3 当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的左孩子 (01) 将“父节点”设为“黑色”。
(02) 将“祖父节点”设为“红色”;
(03) 以“祖父节点”为支点进行右旋。

删除

将红黑树内的某一个节点删除。需要执行的操作依次是:首先,将红黑树当作一颗二叉查找树,将该节点从二叉查找树中删除;然后,通过”旋转和重新着色”等一系列来修正该树,使之重新成为一棵红黑树。详细描述如下:

  • 第一步:将红黑树当作一颗二叉查找树,将节点删除。
    • 被删除节点没有儿子,即为叶节点。那么,直接将该节点删除就OK了。
    • 被删除节点只有一个儿子。那么,直接删除该节点,并用该节点的唯一子节点顶替它的位置。
    • 被删除节点有两个儿子。那么,先找出它的后继节点;然后把“它的后继节点的内容”复制给“该节点的内容”;之后,删除“它的后继节点”。在这里,后继节点相当于替身,在将后继节点的内容复制给”被删除节点”之后,再将后继节点删除。这样就巧妙的将问题转换为”删除后继节点”的情况了,下面就考虑后继节点。 在”被删除节点”有两个非空子节点的情况下,它的后继节点不可能是双子非空。既然”的后继节点”不可能双子都非空,就意味着”该节点的后继节点”要么没有儿子,要么只有一个儿子。若没有儿子,则按”情况一”进行处理;若只有一个儿子,则按”情况二 “进行处理。
  • 第二步:通过”旋转和重新着色”等一系列来修正该树,使之重新成为一棵红黑树。
    在第一步中”将红黑树当作一颗二叉查找树,将节点删除”后,可能违反”特性(2)、(4)、(5)”三个特性。第二步需要解决上面的三个问题,进而保持红黑树的全部特性。
    为了便于分析,我们假设”x包含一个额外的黑色”(x原本的颜色还存在),这样就不会违反”特性(5)”。为什么呢?
    我们知道:删除节点y之后,x占据了原来节点y的位置。 既然删除y(y是黑色),意味着减少一个黑色节点;那么,再在该位置上增加一个黑色即可。这样,当我们假设”x包含一个额外的黑色”,就正好弥补了”删除y所丢失的黑色节点”,也就不会违反”特性(5)”。 因此,假设”x包含一个额外的黑色”(x原本的颜色还存在),这样就不会违反”特性(5)”。
    现在,x不仅包含它原本的颜色属性,x还包含一个额外的黑色。即x的颜色属性是”红+黑”或”黑+黑”,它违反了”特性(1)”。
    现在,我们面临的问题,由解决”违反了特性(2)、(4)、(5)三个特性”转换成了”解决违反特性(1)、(2)、(4)三个特性”。RB-DELETE-FIXUP需要做的就是通过算法恢复红黑树的特性(1)、(2)、(4)。RB-DELETE-FIXUP的思想是:将x所包含的额外的黑色不断沿树上移(向根方向移动),直到出现下面的姿态:
  • x指向一个”红+黑”节点。此时,将x设为一个”黑”节点即可。
  • x指向根。此时,将x设为一个”黑”节点即可。
  • 非前面两种姿态。

将上面的姿态,可以概括为3种情况:

  • 情况说明:x是“红+黑”节点 –> 处理方法:直接把x设为黑色,结束。此时红黑树性质全部恢复。
  • 情况说明:x是“黑+黑”节点,且x是根 –> 处理方法:什么都不做,结束。此时红黑树性质全部恢复。
  • 情况说明:x是“黑+黑”节点,且x不是根 –> 这种情况又可以划分为4种子情况。这4种子情况如下表所示:
现象说明 处理策略
Case1 x是”黑+黑”节点,x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。 (01) 将x的兄弟节点设为“黑色”。
(02) 将x的父节点设为“红色”。
(03) 对x的父节点进行左旋。
(04) 左旋后,重新设置x的兄弟节点。
Case2 x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色。 (01) 将x的兄弟节点设为“红色”。
(02) 设置“x的父节点”为“新的x节点”。
Case3 x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的。 (01) 将x兄弟节点的左孩子设为“黑色”。
(02) 将x兄弟节点设为“红色”。
(03) 对x的兄弟节点进行右旋。
(04) 右旋后,重新设置x的兄弟节点。
Case4 x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的,x的兄弟节点的左孩子任意颜色。 (01) 将x父节点颜色 赋值给 x的兄弟节点。
(02) 将x父节点设为“黑色”。
(03) 将x兄弟节点的右子节设为“黑色”。
(04) 对x的父节点进行左旋。
(05) 设置“x”为“根节点”。

参考资料
哈夫曼树(赫夫曼树、最优树)及C语言实现
线索二叉树的创建及对其遍历的C语言实现
B树与B+树
平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了
从B 树、B+ 树、B* 树谈到R 树
红黑树(一)之 原理和算法详细介绍
伸展树(Splay tree)图解与实现