红黑树

指针版

#include <iostream>

using namespace std;

struct Node {
  Node *s[2], *f;
  int v, c;
  Node(int v, Node *a, Node *b, Node *f): v(v), f(f), c(0) {
    s[0] = a;
    s[1] = b;
  }
};

Node *rt, *nil;

Node *newNode(int v, Node *f) {
  return new Node(v, nil, nil, f);
}

Node *rotate(Node *x) {
  Node *y = x->f, *z = y->f;
  int p = y->s[1] == x; Node *c = x->s[p ^ 1];
  if (z != nil) z->s[z->s[1] == y] = x;
  else rt = x;
  x->f = z, x->s[p ^ 1] = y;
  y->f = x, y->s[p] = c;
  c->f = y;
  return x;
}

bool hasRed(Node *u) {
  return u->s[0]->c == 0 || u->s[1]->c == 0;
}

Node *bro(Node *x) {
  Node *y = x->f; int p = y->s[1] == x;
  return y->s[p ^ 1];
}

Node *insFix(Node *z) {
  if (!hasRed(z)) return z;
  Node *y = z->s[0]->c == 0 ? z->s[0] : z->s[1];
  Node *u = bro(y);
  int to = z->s[1] == y;
  if (u->c == 0) {
    if (hasRed(u) || hasRed(y)) {
      z->c = 0;
      u->c = y->c = 1;
    }
    return z;
  }
  if (hasRed(y)) {
    Node *x = y->s[to]->c == 0 ? y->s[to] : y->s[to ^ 1];
    if ((y->s[1] == x) ^ (z->s[1] == y)) {
      y = rotate(x);
    }
    z = rotate(y);
    z->c = 1;
    z->s[0]->c = z->s[1]->c = 0;
  }
  return z;
}

Node *insert(int v, Node *p = nil, Node *u = rt) {
  if (u == nil) return newNode(v, p);
  if (u->v == v) return u;
  int to = u->v < v;
  u->s[to] = insert(v, u, u->s[to]);
  return insFix(u);
}

Node *remFix(Node *z) {
  if (z->s[0]->c != 2 && z->s[1]->c != 2) return z;
  Node *y = z->s[0]->c == 2 ? z->s[0] : z->s[1], *u = bro(y);
  int to = z->s[1] == y;
  if (u->c == 0) {
    z = rotate(u);
    y = z->s[to];
    z->c = 1;
    y->c = 0;
    z->s[to] = remFix(y);
    return z;
  }
  y->c = 1;
  if (!hasRed(u)) {
    z->c += 1;
    u->c -= 1;
    return z;
  }
  Node *x = u->s[to ^ 1]->c == 0 ? u->s[to ^ 1] : u->s[to];
  if ((u->s[1] == x) ^ (z->s[1] == u)) {
    u = rotate(x);
  }
  z = rotate(u);
  z->c = z->s[to]->c;
  z->s[0]->c = z->s[1]->c = 1;
  return z;
}

Node *remove(int v, Node *u = rt) {
  if (u == nil) return u;
  if (u->v != v) {
    int to = u->v < v;
    Node *nw = remove(v, u->s[to]);
    u->s[to] = nw;
    nw->f = u;
  } else if (u->s[0] != nil && u->s[1] != nil) {
    Node *t = u->s[1];
    while (t->s[0] != nil) t = t->s[0];
    u->v = t->v;
    Node *nw = remove(t->v, u->s[1]);
    u->s[1] = nw;
    nw->f = u;
  } else {
    Node *t = u->s[0] != nil ? u->s[0] : u->s[1];
    t->c += u->c;
    t->f = u;
    return t;
  }
  return remFix(u);
}

void dfs(int tp, Node *u) {
  if (u == nil) return ;
  if (tp) cout << u->v << ' ' << (u->c ? 'B' : 'R') << ' ';
  dfs(tp, u->s[0]); 
  if (!tp) cout << u->v << ' ' << (u->c ? 'B' : 'R') << ' ';
  dfs(tp, u->s[1]);
}

signed main() {
  nil = new Node(0, nullptr, nullptr, nullptr);
  nil->s[0] = nil;
  nil->s[1] = nil;
  nil->f = nil;
  nil->c = 1;
  rt = nil;
  int n; cin >> n;
  for (int i = 0; i < n; ++i) {
    string op; int x; cin >> op >> x;
    if (op[0] == 'I') rt = insert(x);
    else rt = remove(x);
    rt->c = 1;
    nil->c = 1;
  }
  dfs(0, rt);
  cout << "\n\n";
  dfs(1, rt);
  return 0;
}

数组版

#include <iostream>

using namespace std;

const int N = 200011;

struct Node {
  int s[2], f;
  int v, c;
}tr[N];

