求助红黑树

#include <bits/stdc++.h>

using namespace std;

#define Bro(x) (ch[fthr[x]][0] == x ? ch[fthr[x]][1] : ch[fthr[x]][0])
#define Chd(x) (ch[fthr[x]][0] == x ? 0 : 1)
const int MaxN = 1e6 + 100, INF = 0x7fffffff;
typedef enum ColorType {RED, BLACK, WU} ColorType;
int val[MaxN], size[MaxN], cnt[MaxN], ch[MaxN][2], fthr[MaxN];
ColorType color[MaxN];
int tot, root = 0;

int NewNode (int x, int v) {
	++ tot;
	val[tot] = x;
	cnt[tot] = size[tot] = 1;
	ch[tot][0] = ch[tot][1] = 0;
	fthr[tot] = v;
	color[tot] = RED;
	return tot;
}

void PushUp (int p) {
	size[p] = size[ch[p][0]] + size[ch[p][1]] + cnt[p];
	if (p != root && p != 0) {
		PushUp (fthr[p]);
	}
}

void Build () {
	root = NewNode (-INF, 0);
	color[root] = BLACK;
	ch[root][1] = NewNode (INF, root);
	color[ch[root][1]] = BLACK;
	PushUp (ch[root][1]);
}

void Rotate (int &p, int d) {
	int Tmp = ch[p][d ^ 1];
	ch[p][d ^ 1] = ch[Tmp][d];
	ch[Tmp][d] = p;
	p = Tmp;
	PushUp (ch[p][d]);
}

int Rank (int p, int x) {
	if (! p) return 1;
	else if (x == val[p]) return size[ch[p][0]] + 1; 
	else if (x < val[p]) return Rank (ch[p][0], x);
	else if (x > val[p]) return size[ch[p][0]] + cnt[p] + Rank (ch[p][1], x);
}

int Val (int p, int rank) {
	if (! p) return 0;
	else if (rank <= size[ch[p][0]]) return Val (ch[p][0], rank);
	else if (rank <= size[ch[p][0]] + cnt[p]) return val[p];
	else return Val (ch[p][1], rank - size[ch[p][0]] - cnt[p]);
}

int Pre (int p, int x) {
	int id = 1, pre;
	while (id) {
		if (val[id] < x) pre = val[id], id = ch[id][1];
		else id = ch[id][0];
	}
	return pre;
}

int Next (int p, int x) {
	int id = 1, next;
	while (id) {
		if (val[id] > x) next = val[id], id = ch[id][0];
		else id = ch[id][1];
	}
	return next;
}

int Find (int p, int x, int id, int father = 0) {
	if (! p) {
		if (id == 0) return INF;
		else return father;
	}
	else if (x < val[p]) return Find (ch[p][0], x, id, p);
	else if (x > val[p]) return Find (ch[p][1], x, id, p);
	else if (x == val[p]) return p;
}

void DoubleRed1 (int p) {
	if (p == root) {
		color[p] = BLACK;
		return ;
	} else if (color[fthr[p]] == BLACK) {
		return ;
	} else {
		color[fthr[fthr[p]]] = RED;
		color[fthr[p]] = BLACK;
		color[Bro (fthr[p])] = BLACK;
		DoubleRed1 (fthr[fthr[p]]);
	}
}

void DoubleRed2 (int p) {
	if (Chd (fthr[p]) == 0) {
		if (Chd (p) == 0) {
			color[fthr[p]] = BLACK;
			color[fthr[fthr[p]]] = RED;
			Rotate (fthr[fthr[p]], 1);
		} else {
			Rotate (fthr[p], 0);
			DoubleRed2 (p);
		}
	} else {
		if (Chd (p) == 1) {
			color[fthr[p]] = BLACK;
			color[fthr[fthr[p]]] = RED;
			Rotate (fthr[fthr[p]], 0);
		} else {
			Rotate (fthr[p], 1);
			DoubleRed2 (p);
		}
	}
}

void Insert (int &p, int x) {
	if (! root) {
		root = NewNode (x, 0);
		color[root] = BLACK;
		PushUp (root);
		return ;
	} else {
		int id = Find (root, x, 0);
		if (id == INF) {
			id = Find (root, x, 1);
			ch[id][x > val[id]] = NewNode (x, id);
			if (color[id] != BLACK) {
				if (Bro (id) != 0 && color[Bro (id)] == RED) {
					DoubleRed1 (ch[id][x > val[id]]);
				} else {
					DoubleRed2 (ch[id][x > val[id]]);
				}
			}
			PushUp (ch[id][x > val[id]]);
		} else {
			++ cnt[id];
			PushUp (id);
		}
	}
}

void OutPut (int p) {
	if (p) {
		OutPut (ch[p][0]);
		printf ("%d ", val[p]);
		OutPut (ch[p][1]);
	}
}

int main () {
	
	Build ();
	Insert (root, 1);
	Insert (root, 2);
	Insert (root, 3);
	Insert (root, 4);
	Insert (root, 5);
	Insert (root, 6);
	Insert (root, 7);
	Insert (root, 8);
	OutPut (root);
	
	return 0;
}