红黑树定义
通过变色和旋转方式来实现存储过程中自平衡的二叉搜索树。保证最坏搜索情况下时间复杂度为 O( n)。
红黑树的性质
- 每个结点为红色或黑色;
- 根结点为黑色;
- 叶子结点(NIL / NULL)是黑色的;
- 不可能有互为父子关系的两个红色结点。
- 对每个结点,从该结点到其所有后代叶子结点的简单路径上,均包含相同数目的黑色结点。
红黑树相关特性
- 一棵有n个内部结点的红黑树,高度**至多为 2 (n - 1)
结构定义
结点结构定义
- 父指针方便自下而上的查找。实现时候注意父子关系一致性。
- 红黑状态标记。注意插入情况下构建结点的颜色。
// 红黑树结点结构定义
typedef struct BrTreeNode
{
// 数据域
BrTreeNodeElementType data;
// 左孩子的指针
BrTreeNode* left;
// 右孩子的指针
BrTreeNode* right;
// 父指针
BrTreeNode* parent;
// 红黑状态标记,默认为红色
bool black = false;
}BrNode, * BrTree;
常量定义 ```c /替代所有NULL的结点/ BrTreeNode nil = {NULL, NULL, NULL, NULL, true};
/根结点指针/ BrTree root = &nil;
- nil ==> 红黑树中**所有Null指向**的替换
- **未满状态**的结点(包括叶子)
- **根结点的parent**
- 根结点 => 所有**存取操作**的**初始**操作元素
> 红黑树的基本操作
![红黑树_左旋&右旋.svg](https://cdn.nlark.com/yuque/0/2021/svg/21873585/1624244809220-aafe4ea1-681c-425b-bded-202164ceaf5c.svg#align=left&display=inline&height=328&margin=%5Bobject%20Object%5D&name=%E7%BA%A2%E9%BB%91%E6%A0%91_%E5%B7%A6%E6%97%8B%26%E5%8F%B3%E6%97%8B.svg&originHeight=328&originWidth=871&size=18048&status=done&style=none&width=871)
- **变色**:红色和黑色之间的转变,在某些插入或删除条件的发生。
- 左旋:实现自平衡的一种方法。对某个**结点x**,**x的父结点**,**x右子树根y**,y**的左子树根β**之间的操作(当前操作对象为x)。
```c
/* 02_红黑树_左旋(对某个结点及其右孩子的操作)*/
void leftRotate_BrT(BrTree& root, BrTree x)
{
// 1. 保存其右孩子
BrTree y = x->right;
// 2. x -> y 连接更改,改为y的左孩子
x->right = y->left;
if (y->left != &nil)
{
y->left->parent = x;
}
// 3. x与其父结点关系
// 无父结点,x即为root
if (x->parent == &nil)
{
root = y;
y->parent = &nil;
}
// 为其左孩子
else if (x == x->parent->left)
{
x->parent->left = y;
y->parent = x->parent;
}
// 为其右孩子
else
{
x->parent->right = y;
y->parent = x->parent;
}
// 4. 调整为 y -> x 的关系,反向
y->left = x;
x->parent = y;
}
- 找到x的右孩子,用指针y保存;
- x 断开与 y的连接,改为连接y的左孩子(存在互相指向,注意父指针别遗忘);
- 指向x的结点,改为指向y(互相指向,别遗忘父指针);
建立新的x与y之间指向(别遗忘父指针)。
- 右旋:参考左旋,操作与之对称,与左旋互为逆过程。对某个结点y,y的父结点,y的左子树根x,x的右子树根β之间的操作。 ```c / 03红黑树右旋(对某个结点及其左孩子的操作)/ void rightRotate_BrT(BrTree& root, BrTree y) { // 1. 保存其左孩子 BrTree x = y->left;
// 2. y -> x的连接更改,改为x的右孩子 y->left = x->right; if (x->right != &nil) { x->right->parent = y; }
// 3. y与上级指针的关系 // 无父指针,则y为根结点 if (y->parent == &nil) { root = x; x->parent = &nil; } // y为父的左 else if (y == y->parent->left) { y->parent->left = x; x->parent = y->parent; } // y为父的右 else { y->parent->right = x; x->parent = y->parent; }
// 4. 调整为 x -> y 的关系,反向 x->right = y; y->parent = x; } ```
红黑树的插入元素操作
先按二叉查找树(BST)方式插入元素。
/* 04_红黑树_插入元素(插入完成,根据情况执行保持平衡的基本操作)*/
Status insertElem_BrT(BrTree& root, BrTreeNodeElementType data)
{
// 1. 根结点为空,直接插入,并返回
if (root == &nil)
{
return buildBrNode_BrT(root, true, data) ? OK : ERROR;
}
// 2. 否则构建红色结点,并执行二叉搜索插入
BrTree toAdd = NULL;
if (!buildBrNode_BrT(toAdd, false, data))
{
return ERROR;
}
brSearchAddElem(root, toAdd);
// 3. 判断红黑特性,决定自平衡操作
insertFixUp_BrT(root, toAdd);
return OK;
}
先判断根结点是否为Null。
/* 根据颜色和数据,构建结点*/
Status buildBrNode_BrT(BrTree& brT, bool black, BrTreeNodeElementType data)
{
brT = (BrTree)malloc(sizeof(BrTreeNode));
if (!brT)
{
printf("构建结点失败!\n");
return ERROR;
}
// 颜色、数据
brT->black = black;
brT->data = data;
// 处理Null
brT->left = &nil;
brT->right = &nil;
brT->parent = &nil;
return OK;
}
- 是。
- 插入即是树根,构建黑色结点。
- 处理Null位置,退出。
- 否。构建红色结点。
- 执行二叉搜索插入。
/* 红黑树基础二叉搜索插入(注意parent指针)*/
void brSearchAddElem(BrTree& brT, BrTree& toAdd)
{
// 关键字大小,小于 ==> 左子树
if (toAdd->data < brT->data)
{
// 为空,连接上,设置父子关系
if (brT->left == &nil)
{
brT->left = toAdd;
toAdd->parent = brT;
return;
}
// 递归其左子树
else
{
brSearchAddElem(brT->left, toAdd);
}
}
// 大于等于 ==> 右子树
else
{
if (brT->right == &nil)
{
brT->right = toAdd;
toAdd->parent = brT;
return;
}
// 递归其右子树
else
{
brSearchAddElem(brT->right, toAdd);
}
}
}
检查红黑特性满足条件,决策执行自平衡操作。
- 父亲为黑色,不影响平衡,不操作。
- 父亲为红色 ==> 一定有黑色的祖父结点。
- 叔叔为红色。
- 父亲和叔叔变黑色;
- 爷爷变红色;
- 当前结点置为爷爷,继续检查。
- 叔叔为黑色(包括Null)
- 祖父、父亲、孩子同向(同左边或同右边)
- 祖父、父亲变色;
- 祖父旋转(同左 ==> 右转,同右 ==> 左转)
- 祖父、父亲、孩子不同向
- 对父亲旋转,使得三代同向。
- 按同向逻辑变色和旋转。
- 祖父、父亲、孩子同向(同左边或同右边)
- 叔叔为红色。
- 红黑树插入自平衡代码
/* 10_红黑树_插入自平衡处理*/
void insertFixUp_BrT(BrTree& root, BrTree cur)
{
// 父亲红色时候,才需要进行平衡
while (!cur->parent->black)
{
// 叔叔结点
BrTree uncle;
// 父亲是祖父左孩子
if (cur->parent == cur->parent->parent->left)
{
// 叔叔(祖父右孩子)
uncle = cur->parent->parent->right;
// 1. 父代均为红色,仅变色
if (!uncle->black)
{
cur->parent->black = true;
uncle->black = true;
cur->parent->parent->black = false;
cur = cur->parent->parent;
// 为红色需重新进入判断
continue;
}
// 2. 叔叔黑,父亲红
// 2.1 当前为父亲的右孩子
else if (cur == cur->parent->right)
{
cur = cur->parent;
leftRotate_BrT(root, cur);
}
// 2.2 当前为父亲左孩子
cur->parent->black = true;
cur->parent->parent->black = false;
rightRotate_BrT(root, cur->parent->parent);
}
// 父亲是祖父右孩子
else
{
// 叔叔(祖父左孩子)
uncle = cur->parent->parent->left;
// 1. 父代均为红色,仅变色
if (!uncle->black)
{
cur->parent->black = true;
uncle->black = true;
cur->parent->parent->black = false;
cur = cur->parent->parent;
continue;
}
// 2. 叔叔黑,父亲红
// 2.1 当前为父亲的左孩子
else if (cur == cur->parent->left)
{
cur = cur->parent;
rightRotate_BrT(root, cur);
}
// 2.2 当前为父亲右孩子
cur->parent->black = true;
cur->parent->parent->black = false;
leftRotate_BrT(root, cur->parent->parent);
}
}
root->black = true;
}
红黑树的删除元素操作
先按二叉查找树(BST)方式删除元素(参考BST删除元素)。 结点定义
- Z ==> 待删除结点
- X ==> 自平衡起始的结点(替代结点)
- Y ==> 按z的孩子数
- 为2时候:y作为z的后继
- 小于2个,y用于保存z的颜色
- 元素没有左孩子,用右其孩子替换(不论右孩子是否为空)。
- 没有右孩子,用其左孩子替换(不论左孩子是否为空)。
- 有两个孩子。需要找其前驱或后继(这里找其后继)。
- 右孩子无左子树,则后继==> 右孩子。
- 右孩子有左子树,后继 ==> 左子树最左的元素。
检查红黑特性满足条件,决策执行自平衡操作。
- 自平衡情况是左右对称的,只需讨论一边的情况,另一边镜像即可。
- 总体思路:先讨论替代节点的红黑情况,再讨论
- 自平衡的结点定义
- 删除自平衡操作。
- 替代结点X 为红色 ==> 变黑即可
- 根据红黑性质【不能有两个连续的红色结点】,推导出【真正删除的结点为黑色】,而父亲的颜色不确定
- 当前①②所在分支少了一个黑结点,黑平衡被破坏,将当前红结点变黑即可解决。
- 替代结点X为黑色
- 兄弟S为红色 ==> 父亲P,左侄子SL,右侄子SR一定为黑色
- 兄弟S,父亲P互换颜色;
- 对P旋转,更新旋转后的兄弟指针指向(图中的SL)。
- 此时所有路径黑结点数未受影响。经过路径①②的黑结点,仍然比其他路径少1个。但情况以转变为如下【兄弟S为黑色】
- 兄弟S为黑色
- 兄弟的左右孩子(SL和SR)均为黑色
- 父亲P为黑色
- 父亲P为红色
- 兄弟的孩子(SL与SR)中存在红色,父亲(P)均可。
- 左孩子SL为红色,SR为黑色。
- SR为红色,SL可红可黑。
- 兄弟的左右孩子(SL和SR)均为黑色
- 兄弟S为红色 ==> 父亲P,左侄子SL,右侄子SR一定为黑色
- 替代结点X 为红色 ==> 变黑即可