发布时间:2023-07-31 15:00
#include
typedef int T1;
struct node {
T1 key, rank; //key是结点的值,rank是后面测试红黑树正确性要用到,可忽略
bool color; //节点颜色
node* left, * right, * pre; //左右子节点、父节点
};
struct rbt {
node* root = NULL, * w; //树根,初始值为NULL
bool red = true, black = false; //红色为真,黑色为假
void pcset(node* p, node* t, bool isleft) {//该函数将p设为t的父节点,若p为NULL则t是树根
(p != NULL ? (isleft ? p->left : p->right) : root) = t;
if (t) t->pre = p;
}
void rotate(node* t, bool isleft) { //旋转函数,isleft决定左旋右旋
node* tmp = isleft ? t->right : t->left;
pcset(t, isleft ? tmp->left : tmp->right, !isleft);
pcset(t->pre, tmp, t->pre && t->pre->left == t);
pcset(tmp, t, isleft);
}
node* find(T1 key) {//按key的值查找函数
node *t=root,*p=NULL;
while (t && t->key != key) t = key < (p = t)->key ? t->left : t->right;
return t ? t : p;
}
node* insert(T1 key) { //按key插入函数
node* pre = find(key), * t, * p, * gpre;
if (pre && pre->key == key) return pre; //如果插入的值已经存在,返回
p = t = new node{ key,0,red,NULL,NULL,NULL }; //否则新建一个节点,节点颜色为红
pcset(pre, t, pre && pre->key > key); //把节点挂在树上
while ((pre = t->pre) && pre->color) { //如果出现红红连在一起,则需要调整
node * gpre = pre->pre;
bool isleft = gpre->left == pre;
if (isleft != (t == pre->left)) rotate(t = pre, isleft);//左右左旋,右左右旋
t->color = black; //改变t的颜色为黑
t = t->pre;
rotate(gpre, !isleft); //旋转祖父节点
}
root->color = black; //保证根节点是黑色
return p;
}
void fix(node* pre, node* t, bool isleft) { //删除后的调整函数
while (t != root && (!t || !t->color)) {
node* other = isleft ? pre->right : pre->left; //兄弟节点
if (other->color) { //如果兄弟节点是红
rotate(pre, isleft); //则旋转父节点
other->color = !(pre->color = red); //父节点设为红,兄弟节点为黑
other = isleft ? pre->right : pre->left; //重新设置兄弟节点
}
node* x = other->left, * y = other->right;
if ((!x || !x->color) && (!y || !y->color)) {
other->color = red;
pre = (t = pre)->pre;
}
else{
if (isleft) swap(x, y);
if (!x || !x->color) {
rotate(other, !isleft);
other->color=red;
(other = y)->color = black;
x = isleft ? y->right : y->left;
}
rotate(pre, isleft);
other->color = pre->color;
pre->color = x->color = black;
t = root;
}
isleft = pre && pre->left == t;
}
if (t) t->color = black;
}
void erase(T1 key) { //删除节点的函数
node* t = find(key), * tmp = t;
if (!t || t->key != key) return; //删除的节点不存在,返回
if (t->left && t->right) { //如果删除的节点有左右孩子
t = t->right;
while (t->left) t = t->left; //找到删除的节点的中序遍历后继节点
tmp->key = t->key; //把要删的对象换成后继节点,删前转移其值
}
tmp = t->left ? t->left : t->right; //保留删除的节点的孩子
bool is = t->pre && t->pre->left == t;
pcset(t->pre, tmp, is); //重新设置父子关系
if (!t->color) fix(t->pre, tmp, is); //如果删的是黑节点,就要调整
delete t;
}
void postorder(node* t, node*& tmp, node* pre) {//后序遍历函数,拷贝构造和析构会用到
if (!t) return;
if (w) tmp = new node{ t->key,t->rank,t->color, NULL,NULL,pre };
postorder(t->left, tmp->left, tmp);
postorder(t->right, tmp->right, tmp);
if (!w) delete t;
}
rbt() {} //构造函数
rbt(const rbt& t) { postorder(w = t.root, root, NULL); }//拷贝构造
~rbt() { postorder(root, root, w = NULL); } //析构函数
};
正确性检验:用树形结构把整棵树的结构打印出来,结果是正确的。至于如何打印树形结构在我另一篇文章中有代码实现 :链接。
其中一张图如下,带#号的节点就是红色节点,其余都是黑色节点,其他图就不一一展示
效率检验:我把写的红黑树封装成set或map容器和stl中的set或map容器作比较,结果是比stl快4倍以上,稍后会发布,在效率方面说明我写的红黑树是正确的。