最近要准备阿里的面试
就学习下红黑树
红黑树：根必为黑，红节点不会连续，黑高相等
保证了查询复杂度小于logn
当然比较难理解的是插入，删除
怎么就旋转跳跃，就又变成平衡了呢
真是牛逼
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
struct RedBlack {
int color, key, left, right, parent; // 0 black 1 red
}E[N];
int tot;
int root;
void left_rotate(int x) {
int y = E[x].right;
E[x].right = E[y].left;
if(E[y].left) {
E[E[y].left].parent = x;
}
E[y].parent = E[x].parent;
if(E[x].parent == 0) root = y;
else if( x == E[E[x].parent].left ) E[E[x].parent].left = y;
else E[E[x].parent].right = y;
E[y].left = x;
E[x].parent = y;
}
void right_rotate(int x) {
int y = E[x].left;
E[x].left = E[y].right;
if(E[y].right) {
E[E[y].right].parent = x;
}
E[y].parent = E[x].parent;
if(E[x].parent == 0) root = y;
else if( x == E[E[x].parent].left ) E[E[x].parent].left = y;
else E[E[x].parent].right = y;
E[y].right = x;
E[x].parent = y;
}
void FixInsert(int z) {
int y;
while(E[E[z].parent].color == 1) {
if(E[z].parent == E[E[E[z].parent].parent].left) {
y = E[E[E[z].parent].parent].right;
if(E[y].color == 1) {
E[E[z].parent].color = 0;
E[y].color = 0;
E[E[E[z].parent].parent].color = 1;
z = E[E[z].parent].parent;
}else {
if(z == E[E[z].parent].right) {
z = E[z].parent;
left_rotate(z);
}
E[E[z].parent].color = 0;
E[E[E[z].parent].parent].color = 1;
right_rotate(E[E[z].parent].parent);
}
}else {
y = E[E[E[z].parent].parent].left;
if(E[y].color == 1) {
E[E[z].parent].color = 0;
E[y].color = 0;
E[E[E[z].parent].parent].color = 1;
z = E[E[z].parent].parent;
}else {
if(z == E[E[z].parent].left) {
z = E[z].parent;
right_rotate(z);
}
E[E[z].parent].color = 0;
E[E[E[z].parent].parent].color = 1;
left_rotate(E[E[z].parent].parent);
}
}
}
E[root].color = 0;
}
void Insert(int z) {
int x = root;
int y = 0;
while(x) {
y = x;
if(E[z].key < E[x].key) {
x = E[x].left;
}else x = E[x].right;
}
E[z].parent = y;
if(!y) root = z;
else if(E[z].key < E[y].key)
E[y].left = z;
else E[y].right = z;
E[z].left = 0;
E[z].right = 0;
E[z].color = 1;
FixInsert(z);
}
void Transplant(int u, int v) { // tanform v to u;
if(!E[u].parent) {
root = v;
}else if(u == E[E[u].parent].left) {
E[E[u].parent].left = v;
}else E[E[u].parent].right = v;
E[v].parent = E[u].parent;
}
int treeminimum(int x) {
while(!E[x].left) {
x = E[x].left;
}
return x;
}
int treemaxmum(int x) {
while(!E[x].right) {
x = E[x].right;
}
return x;
}
void Deletefix(int x) { // 被删掉的肯定是黑色
int w;
while(x != root && E[x].color == 0) {
if(x == E[E[x].parent].left) {
w = E[E[x].parent].right;
if(E[w].color == 1) { // w如果是红色节点 先转化成为黑色
E[w].color = 0;
E[E[x].parent].color = 1;
left_rotate(E[x].parent);
w = E[E[x].parent].right;
}
if(E[E[w].left].color == 0 && E[E[w].right].color == 0) {
E[w].color = 1;
x = E[x].parent;
}
else {
if(E[E[w].right].color == 0) {
E[E[w].left].color = 0;
E[w].color = 1;
right_rotate(w);
w = E[E[x].parent].right;
}
E[w].color = E[E[x].parent].color;
E[E[x].parent].color = 0;
E[E[w].right].color = 0;
left_rotate(E[x].parent);
x = root;
}
}else {
w = E[E[x].parent].left;
if(E[w].color == 1) {
E[w].color = 0;
E[E[x].parent].color = 1;
right_rotate(E[x].parent);
w = E[E[x].parent].left;
}
if(E[E[w].right].color == 0 && E[E[w].left].color == 0) {
E[w].color = 1;
x = E[x].parent;
}
else {
if(E[E[w].left].color == 0) {
E[E[w].right].color = 0;
E[w].color = 1;
left_rotate(w);
w = E[E[x].parent].left;
}
E[w].color = E[E[x].parent].color;
E[E[x].parent].color = 0;
E[E[w].left].color = 0;
right_rotate(E[x].parent);
x = root;
}
}
}
E[x].color = 0;
}
void Delete(int z) {
int y = z; int x;
int yorgcol = E[y].color;
if(!E[z].left) {
x = E[z].right;
Transplant(z, E[z].right);
}else if(!E[z].right) {
x = E[x].left;
Transplant(z, E[z].left);
}else {
y = treeminimum(E[z].right);
yorgcol = E[y].color;
x = E[y].right;
if(E[y].parent == z) {
E[x].parent = y;
}else {
Transplant(y, E[y].right);
E[y].right = E[z].right;
E[E[y].right].parent = y;
}
Transplant(z, y);
E[y].left = E[z].left;
E[E[y].left].parent = y;
E[y].color = E[z].color;
}
if(yorgcol == 0) {
Deletefix(x);
}
}
int main() {
int n;
while(~scanf("%d",&n)) {
root = 0; tot = 0;
for(int i = 1; i <= n; ++i) {
int ty; scanf("%d",&ty);
if(ty == 1) {
int a; scanf("%d",&a);
E[++tot].key = a;
Insert(tot);
}else {
Delete(tot);
}
}
}
return 0;
}