平衡树

返回至上一层

发布时间：2026-09-26 | 分类：随笔/创意

前言

统一一下帖子的格式，以后像“前文”、“正文”什么的都统一用h4。分点的标题就用h5。再下一层就是strong，最后就是普通的文字。

这篇帖子讲述的平衡树是有旋的AVL树，以后学到了更进阶的在写其他的。

正篇

AVL树，是二叉搜索树和平衡树为一体的树。平衡树即所有节点的子树高度差不超过1。

左右旋操作

先看右旋。右旋操作可以看下面的动图：

gif

不难看出，有这三个步骤：

1. 当前节点的左孩子为左孩子的右孩子

2. 左孩子的右孩子为当前节点

3. 当前的根节点为左孩子

用代码实现就是：

BiTree RgtRt(BiTree T)
{
    BiTree L=T->lchild;
    T->lchild=L->rchild;
    L->rchild=T;
    T=L;
    return T;
}

接下来是左旋：

gif

同样能看出，有这三个步骤：

1. 当前节点的右孩子为右孩子的左孩子

2. 右孩子的左孩子为当前节点

3. 当前的根节点为右孩子

用代码实现就是：

BiTree LftRt(BiTree T)
{
    BiTree R=T->rchild;
    T->rchild=R->lchild;
    R->lchild=T;
    T=R;
    return T;
}

平衡调整

接下来我们可以根据下图来判断什么时候左旋，什么时候右旋。以此来保持平衡。

（图源 : bilibili @蓝不过海呀）

我们先来处理LX的情况。

先储存一下左子树，因为后面会用到，这样可以提高可读性。

BiTree L=T->lchild;

LL树中，若当前节点的左子节点的平衡因子为1，则当前节点一定失衡，这是在一个平衡树上加一个节点后的情况。

那么我们就按照图，将当前节点进行右旋。

不过要记得修改平衡因子，当这种情况的LL树右旋后，当前节点和左子节点的平衡因子变为0。这点可以看一下右旋操作。

T->bf=L->bf=0;
T=RgtRt(T);

LR树中，若当前节点的左子节点的平衡因为为-1，则按照图先左旋左孩子，再右旋当前节点。

这里的平衡因子有三种情况，都可以通过代码自行画图来理解（可以借助变量名画图）:

BiTree R=L->rchild;
BiTree R=L->rchild;
switch(R->bf)
{
    case -1:
    {
        T->bf=1;
        L->bf=0;
        break;
    }
    case 0:
    {
        T->bf=0;
        L->bf=0;
        break;
    }
    case 1:
    {
        T->bf=0;
        L->bf=-1;
        break;
    }
}
R->bf=0;
L=LftRt(L);
T=RgtRt(T);

接下来是RX树的情况:

先储存一下右子树，因为后面会用到，这样可以提高可读性。

BiTree R=T->rchild;

RR树中，若当前节点的右子节点的平衡因子为-1，则当前节点一定失衡。

按照图左旋，这里也要改平衡因子:

T->bf=R->bf=0;
T=LftRt(T);

RL树中，若当前节点的左子节点的平衡因子为1，则当前节点一定失衡，这里也是看情况。

BiTree L=R->lchild;
switch(L->bf)
{
    case 1:
    {
        T->bf=-1;
        R->bf=0;
        break;
    }
    case 0:
    {
        T->bf=0;
        R->bf=0;
        break;
    }
    case -1:
    {
        T->bf=0;
        R->bf=1;
        break;
    }
    
}
L->bf=0;
R=RgtRt(R);
T=LftRt(T);

插入节点

毕竟前面只判断了子节点为多少，当前节点并不知道，不过我们可以根据节点插入的位置来判断当前节点的平衡因子。

明显地，当当前节点的平衡因子为1，且插入节点在左边的话，那么就能判断出是LX树（因为插入的节点会在左子节点的左或右边）

RX树也是一样，那么以此类推，不难写出代码:

