红黑树实现
1、五个性质
(1）根节点黑色
(2) 只有红色和黑色节点
(3) 红色节点相邻节点黑色
(4) 每个节点到任意子树叶子节点黑色节点个数相同
(5) 叶子节点黑色
2、插入
插入节点颜色为红色
(1) 根节点为null 直接赋值
(2) 插入节点父亲节点为黑色结束
(3) 插入节点父亲节点颜色为红色
1、叔叔节点颜色为红色
b r
/ \ / \
r r -> b b
/ /
(r) (r)
2、叔叔节点为黑色
b b
/ \ / \
r b -> (r) r
/ \
(r) b
or
b b
/ \ / \
r b -> (r) b
\ /
(r) r
我的实现
if (rt->color == RED && par->color == RED) {
Node *grand = par->parent;
bool fc = (grand->ch[1] == par);
Node *uncle = grand->ch[fc ^ 1];
/*
* b r
* / \ / \
* r r -> b b
* / /
* (r) (r)
*
*/
if (uncle->color == RED) {
uncle->color = par->color = BLACK;
grand->color = RED;
} else {
bool c = (par->ch[1] == rt);
/**
* b b
* / \ / \
* r b -> (r) r
* / \
* (r) b
*/
if (c == fc) {
par->color = BLACK;
grand->color = RED;
rotate(par);
} else {
/**
* b b
* / \ / \
* r b -> (r) b
* \ /
* (r) r
*/
rotate(rt);
pushUp(rt->ch[c ^ 1]);
}
}
}
3、删除
找到前继节点或者后继节点，颜色不变，值互换下，然后开始删前继或者后继节点，这个时候删除其实有9种情况
(1) 根节点直接删
(2) 红色节点直接删
(3) 删除节点父亲节点为红色，父亲变黑
(4) 子节为红色的，变黑
然后就是红黑树里面最蛋疼的地方了一共五种情况，我们已经删除了节点，要开始平衡红黑树，看代码
/**
* delete balance
* @param rt
*/
void RedBlackTree::balance(Node *rt) {
if (rt == root) {
return;
}
Node *par = rt->parent;
bool c = par->isRightChild();
Node *brother = par->ch[c ^ 1];
/**
*
* B (B)
* / \ / \
* (B) B -----> B R
* / \ / \
* B B B B
*/
if (par->color == BLACK && brother->color == BLACK && brother->ch[c] == BLACK
&& brother->ch[c ^ 1] == BLACK) {
brother->color = RED;
balance(par);
return;
}
/**
* B1 B3
* / \ ----> /
* (B)2 R3 R1
* /
* (B)2
*
* grantee that brother is not red in the following
*/
if (brother->color == RED) {
std::swap(brother->color, par->color);
rotate(brother);
}
/**
* R (B)
* / \ / \
* (B) B -----> B R
* / \ / \
* B B B B
*/
assert(brother->color == BLACK);
brother = par->ch[c ^ 1];
if (par->color == RED && brother->color == BLACK && brother->ch[c] == BLACK
&& brother->ch[c ^ 1] == BLACK) {
std::swap(par->color, brother->color);
balance(par);
return;
}
/**
* X X
* / \ / \
* (B) B2 --> (B) B1
* / \ \
* R1 B3 R2
* \
* B3
*/
Node *left = brother->ch[c];
if (left->color == RED) {
std::swap(brother->color, left->color);
rotate(left);
}
/**
* X1 X2
* / \ / \
* (B) B2 -----> B1 B4
* / \ / \
* X3 R4 (B) X3
*/
Node *right = brother->ch[c ^ 1];
if (right->color == RED) {
std::swap(brother->color, par->color);
right->color = BLACK;
rotate(brother);
}
}
我的旋转代码 当前节点往父亲节点旋，这个可以根据自己的喜好来
void RedBlackTree::rotate(Node *rt) {
Node *father = rt->parent;
Node *grand = father->parent;
bool c = (father->ch[1] == rt);
bool fc = (grand->ch[1] == father);
Node *&ch = rt->ch[c ^ 1];
father->ch[c] = ch;
if (ch != nullNode) {
ch->parent = father;
}
ch = father;
ch->parent = rt;
rt->parent = grand;
grand->ch[fc] = rt;
if (father == root) {
root = rt;
}
maintain(father);
maintain(rt);
}
