#创作计划#浅谈 AVL 树和红黑树-3

yxdl1

2026-07-05 17:33:44

发布于：浙江

105阅读

0回复

0点赞

先写 3。

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

红黑树的定义

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

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

好了不开玩笑了。

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

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

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

根据第五条性质，红黑树的最低子树不会超过最高子树的两倍。证明就算了，所以红黑树是一种弱平衡的二叉搜索树，他的查询是 $\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 指针即可。

插入

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

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

插入
调整

其中插入的方法与 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;
    }
}

删除

一样的，主要讲调整。其中若删除的节点是红色节点则不会破坏其他性质，删了就行。主要针对黑色节点的删除进行讨论。这里用了双黑节点，指这个节点带有额外的黑色权重。若当前节点到了根节点，则直接染黑；若变成了红色节点，则染黑即可，调整结束。否则分为以下两种大情况讨论。

情况一

大情况是当前节点是其父节点的左孩子，分以下四种子情况：

子情况一

此时的兄弟节点是红色，那么我们把兄弟节点变黑，然后父节点变红，然后以父节点为轴左旋。即可转化为下面的三种情况之一。注意更新兄弟节点。

子情况二

兄弟节点是黑色（若为红色则进入情况一，无序额外判断），同时他的俩孩子都是黑的。

因为没办法接到额外的黑色来补偿当前节点，所以把双黑节点传递到父节点。

子情况三：

兄弟节点是黑色，与子情况二不同，兄弟节点的孩子们至少有一个是黑的。在子情况三的情况下其左孩子是红的。

那么我们将其左孩子变黑，兄弟节点变红，以兄弟节点为轴右旋，最后更新兄弟节点即可。

情况四

和情况三类似，不过右孩子是红的。到了这种情况，就可以彻底清掉双黑结束调整了。

这时我们把兄弟节点颜色变为父节点颜色，兄弟的右孩子，父节点变黑，以父节点为轴左旋。那么此时当前节点路径上的黑高已经补全了。设置当前节点为根节点即可（注意上文讲到的循环退出条件）。

情况二

和情况一所有子情况严格对称，不多细讲了。

删除调整代码：

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;
    }

删除代码

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);
    }

整体代码

那么整个红黑树最重要的部分就讲完了，接下来贴整体代码

#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;
}

一般的，红黑树中我们说的叶子结点指的都是空节点。 ↩︎
设叶子结点为黑色，是为了后序的插入与删除操作。 ↩︎
这里指父亲的兄弟节点。 ↩︎

有帮助，赞一个

去预览

0/2000

全部评论 10

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

2026-07-12 来自上海
1
- yxdl1
  回复
  请‎输‎入‎文‎本‎. ‎🐛‎
  如有“直接删评”，没有直接删评
  
  2026-07-12 来自浙江
  0
几木几木上校·互关(半退)
前排自占

2026-04-26 来自广东
1
yxdl1
前排自占

2026-04-26 来自浙江
1
cjdst
无意义评论，“d”，“qp”等言论

2026-08-03 来自浙江
0
wcqk🦐✅️
orz pzh 之下初一最强之人出现了

2026-08-03 来自浙江
0
Xylophone
这就是 B 队%%%

2026-04-27 来自广东
0
- yxdl1
  回复
  Xylophone
  @prediction我猜对了
  
  2026-04-27 来自浙江
  0
- yxdl1
  回复
  Xylophone
  但是大佬别 P 了（）（）（）
  
  2026-04-27 来自浙江
  0
- Xylophone
  回复
  yxdl1
  orz pzh 之下初一最强之人出现了
  
  2026-04-27 来自广东
  0
KP-kouto
有几个疑点

2026-04-27 来自广东
0
- KP-kouto
  回复
  KP-kouto
  首先，为啥72年发现，78年公布，是因为要卡点么
  
  2026-04-27 来自广东
  0
- KP-kouto
  回复
  KP-kouto
  然后就是为啥叫红黑树不叫红蓝树蓝黑树红红树绿绿树黑黑树白白树黄黄树……(认真))
  
  2026-04-27 来自广东
  0
- yxdl1
  回复
  KP-kouto
  ？
  
  2026-04-27 来自浙江
  0
KP-kouto
细节不写2

2026-04-27 来自广东
0
- yxdl1
  回复
  KP-kouto
  2 代码没拉完
  
  2026-04-27 来自浙江
  0
- KP-kouto
  回复
  yxdl1
  我等着吃呢
  
  2026-04-27 来自广东
  0
- yxdl1
  回复
  KP-kouto
  急啥
  
  2026-04-27 来自浙江
  0
yhz
为啥不和 AVL 那篇放一起

2026-04-26 来自北京
0
- yxdl1
  回复
  yhz
  我是这么想的，AVL，红黑各一片，然后前传一篇，剩下一篇都是题
  
  2026-04-26 来自浙江
  0
- yhz
  回复
  yxdl1
  说句题外话
  
  俩都是高中生（
  
  2026-04-26 来自北京
  0
- yxdl1
  回复
  yhz
  这谁
  
  2026-04-26 来自浙江
  0
yxdl1
@AAA逃离森林湖的蔡锡龙批发准备开第三章

2026-04-26 来自浙江
0