红黑树C++实现（转）

参考 https://www.cnblogs.com/xidian-mao/p/11014825.html

#include <bits/stdc++.h>
using namespace std;
#define RED 1
#define BLACK 0
#define RBnode node<T> *
template <class T>
struct node {
	T key;
	int sum; //sum子树节点数
	bool color;
	node *p, *left, *right;
	node() {
		sum = 0; color = BLACK;
	}
	node(T key, int sum, int color, node *p, node *left, node *right) :
		key(key), sum(sum), color(color), p(p), left(left), right(right) {}
	void up() {
		sum = 1 + left->sum + right->sum; // nil节点不更新
	}
};

template <class T>
class  RBtree {
private:
	RBnode rt;
	RBnode nil;
public:
	RBtree() {
		nil = new node<T>();
		nil->p = nil->left = nil->right = nil;
		rt = nil;
	}

	void mid_print(RBnode x) { // 中序遍历
		if (x == nil) return;
		mid_print(x->left);
		cout << "key: " << x->key << " color:" << x->color << " sum: " << x->sum << endl;
		mid_print(x->right);
	}

	void  my_print() {
		mid_print(rt);
	}

	void insert(T key) {
		RBnode z = new node<T>(key, 1, RED, nil, nil, nil);
		RBnode y = nil; // y: x的parent;
		RBnode x = rt;
		while (x != nil) {
			y = x;
			if (z->key <= x->key)
				x = x->left;
			else
				x = x->right;
		}
		z->p = y;  // 特别的根节点父节点是nil
		if (y == nil)
			rt = z;
		else if (z->key <= y->key)
			y->left = z;
		else
			y->right = z;
		// sum的改变
		while (y != nil) {
			y->up();
			y = y->p;
		}
		insert_fixup(z);
	}

	// 可能违反的性质:
	// 1)z的parent节点颜色是红色
	// 2)根节点是红色 
	void insert_fixup(RBnode z) {  // 插入看叔叔节点 
		while (z->p->color == RED) {
			if (z->p == z->p->p->left) {
				RBnode uncle = z->p->p->right;
				if (uncle->color == RED) { // case1 叔叔节点是红色; 叔叔和父亲加一层黑色,祖父层变黑(黑色上移)
					z->p->color = BLACK;
					uncle->color = BLACK;
					z->p->p->color = RED;
					z = z->p->p;
				}
				else {
					if (z->p->right == z) { // case2 叔叔是黑色, 祖孙三代不在一条直线, 调整到case3 
						z = z->p;
						left_rotate(z);
					}
					z->p->color = BLACK;  // case3 调整过后,冲突解决
					z->p->p->color = RED;
					right_rotate(z->p->p);
				}
			}
			else {
				RBnode uncle = z->p->p->left;
				if (uncle->color == RED) { // case1
					z->p->color = BLACK;
					uncle->color = BLACK;
					z->p->p->color = RED;
					z = z->p->p;
				}
				else {
					if (z->p->left == z) { // case 2
						z = z->p;
						right_rotate(z);
					}
					z->p->color = BLACK;  // case 3
					z->p->p->color = RED;
					left_rotate(z->p->p);
				}
			}
		}
		rt->color = BLACK;
	}

	// 旋转的性质: 左旋或右旋后,交换两节点的颜色不改变黑高(自我总结)
	void left_rotate(RBnode x) {
		RBnode y = x->right;
		x->right = y->left;
		if (y->left != nil)
			y->left->p = x;
		y->p = x->p;
		if (x->p == nil)
			rt = y;
		else if (x->p->left == x)
			x->p->left = y;
		else
			x->p->right = y;
		y->left = x;
		x->p = y;
		if (x != nil) x->up(); // 先调整x,再调整y
		if (y != nil) y->up();
	}

	void right_rotate(RBnode x) {
		RBnode y = x->left;
		x->left = y->right;
		y->p = x->p;
		if (y->right != nil)
			y->right->p = x;
		if (x->p == nil)
			rt = y;
		else if (x->p->left == x)
			x->p->left = y;
		else
			x->p->right = y;
		y->right = x;
		x->p = y;
		if (x != nil) x->up();
		if (x != nil) y->up();
	}

	RBnode min_mum(RBnode x) {
		while (x->left != nil)
			x = x->left;
		return x;
	}

	RBnode max_mum(RBnode x) {
		while (x->right != nil)
			x = x->right;
		return x;
	}

	RBnode low_find(int k) { // 寻找比k小且最大的节点
		return _low(k, rt);
	}

	RBnode _low(int k, RBnode x) {
		if (x == nil) return x;
		if (k <= x->key) return _low(k, x->left);
		else {
			RBnode ans = _low(k, x->right);
			if (ans != nil) return ans;
			else          return x;
		}
	}

	RBnode upp_find(T k) { // 寻找比k大且最小的节点
		return _upp(k, rt);
	}

	RBnode _upp(T k, RBnode x) {
		if (x == nil) return x;
		if (k >= x->key) return _upp(k, x->right);
		else {
			RBnode ans = _upp(k, x->left);
			if (ans != nil) return ans;
			else          return x;
		}
	}

