先写 3。

请不要发布无意义评论，“d”，“qp”等言论请不要大量发布，不欢迎宣传与刷罐。如有直接删评。

红黑树的定义

红黑树在 1972 年被发明，于 1978 年正式被发表。

为什么叫红黑树，因为你学着学着就红温了，然后两眼一黑。所以叫红黑树（

好了不开玩笑了。

一般地，红黑树满足以下几条性质：

1. 是一棵二叉搜索树
2. 所有节点均为红色或黑色
3. 根节点与叶子节点^[1]为黑色^[2]
4. 没有两个相邻的红色节点
5. 从根节点开始到叶子结点，所有的路径所经过的黑色节点数都是相同的。

由于第二条性质，我们说这种平衡树叫做红黑树。

根据第五条性质，红黑树的最低子树不会超过最高子树的两倍。证明就算了，所以红黑树是一种弱平衡的二叉搜索树，他的查询是 $\mathcal{O(\log n)}$ 的。因为红黑树对树高的要求不是很严格，所以他的查询效率略逊于 AVL 树。但若插入，删除等操作较多时，红黑树能吊打绝大部分平衡树。当然，红黑树码量自然比较大。

红黑树的前驱后缀等的查询与二叉搜索树基本类似，所以我们这里只讲删除和插入，以及相应的平衡的调整。

还是你们最爱看的指针（

红黑树结构体定义

先看代码

struct rbt{
    T key,cnt,siz;
    bool color;
    rbt*l,*r,*fa;
}*root,*nil;

这里的 T 你们就理解为 int 即可，这是模版的东西。

key cnt siz 分别指权值，出现次数，字数大小。布尔变量 color 是当前节点的颜色。三个指针分别指向左孩子右孩子和父亲节点。

下面的 root 和 nil 指针分别是根节点与叶节点，也就是我们所说的空节点。所有的空指针指向它。这是为了模拟红黑树的叶节点。它的颜色固定为黑色，这是上文提到的性质。对于一颗红黑树，我们仅需要维护一个 nil 指针即可。

插入

我们发现，在插入节点的过程中，若插入黑色节点，则有可能违反第五条性质，但如果插入红色节点则会违反第四条性质。我们发现维护第五条性质的难度明显大于维护第四条性质，所以我们选择插入红色节点，若为空树则直接插入黑色节点即可。

红黑树的插入过程分以下两步：

1. 插入
2. 调整

其中插入的方法与 BST 一样，不多赘述，重点是后面的调整。

我们分类讨论，若插入节点的父亲是黑色，则不需要做任何调整。若为红色，则需要进行调整。我们来到下一步。实际上这里会有两种不同的情况，即父节点是爷节点的‌左孩子，以及父节点是爷节点的‌右孩子。这里两种情况的处理方式类似，只不过是相反的。我们这里以第一种情况为例

情况一

现在我们插入节点 E，插入后的红黑树是这样的：

我们在插入过程中，主要是看叔叔的脸色^[3]。现在叔叔红温了，父亲也红温了，我们直接把叔叔和父亲都染成黑色即可。

情况二

这个时候叔叔又黑了，分为以下两种情况

子情况一

如下：

若为 LR 型，也就是当前节点是父亲的右孩子，我们直接左旋父节点即可。这时会变为下面的那种情况

子情况二

如下：

我们将父节点变成黑色，爷节点染成红色，然后对祖父节点进行右旋操作即可。由于过程较复杂我放一个旋转好的图：

这时的父节点变成了爷节点，叔叔节点变成了孙子节点，你说叔叔脸为啥黑🤔🤔🤔

注意，在这些操作结束后，要将爷节点当做新插入的节点，继续向上迭代，直到父亲为黑色节点为止。

上述第二种情况与这种情况操作为镜像，就不讲了。接下来贴红黑树的调整代码。

void insertfix(rbt*x){
    while(x->fa->color==red){//若父亲为红色
        if(x->fa==x->fa->fa->l){//上文提到的第一种情况
            rbt*unc=x->fa->fa->r;//叔叔节点
            if(unc->color==red){//情况一
                x->fa->color=black;
                unc->color=black;
                x->fa->fa->color=red;
                x=x->fa->fa;
            }else{
                if(x==x->fa->r){//情况二的子情况一，这里经过旋转后会直接变为子情况二，故为并列关系
                    x=x->fa,zag(x);
                }
                x->fa->color=black;//子情况二的调整
                x->fa->fa->color=red;
                zig(x->fa->fa);
            }
        }else{//上文提到的第二种情况，镜像，就不打注释了
            rbt*unc=x->fa->fa->l;
            if(unc->color==red){
                x->fa->color=black;
                unc->color=black;
                x->fa->fa->color=red;
                x=x->fa->fa;
            }else{
                if(x==x->fa->l){
                    x=x->fa,zig(x);
                }
                x->fa->color=black;
                x->fa->fa->color=red;
                zag(x->fa->fa);
            }
        }
    }root->color=black;//注意把根节点染红
}