int idx;
int rt;

int rotate(int x) {
  int y = tr[x].f, z = tr[y].f;
  int p = tr[y].s[1] == x, c = tr[x].s[p ^ 1];
  if (z) tr[z].s[tr[z].s[1] == y] = x;
  else rt = x;
  tr[x].f = z, tr[x].s[p ^ 1] = y;
  tr[y].f = x, tr[y].s[p] = c;
  tr[c].f = y;
  return x;
}

bool hasRed(int u) {
  return tr[tr[u].s[0]].c == 0 || tr[tr[u].s[1]].c == 0;
}

int bro(int x) {
  int y = tr[x].f, p = tr[y].s[1] == x;
  return tr[y].s[p ^ 1];
}

int deal(int z) {
  if (!hasRed(z)) return z;
  int y = tr[tr[z].s[0]].c == 0 ? tr[z].s[0] : tr[z].s[1];
  int to = tr[z].s[1] == y;
  int u = bro(y);
  if (tr[u].c == 0) {
    if (hasRed(u) || hasRed(y)) {
      tr[z].c = 0;
      tr[u].c = tr[y].c = 1;
    }
    return z;
  }
  if (hasRed(y)) {
    int x = tr[tr[y].s[to]].c == 0 ? tr[y].s[to] : tr[y].s[to ^ 1];
    if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) {
      y = rotate(x);
    }
    z = rotate(y);
    tr[z].c = 1;
    tr[tr[z].s[0]].c = tr[tr[z].s[1]].c = 0;
  }
  return z;
}

int newNode(int v, int p) {
  int u = ++idx;
  tr[u].v = v;
  tr[u].f = p;
  tr[u].c = 0;
  return u;
}

int insert(int u, int v, int p) {
  if (!u) return newNode(v, p);
  if (tr[u].v == v) return u;
  int to = tr[u].v < v;
  tr[u].s[to] = insert(tr[u].s[to], v, u);
  return deal(u);
}

int beal(int z) {
  if (tr[tr[z].s[0]].c != 2 && tr[tr[z].s[1]].c != 2) return z;
  int y = tr[tr[z].s[0]].c == 2 ? tr[z].s[0] : tr[z].s[1], u = bro(y);
  int to = tr[z].s[1] == y;
  if (tr[u].c == 0) { // red unc
    z = rotate(u);
    y = tr[z].s[to];
    tr[z].c = 1;
    tr[y].c = 0;
    tr[z].s[to] = beal(y);
    return z;
  }
  tr[y].c = 1;
  if (!hasRed(u)) { // black unc
    tr[z].c += 1;
    tr[u].c -= 1;
    return z;
  }
  int x = tr[tr[u].s[to ^ 1]].c == 0 ? tr[u].s[to ^ 1] : tr[u].s[to];
  if ((tr[u].s[1] == x) ^ (tr[z].s[1] == u)) {
    u = rotate(x);
  }
  z = rotate(u);
  tr[z].c = tr[tr[z].s[to]].c;
  tr[tr[z].s[0]].c = tr[tr[z].s[1]].c = 1;
  return z;
}

int remove(int u, int v) {
  if (!u) return u;
  if (tr[u].v != v) {
    int to = tr[u].v < v;
    int nw = remove(tr[u].s[to], v);
    tr[u].s[to] = nw;
    tr[nw].f = u;
  } else if (tr[u].s[0] && tr[u].s[1]) {
    int t = tr[u].s[1];
    while (tr[t].s[0]) t = tr[t].s[0];
    tr[u].v = tr[t].v;
    int nw = remove(tr[u].s[1], tr[t].v);
    tr[u].s[1] = nw;
    tr[nw].f = u;
  } else {
    int t = tr[u].s[0] + tr[u].s[1];
    tr[t].c += tr[u].c;
    tr[t].f = u;
    return t;
  }
  return beal(u);
}

void dfs(int tp, int u) {
  if (!u) return ;
  if (tp == 1) cout << tr[u].v << ' ' << (tr[u].c ? "B" : "R") << ' ';
  dfs(tp, tr[u].s[0]);
  if (tp == 0) cout << tr[u].v << ' ' << (tr[u].c ? "B" : "R") << ' ';
  dfs(tp, tr[u].s[1]);
}

signed main() {
  cin.tie(0)->sync_with_stdio(false);
  tr[0].c = 1;
  int n; cin >> n;
  for (int i = 0; i < n; ++i) {
    string op; int x; cin >> op >> x;
    if (op[0] == 'I') rt = insert(rt, x, 0);
    else rt = remove(rt, x);
    tr[rt].c = 1;
  }
  dfs(0, rt);
  cout << "\n\n";
  dfs(1, rt);
  return 0;
}