bool InsertAVL(BiTree &T, int val, bool &is_taller)
{
    if(!T) //已经到了最底层
    {
        T=new BiTNode; //创建节点
        T->data=val;
        T->lchild=T->rchild=NULL;
        T->bf=0;
        is_taller=true;
        return true;
    }
    if(val==T->data) //如果值重复了
    {
        is_taller=false; //加入失败
        return false;
    }
    if(val<T->data) //插入在左边
    {
        if(!InsertAVL(T->lchild,val,is_taller)) //插入失败则直接返回false
            return false;
        if(is_taller) //如果子树的高度有变
        {
            switch(T->bf)
            {
                case 0:
                {
                    T->bf=1;
                    is_taller=true;
                    break;
                }
                case 1:
                {
                    T=LftBl(T); //LX树
                    is_taller=false;
                    break;
                }
                case -1:
                {
                    T->bf=0;
                    is_taller=false;
                    break;
                }
            }
        }
    }
    else //插入在右边
    {
        if(!InsertAVL(T->rchild,val,is_taller)) //插入失败则直接返回false
            return false;
        if(is_taller) //如果子树的高度有变
        {
            switch(T->bf)
            {
                case 0:
                {
                    T->bf=-1;
                    is_taller=true;
                    break;
                }
                case -1:
                {
                    T=RgtBl(T); //RX树
                    is_taller=false;
                    break;
                }
                case 1:
                {
                    T->bf=0;
                    is_taller=false;
                    break;
                }
            }
        }
    }
    return true;
}

后面是完整代码:

