(数据结构)C++实现红黑树

#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倍以上，稍后会发布，在效率方面说明我写的红黑树是正确的。