# 前置知识

  • 二叉搜索树

# 红黑树简介

# 红黑树是什么

红黑树是一种弱平衡二叉树。相比 AVL(一种严格平衡二叉树),它牺牲了一部分的查询效率,从而实现它飞快的插入与删除操作。

# 红黑树的性质

红黑树主要有以下性质:

  1. 是一颗二叉查找树
  1. 结点有红、黑两种颜色
  1. 根结点、叶子结点(NIL,不维护任何数值)是黑色
  1. 红色结点的子结点是黑色
  1. 根结点到所有叶子结点的路径上的黑色结点数量相等(这个数值被称为 黑高度

特别的,除了根结点可能是红色,这些性质对一颗红黑树的所有子树均适用。

这些性质严格限制了红黑树的高度在 O(logn)\operatorname O(\log n) 级别,也让它成为了最难写、最难调的平衡树之一。

# 基本框架

根据上面的定义和性质,我们可以写出基本的程序框架:

namespace RBTree{
    struct node{int val,color,siz,cnt;node *son[2],*f;node(int,node*);node();//son[0]左儿子,son[1]右儿子,f父亲,color颜色
    }*nil=new node(),*root=nil;int size;
    node::node():val(0),f(nil),color(1),siz(0),cnt(0){son[0]=son[1]=nil;}
    node::node(int val,node* f):val(val),f(f),color(0),siz(1),cnt(1){son[0]=son[1]=nil;}
    #define s(u,k) (u->son[k])
    #define val(u) (u->val)
    #define f(u) (u->f)
    #define siz(u) (u->siz)
    #define cnt(u) (u->cnt)
    #define color(u) (u->color)
    int checkred(node* u){return !color(s(u,1));}//查询红儿子的方向,右侧优先
    int check(node* u){return s(f(u),1)==u;}void swap(int& x,int& y){x^=y,y^=x,x^=y;}//查询结点相对父亲的方向、交换两数值
    void pushup(node* u){if(u!=nil)siz(u)=siz(s(u,0))+siz(s(u,1))+cnt(u);}//向上维护权值
    void swap(node* x,node* y){swap(val(x),val(y)),swap(siz(x),siz(y)),swap(cnt(x),cnt(y)),pushup(x),pushup(y);}//交换权值
    void connect(node* u,node* v,int k){if(v!=nil)s(v,k)=u;if(u!=nil)f(u)=v;}//连边
    void cut(node* u){node* f=f(u);int k=check(u);if(f!=nil)s(f,k)=nil;}//断边
    void rotate(node* u,int k){if(u==nil)return;node *v=s(u,k^1),*t=s(v,k),*f=f(u);int ku=check(u);
        if(v==nil)return;connect(t,u,k^1),connect(u,v,k),connect(v,f,ku);pushup(u),pushup(v);if(u==root)root=v;
    }void init(){nil->son[0]=nil->son[1]=nil;}//旋转、初始化
}

# 红黑树的操作

# 查询操作

同二叉查找树。

# 插入操作

# 插入结点

从根开始向下寻找,同二叉查找树。遇到空的结点就插入。新插入的结点染成红色,这是为了避免破坏性质 5。

namespace RBTree{
    void insert(node* &u,int x,node* f){if(u==nil)return u=new node(x,f),insertfix(u),void();
        if(val(u)==x)return cnt(u)++,pushup(u),void();insert(s(u,val(u)<x),x,u),pushup(u),insertfix(u);
    }void insert(int x){insert(root,x,nil);}
}

看起来很简单?

让人智息的操作在下面。

# 双红修正

我们发现直接插入一个结点可能会破坏性质 3、4。

于是我们考虑修正。

为了方便,我们给结点命名、着色如下(下同):

  • U 是当前修正的节点
  • F 是 U 修正之前的父亲
  • G 是 F 在 U 修正之前的父亲
  • A 是 G 在 U 修正之前的另外一个儿子
  • B 是 F 在 U 修正之前的另外一个儿子
  • R 是一个特定的红色结点
  • 空心结点是将要修正的结点
  • X0\mathrm X_0 是编号为 X 的结点的左子树,在合法情况下可以为空
  • X1\mathrm X_1 是编号为 X 的结点的右子树,在合法情况下可以为空
  • 结点的颜色就是图中所着的颜色
  • 对于 X0/1\mathrm X_{0/1},图中所着的颜色是是它的根结点的颜色
  • 图中着除红黑外的颜色的结点可以是任何颜色(对于 X0/1\mathrm X_{0/1} 同样适用); 除蓝色外,所有图中着相同颜色的结点的颜色相同。

分五种情况讨论。

  1. U 或 F是黑色

不需要进行任何操作。

  1. U 是根结点

染黑即可。此时全树黑高度增加 11

  1. U、F、A 是红色,G 是黑色

显然,U0,U1,A0,A1\mathrm U_0, \mathrm U_1, \mathrm A_0, \mathrm A_1 和 F 的另一个子树的黑高度相等,所以直接染红 G,染黑 F、A,然后对 G 进行双红修正即可(这个可以在插入回溯的过程中进行)。

e.g.

  • 修正前

  • 修正后

  1. U、F 是红色,G 是黑色,A 是黑色,且 U 相对 F 的方向和 F 相对 G 的方向相同

显然,U0,U1\mathrm U_0, \mathrm U_1 和 F 的另一个子树的黑高度比 A0,A1\mathrm A_0, \mathrm A_1 的黑高度大 11。我们直接旋转 G,使 F 上调到 G 的位置,然后染黑 F,染红 G 即可。

e.g.

  • 修正前

  • 修正后

  1. U、F 是红色,G 是黑色,A 是黑色,且 U 相对 F 的方向和 F 相对 G 的方向不同

显然,U0,U1\mathrm U_0, \mathrm U_1 和 F 的另一个子树的黑高度比 A0,A1\mathrm A_0, \mathrm A_1 的黑高度大 11。我们先旋转 F,使 U 上调到 F 的位置,再旋转 G,使 U 上调到 G 的位置,最后染红 G,染黑 U 即可。

e.g.

  • 修正前

  • 修正后

namespace RBTree{
    void insertfix(node* u){if(u==root)return color(u)=1,void();if(color(u)==1||color(f(u))==1)return;
        node *f=f(u),*g=f(f),*h=s(g,check(f)^1);int ku=check(u),kf=check(f);pushup(f),pushup(g);node* get(node* u,int x){if(val(u)==x||u==nil)return u;return get(s(u,val(u)<x),x);}
        if(color(h)){if(ku==kf)color(g)=0,color(f)=1,rotate(g,kf^1);
            else color(u)=1,color(g)=0,rotate(f,ku^1),rotate(g,kf^1);
        }else color(g)=0,color(f)=color(h)=1;
    }
}

# 删除操作

# 删除结点

和普通的二叉查找树一样。若被删除结点有右子树,那么就用它在以它为根的子树范围内的后继结点替换它,否则用它的左子结点替换它。然后把替换结点当作被删除结点继续执行删除操作,直到叶子结点(忽略 NIL,下同)

我们发现,最后真正删除的只有一个叶子结点。我们只要找出这个叶子结点,找的过程中替换一下,最后删除这个叶子结点即可。删除之前别忘了向上更新信息。

namespace RBTree{
    node* get(node* u,int x){if(val(u)==x||u==nil)return u;return get(s(u,val(u)<x),x);}  //寻找结点
    node* next(node* u){if(s(u,1)!=nil)return suc(u,val(u));return s(u,0);}  //寻找替换结点
    void up(node* u){while(u!=nil){pushup(u),u=f(u);}}//向上更新信息
    void del(int x){node* u=get(root,x);if(u==nil)return;if(cnt(u)>1)return cnt(u)--,up(u),void();  //如果不止一个就只更新个数
        while(siz(u)!=cnt(u)){node* v=next(u);cnt(u)=cnt(v),val(u)=val(v),u=v;}siz(u)=cnt(u)=0;  //寻找最终删除的结点
        up(u),delfix(u),cut(u);if(u==root)root=nil;delete u;  //更新信息,删除
    }
}

简单吗?不。

# 双黑修正

这也是红黑树最令人智息的操作之一。

我们发现,删除一个叶子结点(忽略 NIL),若它是红色,则不会破坏红黑树的性质; 若它是黑色,那么会破坏红黑树的性质 5。那么就要对它进行双黑修正。理解的时候考虑下删除它对黑高度的影响。

还是双红修正时的命名、着色方式。

分情况讨论:

  1. U 是红结点

不用执行任何操作。

  1. U 是黑结点,B 是红结点

显然, U0,U1\mathrm U_0, \mathrm U_1 的黑高度比 B0,B1\mathrm B_0, \mathrm B_122。只需要旋转 F,使 B 上调,然后给 B 染黑色,F 染红色,继续双黑修正。

e.g.

  • 修正前

  • 修正后

  1. U, F, B 都是黑色,B 没有红儿子

显然,U0,U1\mathrm U_0, \mathrm U_1 的黑高度比 B0,B1\mathrm B_0, \mathrm B_111,所以只需染红 B。由于整颗子树的黑高度都少了 11,所以还需要对 F 进行双黑修正。

e.g.

  • 修正前

  • 修正后

  1. U, B 是黑色,F 是红色,B 没有红儿子

显然,U0,U1\mathrm U_0, \mathrm U_1 的黑高度比 B0,B1\mathrm B_0, \mathrm B_111,又因 B 是黑色,F 是红色,所以只需把 F 染黑,B 染红即可。

e.g.

  • 修正前

  • 修正后

  1. U,B 是黑色,B 有红儿子

令 R 是 B 的红儿子。显然,U0,U1\mathrm U_0, \mathrm U_1 的黑高度比 R0,R1\mathrm R_0, \mathrm R_1 和 B 的另一个子树小 11

分情况讨论

  1. R 相对 B 的方向和 B 相对 F 的方向相同

直接旋转 F,将 B 上调,然后给 B 染 F 的颜色,F、R 染黑。

e.g.
- 修正前
- 修正后

  1. R 相对 B 的方向和 B 相对 F 的方向不同

旋转 B,上调 R,旋转 F,上调 R,给 R 然 F 的颜色,F、B 染黑即可。

e.g.
- 修正前
- 修正后

然后 delfix 函数也就很容易写出来了。

namespace RBTree{
    void delfix(node* u){if(!color(u))return;
        while(u!=root){node *f=f(u),*b=s(f,check(u)^1);int k=check(u);
            if(!color(b)){rotate(f,k),color(b)=1,color(f)=0;continue;}
            if(color(b)&&color(f)&&color(s(b,0))+color(s(b,1))==2){color(b)=0,u=f;continue;}
            if(color(b)&&color(f)==0&&color(s(b,0))+color(s(b,1))==2){color(f)=1,color(b)=0;break;}
            if(color(b)&&color(s(b,0))+color(s(b,1))<2){int kr=checkred(b);node* r=s(b,kr);
                if(kr==check(b))rotate(f,k),color(b)=color(f),color(f)=color(r)=1;
                else rotate(b,kr^1),rotate(f,k),color(r)=color(f),color(f)=1;break;
            }
        }
    }
}

# 例题

# Luogu-P6136 (opens new window)/LOJ-104 (opens new window) 【模板】普通平衡树(数据加强版)

所有操作整合一下就好了。

#include<cstdio>
namespace Global{int n,m,last,ans;}
int read(){int ret=0,c=getchar(),f=1;
    while(c<'0'||c>'9')f*=(c=='-'?-1:1),c=getchar();
    while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();return ret*f;
}namespace RBTree{using namespace Global;
    struct node{int val,color,siz,cnt;node *son[2],*f;node(int,node*);node();
    }*nil=new node(),*root=nil;int size;
    node::node():val(0),f(nil),color(1),siz(0),cnt(0){son[0]=son[1]=nil;}
    node::node(int val,node* f):val(val),f(f),color(0),siz(1),cnt(1){son[0]=son[1]=nil;}
    #define s(u,k) (u->son[k])
    #define val(u) (u->val)
    #define f(u) (u->f)
    #define siz(u) (u->siz)
    #define cnt(u) (u->cnt)
    #define color(u) (u->color)
    int checkred(node* u){return !color(s(u,1));}
    int check(node* u){return s(f(u),1)==u;}void swap(int& x,int& y){x^=y,y^=x,x^=y;}
    void pushup(node* u){if(u!=nil)siz(u)=siz(s(u,0))+siz(s(u,1))+cnt(u);}
    void swap(node* x,node* y){swap(val(x),val(y)),swap(siz(x),siz(y)),swap(cnt(x),cnt(y)),pushup(x),pushup(y);}
    void connect(node* u,node* v,int k){if(v!=nil)s(v,k)=u;if(u!=nil)f(u)=v;}
    void cut(node* u){node* f=f(u);int k=check(u);if(f!=nil)s(f,k)=nil;}
    void rotate(node* u,int k){if(u==nil)return;node *v=s(u,k^1),*t=s(v,k),*f=f(u);int ku=check(u);
        if(v==nil)return;connect(t,u,k^1),connect(u,v,k),connect(v,f,ku);pushup(u),pushup(v);if(u==root)root=v;
    }node* kth(node* u,int k){if(u==nil||siz(s(u,0))<k&&siz(s(u,0))+cnt(u)>=k)return u;
        if(siz(s(u,0))+cnt(u)<k)return kth(s(u,1),k-siz(s(u,0))-cnt(u));return kth(s(u,0),k);
    }int find(int k){return val(kth(root,k));}
    node* pre(node* u,int x){if(u==nil)return nil;
        if(val(u)<x){node* v=pre(s(u,1),x);return (v==nil||val(u)>val(v))?u:v;}else return pre(s(u,0),x);
    }node* suc(node* u,int x){if(u==nil)return nil;
        if(val(u)>x){node* v=suc(s(u,0),x);return (v==nil||val(u)<val(v))?u:v;}else return suc(s(u,1),x);
    }int pre(int x){return val(pre(root,x));}int suc(int x){return val(suc(root,x));}
    int rank(node* u,int x){if(u==nil)return 1;if(val(u)==x)return siz(s(u,0))+1;
        if(val(u)<x)return siz(s(u,0))+cnt(u)+rank(s(u,1),x);else return rank(s(u,0),x);
    }int rank(int x){return rank(root,x);}
    void insertfix(node* u){if(u==root)return color(u)=1,void();if(color(u)==1||color(f(u))==1)return;
        node *f=f(u),*g=f(f),*h=s(g,check(f)^1);int ku=check(u),kf=check(f);pushup(f),pushup(g);
        if(color(h)){if(ku==kf)color(g)=0,color(f)=1,rotate(g,kf^1);
            else color(u)=1,color(g)=0,rotate(f,ku^1),rotate(g,kf^1);
        }else color(g)=0,color(f)=color(h)=1;
    }void insert(node* &u,int x,node* f){if(u==nil)return u=new node(x,f),insertfix(u),void();
        if(val(u)==x)return cnt(u)++,pushup(u),void();insert(s(u,val(u)<x),x,u),pushup(u),insertfix(u);
    }void insert(int x){insert(root,x,nil);}void init(){nil->son[0]=nil->son[1]=nil;}
    node* get(node* u,int x){if(val(u)==x||u==nil)return u;return get(s(u,val(u)<x),x);}
    void delfix(node* u){if(!color(u))return;
        while(u!=root){node *f=f(u),*b=s(f,check(u)^1);int k=check(u);
            if(!color(b)){rotate(f,k),color(b)=1,color(f)=0;continue;}
            if(color(b)&&color(f)&&color(s(b,0))+color(s(b,1))==2){color(b)=0,u=f;continue;}
            if(color(b)&&color(f)==0&&color(s(b,0))+color(s(b,1))==2){color(f)=1,color(b)=0;break;}
            if(color(b)&&color(s(b,0))+color(s(b,1))<2){int kr=checkred(b);node* r=s(b,kr);
                if(kr==check(b))rotate(f,k),color(b)=color(f),color(f)=color(r)=1;
                else rotate(b,kr^1),rotate(f,k),color(r)=color(f),color(f)=1;break;
            }
        }
    }node* next(node* u){if(s(u,1)!=nil)return suc(u,val(u));return s(u,0);}
    void up(node* u){while(u!=nil){pushup(u),u=f(u);}}
    void del(int x){node* u=get(root,x);if(u==nil)return;if(cnt(u)>1)return cnt(u)--,up(u),void();
        while(siz(u)!=cnt(u)){node* v=next(u);cnt(u)=cnt(v),val(u)=val(v),u=v;}siz(u)=cnt(u)=0;
        up(u),delfix(u),cut(u);if(u==root)root=nil;delete u;
    }
}using RBTree::find;using RBTree::pre;using RBTree::suc;using RBTree::rank;using RBTree::insert;
using namespace Global;using RBTree::init;using RBTree::del;
int main(){n=read(),m=read(),init();for(int i=1;i<=n;i++)insert(read());
    for(int i=1;i<=m;i++){int opt=read(),x=read();
        if(opt==1)insert(x^last);if(opt==2)del(x^last);if(opt==3)ans^=(last=rank(x^last));
        if(opt==4)ans^=(last=find(x^last));if(opt==5)ans^=(last=pre(x^last));if(opt==6)ans^=(last=suc(x^last));
    }printf("%d\n",ans);
}

# 作图工具

# References

2020 08 07 Fri 03:19:09
2020 10 17 Sat 07:00:25