红黑树的定义 🔗
红黑树：
- 每个节点不是红色就是黑色
- 根节点（第一个节点）是黑色
- 叶子结点都是黑色
- 一定没有连在一起的红色节点 （每个红色节点的两个子节点都是黑色）
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
操作 🔗
主要涉及：插入，删除和查找。
红黑树是二叉搜索树BST，所以查找与BST相同。 插入和删除节点可能会导致不符合红黑树的性质，调整过程稍微复杂。
插入节点 🔗
过程： 1 以二叉树搜索树的方式插入新增红色节点node。
2 如果node的parent节点是黑色的，很完美，红黑树的性质维持，END插入过程。
3 如果node的parent节点是红色的，红色节点连在一起，违反性质4。通过颜色调换（color flips）和树旋转来调整
名词与概念。 🔗
G
P U
N
插入的节点标为N，N的父节点标为P，N的祖父节点标为G，N的叔父节点标为U。
左旋： 左旋当前的节点则节点会变成左孩子。
右旋： 右旋当前的节点则节点会变成右孩子。
左旋 🔗
/*
* 对红黑树的节点(x)进行左旋转
*
* 左旋示意图(对节点x进行左旋)：
* px px
* / /
* x y
* / \ --(左旋)--> / \ #
* lx y x ry
* / \ / \
* ly ry lx ly
*
*
*/
static void rbtree_left_rotate(RBRoot *root, Node *x)
{
// 设置x的右孩子为y
Node *y = x->right;
// 将 “y的左孩子” 设为 “x的右孩子”；
// 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
x->right = y->left;
if (y->left != NULL)
y->left->parent = x;
// 将 “x的父亲” 设为 “y的父亲”
y->parent = x->parent;
if (x->parent == NULL)
{
//tree = y; // 如果 “x的父亲” 是空节点，则将y设为根节点
root->node = y; // 如果 “x的父亲” 是空节点，则将y设为根节点
}
else
{
if (x->parent->left == x)
x->parent->left = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
else
x->parent->right = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
}
// 将 “x” 设为 “y的左孩子”
y->left = x;
// 将 “x的父节点” 设为 “y”
x->parent = y;
}
比较好理解的插入实现 🔗
typedef struct t_red_black_node {
enum {red, black} color;
int data // void *item;
t_red_black_node *left, *right, *parent;
} Node;
typedef struct t_red_black {
Node *root;
} Tree;
void bst_insert(Tree *T, Node *x) {
if T->root == NULL {
T->root = x;
T->root->color = black;
return;
}
Node *cur = T->root;
Node *parent;
while (cur != NULL) {
parent = cur
if (cur->data > x->data) {
cur = cur->left;
} else {
cur = cur -> right;
}
}
x->parent = parent;
if (parent->data > x->data) {
parent->left = x;
} else {
parent->right = x;
}
}
// 先向插入bst一样插入新增节点，然后fixup到rb-tree
void rb_insert(Tree *T, Node *x) {
bst_insert(T, x);
x->color = red;
while ( (x != T->root) && (x->parent->color == red) ) {
if (x->parent == x->parent->parent->left) {
// parent在Grand parent的左边
uncle = x->parent->parent->right;
if (uncle->color == red) {
// uncle 是红色， 颜色反转，x move up to grand parent
x->parent->color = black;
uncle->color = black;
x->parent->parent->color = red;
x = x->parent->parent;
} else {
// uncle 是黑色
if (x == x->parent->right) {
//x 是 parent的右孩子， x move up to parent, left rotate
x = x->parent
left_rotate(T, x);
}
x->parent->color = black;
x->parent->parent-color = red;
right_rotate(T, x->parent->parent);
}
}else {
// parent在Grand parent的右边
uncle = x->parent->parent->left;
if (uncle-color == red) {
x->parent->color = black;
uncle->color = black;
x->parent->parent->color = red;
x = x->parent->parent;
} else {
if ( x == x->parent->left) {
x = x->parent;
right_rotate(T, x);
}
x->parent->color = black;
x->parent->parent->color =red;
left_rotate(T, x->parent->parent);
}
}
}
T->root->color = black;
}
插入 wiki上的递归实现 🔗
insert case1 🔗
新节点N位于树的根上，没有父节点。
void insert_case1(node *n){
if(n->parent == NULL)
n->color = BLACK;
else
insert_case2 (n);
}
insert case2 🔗
新节点N有父亲节点，且新节点的父节点P是黑色。 红黑树的性质维持。
void insert_case2(node *n){
if(n->parent->color == BLACK)
return; /* 树仍旧有效*/
else
insert_case3 (n);
}
后续的case3， 4， 5，新节点的父节点为红色时的过程。
insert case3 🔗
如果父节点P和叔父节点U二者都是红色。
过程： 重绘为parent和uncle为黑色并重绘祖父节点G为红色，操作节点指向Grand Parent转到case1。
void insert_case3(node *n){
if(uncle(n) != NULL && uncle (n)->color == RED) {
n->parent->color = BLACK;
uncle (n)->color = BLACK;
grandparent (n)->color = RED;
insert_case1(grandparent(n));
}
else
insert_case4 (n);
}
在余下的情形下，我们假定父节点P是其祖父G的左子节点。如果它是右子节点，情形4和情形5中的左和右应当对调
insert case4 🔗
父节点P是红色而叔父节点U是黑色或缺少，并且新节点N是其父节点P的右子节点而父节点P又是其父节点的左子节点。
过程：进行一次左旋转调换新节点和其父节点的角色。按情形5处理以前的父节点P以解决仍然失效的性质4。
void insert_case4(node *n){
/*
Grand
parent
N
*/
if(n == n->parent->right && n->parent == grandparent(n)->left) {
rotate_left(n);
n = n->left;
} else if(n == n->parent->left && n->parent == grandparent(n)->right) {
/*
Grand
parent
N
*/
rotate_right(n);
n = n->right;
}
insert_case5 (n);
}
insert case5 🔗
父节点P是红色而叔父节点U是黑色或缺少，新节点N是其父节点的左子节点，而父节点P又是其父节点G的左子节点。
过程：
void insert_case5(node *n){
n->parent->color = BLACK;
grandparent (n)->color = RED;
/*
Grand
parent
N
*/
if(n == n->parent->left && n->parent == grandparent(n)->left) {
rotate_right(n->parent);
} else {
/*
Grand
parent
N
*/
/* Here, n == n->parent->right && n->parent == grandparent (n)->right */
rotate_left(n->parent);
}
}
删除节点 🔗
...
参考 🔗
[1] 红黑树C语言的实现 [2] wiki [3][ 红黑树插入过程] (https://www.cs.auckland.ac.nz/software/AlgAnim/red_black_op.html) [3] linux kernel rbtree [4]