#include <iostream> 
using namespace std;
typedef struct BiTNode {
    int data;
    int bf;
    int size;
    BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

int getSize(BiTree T){
    return T ? T->size : 0;
}

void updateSize(BiTree T){
    if(T) T->size = 1 + getSize(T->lchild) + getSize(T->rchild);
}

//左旋 RR
BiTree LftRt(BiTree T) {
    BiTree R=T->rchild;
    T->rchild=R->lchild;
    R->lchild=T;
    updateSize(T); // T变成R的孩子，先更新T
    updateSize(R);
    T=R;
    return T;
}

//右旋 LL
BiTree RgtRt(BiTree T) {
    BiTree L=T->lchild;
    T->lchild=L->rchild;
    L->rchild=T;
    updateSize(T);
    updateSize(L);
    T=L;
    return T;
}

//左子树失衡 LL / LR
BiTree LftBl(BiTree T) {
    BiTree L=T->lchild;
    switch(L->bf)
    {
        case 1: // LL
        {
            T->bf=L->bf=0;
            T=RgtRt(T);
            break;
        }
        case -1: // LR
        {
            BiTree R=L->rchild;
            switch(R->bf)
            {
                case -1:
                {
                    T->bf=1;
                    L->bf=0;
                    break;
                }
                case 0:
                {
                    T->bf=0;
                    L->bf=0;
                    break;
                }
                case 1:
                {
                    T->bf=0;
                    L->bf=-1;
                    break;
                }
            }
            R->bf=0;
            L=LftRt(L);
            T=RgtRt(T);
            break;
        }
    }
    return T;
}

//右子树失衡 RR / RL
BiTree RgtBl(BiTree T) {
    BiTree R=T->rchild;
    switch(R->bf)
    {
        case -1: // RR
        {
            T->bf=R->bf=0;
            T=LftRt(T);
            break;
        }
        case 1: // RL
        {
            BiTree L=R->lchild;
            switch(L->bf)
            {
                case 1:
                {
                    T->bf=-1;
                    R->bf=0;
                    break;
                }
                case 0:
                {
                    T->bf=0;
                    R->bf=0;
                    break;
                }
                case -1:
                {
                    T->bf=0;
                    R->bf=1;
                    break;
                }
            }
            L->bf=0;
            R=RgtRt(R);
            T=LftRt(T);
            break;
        }
    }
    return T;
}

bool InsertAVL(BiTree &T, int val, bool &is_taller) {
    if(!T)
    {
        T=new BiTNode;
        T->data=val;
        T->lchild=T->rchild=NULL;
        T->bf=0;
        T->size=1;
        is_taller=true;
        return true;
    }
    //允许重复节点，重复插左边
    if(val <= T->data)
    {
        if(!InsertAVL(T->lchild,val,is_taller)) return false;
        updateSize(T);
        if(is_taller)
        {
            switch(T->bf)
            {
                case 0:
                {
                    T->bf=1;
                    is_taller=true;
                    break;
                }
                case 1:
                {
                    T=LftBl(T);
                    is_taller=false;
                    break;
                }
                case -1:
                {
                    T->bf=0;
                    is_taller=false;
                    break;
                }
            }
        }
    }
    else
    {
        if(!InsertAVL(T->rchild,val,is_taller)) return false;
        updateSize(T);
        if(is_taller)
        {
            switch(T->bf)
            {
                case 0:
                {
                    T->bf=-1;
                    is_taller=true;
                    break;
                }
                case -1:
                {
                    T=RgtBl(T);
                    is_taller=false;
                    break;
                }
                case 1:
                {
                    T->bf=0;
                    is_taller=false;
                    break;
                }
            }
        }
    }
    return true;
}

bool DeleteAVL(BiTree &T, int val, bool &is_shorter) {
    if(!T)
    {
        is_shorter=false;
        return false;
    }
    if(val < T->data)
    {
        if(!DeleteAVL(T->lchild, val, is_shorter)) return false;
        updateSize(T);
        if(is_shorter)
        {
            switch(T->bf)
            {
                case 1:
                    T->bf=0;
                    is_shorter=true;
                    break;
                case 0:
                    T->bf=-1;
                    is_shorter=false;
                    break;
                case -1:
                    T = RgtBl(T);
                    is_shorter=true;
                    break;
            }
        }
    }
    else if(val > T->data)
    {
        if(!DeleteAVL(T->rchild, val, is_shorter)) return false;
        updateSize(T);
        if(is_shorter)
        {
            switch(T->bf)
            {
                case -1:
                    T->bf=0;
                    is_shorter=true;
                    break;
                case 0:
                    T->bf=1;
                    is_shorter=false;
                    break;
                case 1:
                    T = LftBl(T);
                    is_shorter=true;
                    break;
            }
        }
    }
    else
    {
        BiTree p = T;
        if(!T->rchild)
        {
            T = T->lchild;
            delete p;
            is_shorter=true;
        }
        else if(!T->lchild)
        {
            T = T->rchild;
            delete p;
            is_shorter=true;
        }
        else
        {
            BiTree q = T->lchild;
            while(q->rchild) q = q->rchild;
            T->data = q->data;
            DeleteAVL(T->lchild, q->data, is_shorter);
            updateSize(T);
            if(is_shorter)
            {
                switch(T->bf)
                {
                    case 1:
                        T->bf=0;
                        is_shorter=true;
                        break;
                    case 0:
                        T->bf=-1;
                        is_shorter=false;
                        break;
                    case -1:
                        T = RgtBl(T);
                        is_shorter=true;
                        break;
                }
            }
        }
    }
    return true;
}

//查询x的排名：小于x的个数+1
int getRank(BiTree T, int x){
    if(!T) return 0;
    if(T->data >= x) return getRank(T->lchild, x);
    else return getSize(T->lchild)+1 + getRank(T->rchild, x);
}

//查询第r小
int getKth(BiTree T, int r){
    int sz = getSize(T->lchild);
    if(sz+1 == r) return T->data;
    if(sz >= r) return getKth(T->lchild, r);
    else return getKth(T->rchild, r-sz-1);
}

//前驱：小于x的最大值
int getPre(BiTree T, int x){
    int res = -0x7fffffff;
    BiTree p=T;
    while(p){
        if(p->data < x){
            res = p->data;
            p = p->rchild;
        }else{
            p = p->lchild;
        }
    }
    return res;
}

//后继：大于x的最小值
int getSuc(BiTree T, int x){
    int res = 0x7fffffff;
    BiTree p=T;
    while(p){
        if(p->data > x){
            res = p->data;
            p = p->lchild;
        }else{
            p = p->rchild;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    BiTree root=NULL;
    int n;
    cin>>n;
    while(n--){
        int op,x;
        cin>>op>>x;
        bool tmp;
        if(op==1){
            InsertAVL(root,x,tmp);
        }else if(op==2){
            DeleteAVL(root,x,tmp);
        }else if(op==3){
            cout<<getRank(root,x)+1<<'\n';
        }else if(op==4){
            cout<<getKth(root,x)<<'\n';
        }else if(op==5){
            cout<<getPre(root,x)<<'\n';
        }else if(op==6){
            cout<<getSuc(root,x)<<'\n';
        }
    }
    return 0;
}