	RBnode rfind(T key) {  // 相等元素的最后一个节点
		RBnode x = rt;
		while (x != nil) {
			if (key < x->key)
				x = x->left;
			else if (key > x->key)
				x = x->right;
			else
				return x;
		}
		return x;
	}

	RBnode find(T key) {  // 相等元素第一个节点
		return my_find(key, rt);
	}

	RBnode my_find(T key, RBnode x) {
		if (x == nil) return nil;
		if (key < x->key) return my_find(key, x->left);
		if (key == x->key) {
			RBnode ans = my_find(key, x->left);
			if (ans == nil) return x;
			else          return ans;
		}
		return my_find(key, x->right);
	}

	RBnode find_kth(int k) {  // 排名第k的元素, 相等的元素具有不同的排名
		RBnode x = rt;
		if (rt->sum < k) return nil;
		while (k != x->left->sum + 1) {
			if (k <= x->left->sum)
				x = x->left;
			else {
				k -= x->left->sum + 1;
				x = x->right;
			}
		}
		return x;
	}

	int get_rank(RBnode x) { // 寻找节点x的排名
		RBnode t = rt; int k = 0;
		while (t != x) {
			if (x->key <= t->key)
				t = t->left;
			else {
				k += t->left->sum + 1;
				t = t->right;
			}
		}
		return k + t->left->sum + 1;
	}
	int get_rank(T key) { // 寻找key的排名
		RBnode x = find(key);
		if (x == nil)return -1;
		return get_rank(x);
	}

	void transplate(RBnode y, RBnode x) {  // 以节点x代替y,但不对y的子节点经行替换
		if (y->p == nil)
			rt = x;
		else if (y->p->left == y)
			y->p->left = x;
		else
			y->p->right = x;
		x->p = y->p;
	}

	void remove(RBnode z) {  // y: 要删除的节点  x: 代替的节点
		RBnode y = z;
		RBnode x;
		int ycolor = y->color;
		if (y->left == nil) {
			x = y->right;
			transplate(y, x);
		}
		else if (y->right == nil) {
			x = y->left;
			transplate(y, x);
		}
		else {
			y = min_mum(y->right);
			ycolor = y->color;
			x = y->right;
			if (y->p == z)
				x->p = y;  // x可能是nil节点,因此需要记录其父亲
			else {
				transplate(y, x);
				y->right = z->right;
				z->right->p = y;
			}
			transplate(z, y);
			y->left = z->left;
			z->left->p = y;
			y->color = z->color; // y代替z,但颜色不改变!!!!!!
			y = z;  // y指向废弃节点
		}
		if (ycolor == BLACK)
			remove_fixup(x);
		RBnode t = x->p; // 最后调整sum
		while (t != nil) {
			t->up();
			t = t->p;
		}
		delete y;
	}
	void remove(T key) {
		RBnode z = find(key);
		if (z == nil)return;
		remove(z);
	}

	// 可能有冲突:
	// 1)经过x的路径,黑高减1
	// 2)x的为红色,x的parent也是红
	// 3)x为根节点,颜色为红色
	void remove_fixup(RBnode x) { // 看兄弟节点 // 减少x多的一重黑色
		while (x != rt && x->color == BLACK) {
			if (x == x->p->left) {
				RBnode bro = x->p->right;
				if (bro->color == RED) { // case1 兄弟节点为红色,转化为情况234 
					bro->color = BLACK;
					bro->p->color = RED;
					left_rotate(x->p);
					bro = x->p->right;
				}
				if (bro->left->color == BLACK && bro->right->color == BLACK) { // case2 兄弟节点及其儿子节点都为黑色
					bro->color = RED;
					x = x->p;
				}
				else {
					if (bro->right->color == BLACK) { // case3 兄弟右节点不为红色
						bro->color = RED;
						bro->left->color = BLACK;
						right_rotate(bro);
						bro = x->p->right;
					}
					bro->right->color = BLACK; //case4   兄弟右孩子节点为红色,调整之后结束循环
					bro->color = bro->p->color;
					bro->p->color = BLACK;
					left_rotate(x->p);
					x = rt; // 终止递归
				}
			}
			else {
				RBnode bro = x->p->left;
				if (bro->color == RED) { // case 1
					bro->color = BLACK;
					bro->p->color = RED;
					right_rotate(x->p);
					bro = x->p->left;
				}
				if (bro->left->color == BLACK && bro->right->color == BLACK) { // case 2
					bro->color = RED;
					x = x->p;
				}
				else {
					if (bro->left->color == BLACK) { // case 3
						bro->color = RED;
						bro->right->color = BLACK;
						left_rotate(bro);
						bro = x->p->left;
					}
					bro->left->color = BLACK; // case 4
					bro->color = bro->p->color;
					bro->p->color = BLACK;
					right_rotate(x->p);
					x = rt;
				}
			}
		}
		x->color = BLACK;
	}

	RBnode successor(RBnode x) { // 后继节点
		if (x->right != nil)
			return min_mum(x->right);
		RBnode y = x->p;
		while (y != nil && y->right == x) {
			x = y;
			y = y->p;
		}
		return y;
	}

	RBnode predecessor(RBnode x) { // 前继
		if (x->left != nil)
			return max_mum(x->left);
		RBnode y = x->p;
		while (y != nil && y->left == x) {
			x = y;
			y = y->p;
		}
		return y;
	}

};