红黑树性质
红黑树和基本 不同,不需要频繁进行高度平衡判断,而是使用黑节点的个数,对树型进行维护。
具有以下性质:
- 每个节点只能是黑、红两种颜色的一种
- 根节点一定为黑色,外节点看作黑色
- 不能有两个相连的节点同为红色
- 从根到任何一个外节点的路径上,黑色节点个数相同
其中 性质最为重要,对红黑树的插入、删除更新,都是为满足其性质进行的。
插入
首先需要明确,新插入一个节点时,应该是什么颜色。
考虑如果是黑色,那新节点插入的路径上,黑色个数增加,显然需要向上进行调整,以确保 性质的成立,这就增加了额外的操作。
所以新增加的节点,颜色应为红色。
为解释方便,插入部分各节点关系如下:
其中, 表示左子树, 表示右子树。
为插入的节点,插入时,按照普通二叉查找树的方式进行插入,待新节点插入到位后,再按照以下情况进行调整。
处理过程中,要特别注意对根节点的处理。
这里主要讲解插入节点为左子树的情况,右子树的处理就是其镜像变换,可以通过代码简单描述。
1.0 father为黑
显然,插入后的树满足所有的性质,无需进行更新。
1.1 father、uncle为红
此时,将 变为黑色, 变为红色。但这种处理可能导致 出现双红冲突,所以需要继续对 进行处理(此时 相当于 )。
1.2 father为红,uncle为黑
需注意, 为外节点的话,颜色也是黑色。
1.2.1 fa、No不在同一方向
将 左旋,变为 所属情况,同时待处理的节点变为 。
1.2.2 fa、No在同一方向
将 右旋,同时 颜色互换。
删除
红黑树的删除较为复杂,需针对多种情况进行处理。
此部分的节点关系如下:
其中 为待删除的节点。
2.0 No有两个子树
处理方式同二叉查找树,先将 和后继 交换,然后再进行删除。之后情况便转换为 其中之一。
2.1 No为红色叶节点
直接将 删去即可,并不会影响树的性质,此处 为白色,表示其颜色无需考虑(之后同理)。
2.2 No为黑色,且只有一个子树
此时 唯一的一个子节点一定是红色,将 删除后,用 连接到其子节点,并将子节点颜色改为黑色。
2.3 No为黑色叶节点
2.3.1 br为红色
将 左旋,同时 颜色互换。之后继续在调整后的树上,对 进行调整。
2.3.2 br为黑,远侄子为黑,近侄子为红
此时远侄子一定是外节点,将 右旋,同时 颜色互换,情况变为 ,之后继续在调整后的树上,对 进行调整。
2.3.3 br为黑,远侄子为红
将 左旋,同时 颜色互换, 变为黑色,删除 后, 左儿子为空。
2.3.4 fa为红,br为黑叶子
此时全为外节点,将 删除, 左儿子为空,同时 颜色互换。
2.3.5 fa为黑,br为黑叶子
与 处理方式相同,不过处理完 后,要将 当成新的待处理节点,继续向上更新。
部分代码
节点结构体
struct Node
{
/* 存放数据 */
int data;
/* 颜色,0红,1黑 */
int color;
/* 0左,1右,之后涉及到方向都这么规定 */
Node *next[2];
/* 父亲 */
Node *father;
};
这里将左右子节点的指针放到一个数组中,而不是分别开两个变量,是为了简化后续操作做好准备
旋转
显然,旋转分为左旋和右旋,而不同的旋转,需要操作不同的指针。
但观察旋转方式可以发现,旋转时各指针操作的相对位置是一样的,比如都是保留和自己同方向的子节点,而反方向的子节点接到父节点的同方向。
注意观察,左右子节点的变化规律
因此,借助结构体的定义方式,我们可以通过一个函数,解决所有旋转操作。
/* 将No按照direction反方向旋转 */
/* 如No右旋时,No为左子树,direction=0 */
void rotate(Node *No, int direction)
{
/* 获取No的父亲和祖先 */
Node *fa = No->father, *ffa = fa->father;
/* 对父亲进行更改 */
No->father = fa->father;
fa->father = No;
/* 父亲同方向连接No反方向叶节点 */
fa->next[direction] = No->next[direction ^ 1];
/* 注意子树是否存在 */
if (No->next[direction ^ 1])
No->next[direction ^ 1]->father = fa;
/* 父亲变为反方向叶节点 */
No->next[direction ^ 1] = fa;
/* 根节点特判 */
if (!ffa)
{
root = No;
return;
}
/* 处理祖先 */
if (ffa->next[0] == fa)
ffa->next[0] = No;
else
ffa->next[1] = No;
}
查找
想要完成插入或者删除,则必须先有查找。
/* 查找值域为x的节点,找到返回节点,否则返回最后查找失败的叶节点 */
Node *findNode(const int x)
{
/* 树为空 */
if (!root)
/* 返回无效值 */
return NULL;
/* 从根开始 */
Node *No = root;
while (1)
{
/* 去右子树 */
if (x > No->data)
{
if (No->next[1])
No = No->next[1];
else
return No;
}
/* 去左子树 */
else if (x < No->data)
{
if (No->next[0])
No = No->next[0];
else
return No;
}
/* 找到x */
else
return No;
}
}
插入
插入时,需要先进行查找,如果值存在,则无需插入,否则,在失败叶节点下插入新节点,并对新节点更新。
/* 对No进行更新 */
void insertUpdate(Node *No)
{
while (1)
{
/* getDirection确定No的方向 */
int direction = getDirection(No);
/* 处理到根节点 */
if (direction == -1)
{
/* root_color is black */
No->color = 1;
return;
}
/* 意义同之前的介绍 */
Node *fa, *ffa, *uncle;
fa = No->father;
/* fa黑色,无需处理 */
if (fa->color)
return;
ffa = fa->father;
/* uncle为fa的反向节点 */
uncle = ffa->next[getDirection(fa) ^ 1];
/* 1.1情况 */
if (uncle && uncle->color == 0)
{
/* changeColor改变节点颜色 */
fa->changeColor();
ffa->changeColor();
uncle->changeColor();
No = ffa;
}
/* 1.2情况 */
else
{
/* 1.2.1情况 */
if (ffa->next[direction] != fa)
{
/* 旋转No */
rotate(No, direction);
No = fa;
continue;
}
/* 1.2.2情况 */
rotate(fa, direction);
fa->changeColor();
ffa->changeColor();
return;
}
}
}
/* 插入x */
void insert(const int x)
{
/* 树为空,则直接创建根节点 */
if (!root)
{
root = new Node(x, 1, 0);
return;
}
/* 查找x */
Node *No = findNode(x);
/* 建立右子树 */
if (x > No->data)
{
No->next[1] = new Node(x, 0, No);
/* 对新节点进行更新 */
insertUpdate(No->next[1]);
}
/* 建立左子树 */
else if (x < No->data)
{
No->next[0] = new Node(x, 0, No);
insertUpdate(No->next[0]);
}
}
删除
删除操作较为复杂,尤其是删除黑色叶节点,需要注意顺序,一种一种情况去处理。
/* 针对2.0情况,寻找No的后继 */
Node *removeChange(Node *No)
{
/* Ne是要寻找的后继,初始为No右子树 */
Node *Ne = No->next[1];
/* 不断向下,直到Ne没有左子树 */
while (Ne->next[0])
Ne = Ne->next[0];
/* 交换No,Ne */
No->data = Ne->data;
/* 将后继返回 */
return Ne;
}
/* 针对2.3情况,黑叶子删除后的更新 */
void removeblackNode(Node *No)
{
while (1)
{
/* 确定No方向 */
int direction = getDirection(No);
/* 处理到根节点为止 */
if (direction == -1)
{
No->color = 1;
return;
}
/* fa,brother(br)意义同介绍 */
Node *fa = No->father;
/* br是No反向节点 */
Node *brother = fa->next[direction ^ 1];
/* 2.3.1情况 */
if (brother->color == 0)
{
rotate(brother, direction ^ 1);
swap(fa->color, brother->color);
}
/* br为黑色 */
else if (brother->color == 1)
{
/* 2.3.3情况 */
if (brother->next[direction ^ 1] && brother->next[direction ^ 1]->color == 0)
{
rotate(brother, direction ^ 1);
swap(fa->color, brother->color);
brother->next[direction ^ 1]->color = 1;
return;
}
/* 2.3.2情况 */
else if (brother->next[direction] && brother->next[direction]->color == 0)
{
swap(brother->color, brother->next[direction]->color);
rotate(brother->next[direction], direction);
}
/* br是黑叶子 */
else
{
/* 2.3.4情况 */
if (fa->color == 0)
{
fa->changeColor();
fa->next[direction ^ 1]->changeColor();
return;
}
/* 2.3.5情况 */
else
{
fa->next[direction ^ 1]->changeColor();
/* 继续处理fa */
No = fa;
}
}
}
}
}
/* No删除后的更新 */
void removeUpdate(Node *No)
{
while (1)
{
/* 确定No方向 */
int direction = getDirection(No);
Node *fa = No->father;
/* No为叶节点 */
if (!(No->next[0] || No->next[1]))
{
/* 根节点特判 */
if (No == root)
{
root = NULL;
/* 处理结束 */
goto removeUpdateEnd;
}
/* 2.1情况 */
else if (No->color == 0)
{
fa->next[direction] = NULL;
goto removeUpdateEnd;
}
/* 2.3情况 */
else
{
/* 针对5种情况处理 */
removeblackNode(No);
No->father->next[direction] = NULL;
goto removeUpdateEnd;
}
}
/* 2.0情况,No两个子树 */
else if (No->next[0] && No->next[1])
No = removeChange(No);
/* 2.2情况,No只有一个子树 */
else
for (int i = 0; i <= 1; ++i)
if (No->next[i])
{
/* 注意根节点的特殊处理 */
if (fa)
fa->next[direction] = No->next[i];
if (No == root)
root = No->next[i];
No->next[i]->father = fa;
No->next[i]->color = 1;
goto removeUpdateEnd;
}
}
removeUpdateEnd:
/* 更新完成后再删除No */
delete No;
}
/* 删除值为x的节点 */
void remove(const int x)
{
/* 查找x */
Node *No = findNode(x);
/* 树为空 || 值为x的节点不存在 , 无需处理 */
if (!No || No->data != x)
return;
/* 进行删除和更新 */
removeUpdate(No);
}
总结
红黑树的代码算是平衡树中比较复杂的,不过虽然看起来代码冗长和复杂,其实就是对之前分析的几种情况的模拟,以上红黑树主要实现部分的代码,删去注释和多余的括号空行后,大概180多行,对于一个复杂的平衡树代码来说,已经算是很正常的了。大部分数据结构的原理都比较简单,代码实现才是难点。