下面是插入的代码，与普通 BST 插入无异，不细讲了。

void push(T key){
    rbt*now=root,*last=nil;
    while(now!=nil){
        last=now;
        if(key==now->key){
            now->cnt++;
            pushup(now);
            rbt*cur=now;
            while(cur->fa!=nil){
                cur=cur->fa;
                pushup(cur);
            }return;
        }else if(key<now->key)now=now->l;
        else now=now->r;
    }
    now=newnode(key);
    now->fa=last;
    if(last==nil)root=now;
    else if(key<last->key)last->l=now;
    else last->r=now;
    insertfix(now);//插入完成后调整
    rbt*cur=now;
    while(cur!=nil){//调整完记得向上传递更新节点
        pushup(cur);
        cur=cur->fa;
    }
}

那啥代码先放着，写完要很久了，凑活看看

#include <cstdio>
const int INF=1000000000;
const bool red=1;
const bool black=0;
inline void readll(long long&x){x=0;int f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}x*=f;}
inline void writell(long long x){if(x<0){putchar('-');x=-x;}if(x>9)writell(x/10);putchar(x%10+'0');}
inline void read(int&x){x=0;int f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}x*=f;}
inline void write(int x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
template<typename T>
class Redblacktree{
private:
    struct rbt{T key,cnt,siz;bool color;rbt*l,*r,*fa;}*root,*nil;
    rbt* newnode(T key){
        rbt*p=new rbt;
        p->key=key,p->cnt=1,p->siz=1,p->color=red;
        p->l=p->r=p->fa=nil;
        return p;
    }void pushup(rbt*u){
        u->siz=u->cnt;
        if(u->l!=nil)u->siz+=u->l->siz;
        if(u->r!=nil)u->siz+=u->r->siz;
    }void zig(rbt*u){
        rbt*lc=u->l;
        u->l=lc->r;
        if(lc->r!=nil)lc->r->fa=u;
        lc->fa=u->fa;
        if(u->fa==nil)root=lc;
        else if(u==u->fa->l)u->fa->l=lc;
        else u->fa->r=lc;
        lc->r=u,u->fa=lc;
        pushup(u),pushup(lc);
    }void zag(rbt*u){
        rbt*rc=u->r;
        u->r=rc->l;
        if(rc->l!=nil)rc->l->fa=u;
        rc->fa=u->fa;
        if(u->fa==nil)root=rc;
        else if(u==u->fa->l)u->fa->l=rc;
        else u->fa->r=rc;
        rc->l=u,u->fa=rc;
        pushup(u),pushup(rc);
    }void insertfix(rbt*x){
        while(x->fa->color==red){
            if(x->fa==x->fa->fa->l){
                rbt*unc=x->fa->fa->r;
                if(unc->color==red){
                    x->fa->color=black;
                    unc->color=black;
                    x->fa->fa->color=red;
                    x=x->fa->fa;
                }else{
                    if(x==x->fa->r){
                        x=x->fa,zag(x);
                    }
                    x->fa->color=black;
                    x->fa->fa->color=red;
                    zig(x->fa->fa);
                }
            }else{
                rbt*unc=x->fa->fa->l;
                if(unc->color==red){
                    x->fa->color=black;
                    unc->color=black;
                    x->fa->fa->color=red;
                    x=x->fa->fa;
                }else{
                    if(x==x->fa->l){
                        x=x->fa,zig(x);
                    }
                    x->fa->color=black;
                    x->fa->fa->color=red;
                    zag(x->fa->fa);
                }
            }
        }root->color=black;
    }void transplant(rbt*u,rbt*v){
        if(u->fa==nil)root=v;
        else if(u==u->fa->l)u->fa->l=v;
        else u->fa->r=v;
        v->fa=u->fa;
    }rbt* findmin(rbt*u){
        while(u->l!=nil)u=u->l;
        return u;
    }void delfix(rbt*x){
        while(x!=root&&x->color==black){
            if(x==x->fa->l){
                rbt*bro=x->fa->r;
                if(bro->color==red){
                    bro->color=black;
                    x->fa->color=red;
                    zag(x->fa);
                    bro=x->fa->r;
                }
                if(bro->l->color==black&&bro->r->color==black){
                    bro->color=red;
                    x=x->fa;
                }else{
                    if(bro->r->color==black){
                        bro->l->color=black;
                        bro->color=red;
                        zig(bro);
                        bro=x->fa->r;
                    }
                    bro->color=x->fa->color;
                    x->fa->color=black;
                    bro->r->color=black;
                    zag(x->fa);
                    x=root;
                }
            }else{
                rbt*bro=x->fa->l;
                if(bro->color==red){
                    bro->color=black;
                    x->fa->color=red;
                    zig(x->fa);
                    bro=x->fa->l;
                }
                if(bro->r->color==black&&bro->l->color==black){
                    bro->color=red;
                    x=x->fa;
                }else{
                    if(bro->l->color==black){
                        bro->r->color=black;
                        bro->color=red;
                        zag(bro);
                        bro=x->fa->l;
                    }
                    bro->color=x->fa->color;
                    x->fa->color=black;
                    bro->l->color=black;
                    zig(x->fa);
                    x=root;
                }
            }
        }x->color=black;
    }
public:
    void init(){
        nil=new rbt;
        nil->color=black;
        nil->l=nil->r=nil->fa=nil;
        nil->cnt=nil->siz=0;
        root=nil;
    }void push(T key){
        rbt*now=root,*last=nil;
        while(now!=nil){
            last=now;
            if(key==now->key){
                now->cnt++;
                pushup(now);
                rbt*cur=now;
                while(cur->fa!=nil){
                    cur=cur->fa;
                    pushup(cur);
                }return;
            }else if(key<now->key)now=now->l;
            else now=now->r;
        }
        now=newnode(key);
        now->fa=last;
        if(last==nil)root=now;
        else if(key<last->key)last->l=now;
        else last->r=now;
        insertfix(now);
        rbt*cur=now;
        while(cur!=nil){
            pushup(cur);
            cur=cur->fa;
        }
    }void del(T key){
        rbt*now=root;
        while(now!=nil){
            if(key==now->key)break;
            else if(key<now->key)now=now->l;
            else now=now->r;
        }if(now==nil)return;
        if(now->cnt>1){
            now->cnt--;
            pushup(now);
            rbt*cur=now;
            while(cur->fa!=nil){
                cur=cur->fa;
                pushup(cur);
            }return;
        }
        rbt*y=now,*x;
        bool ycol=y->color;
        if(now->l==nil){
            x=now->r;
            transplant(now,now->r);
        }else if(now->r==nil){
            x=now->l;
            transplant(now,now->l);
        }else{
            y=findmin(now->r),ycol=y->color,x=y->r;
            if(y->fa==now)x->fa=y;
            else{
                transplant(y,y->r);
                y->r=now->r,now->r->fa=y;
            }
            transplant(now,y);
            y->l=now->l,now->l->fa=y,y->color=now->color;
        }
        delete now;
        rbt*cur=x->fa;
        while(cur!=nil){
            pushup(cur);
            cur=cur->fa;
        }if(ycol==black)delfix(x);
    }int getrank(T x){
        rbt*u=root;
        int res=0;
        while(u!=nil){
            if(x<u->key)u=u->l;
            else if(x>u->key)res+=u->l->siz+u->cnt,u=u->r;
            else{res+=u->l->siz;break;}
        }
        return res;
    }T getkth(int k){
        rbt*u=root;
        while(u!=nil){
            int ls=u->l->siz;
            if(k<=ls)u=u->l;
            else if(k<=ls+u->cnt)return u->key;
            else k-=ls+u->cnt,u=u->r;
        }
        return 0;
    }T getpre(T x){
        rbt*u=root;
        T res=-INF;
        while(u!=nil){
            if(u->key<x)res=u->key,u=u->r;
            else u=u->l;
        }
        return res;
    }T getsuc(T x){
        rbt*u=root;
        T res=INF;
        while(u!=nil){
            if(u->key>x)res=u->key,u=u->l;
            else u=u->r;
        }
        return res;
    }
};
int main() {
    Redblacktree<int> tr;
    tr.init();
    int t;
    read(t);
    while(t--){
        int op,x;
        read(op),read(x);
        if(op==1)tr.push(x);
        if(op==2)tr.del(x);
        if(op==3)write(tr.getrank(x)+1),putchar('\n');
        if(op==4)write(tr.getkth(x)),putchar('\n');
        if(op==5)write(tr.getpre(x)),putchar('\n');
        if(op==6)write(tr.getsuc(x)),putchar('\n');
    }
    return 0;
}

---

1. 一般的，红黑树中我们说的叶子结点指的都是空节点。 ↩︎

2. 设叶子结点为黑色，是为了后序的插入与删除操作。 ↩︎

3. 这里指父亲的兄弟节点。 ↩︎