平衡二叉树（AVL树）学习

学了平衡树有一段时间了，一直想来总结一下，就今天吧，用最简单的图和代码来说明白

平衡树的基本操作：

LL型平衡旋转：

void LL(node *&a){
    b = a->lch;
    a->lch = b->rch;
    b->rch = a;
    a->bf = b->bf = 0;
}

RR型平衡旋转：

void RR(node *&a){
    b = a->lch;
    a->rch = b->lch;
    b->lch = a;
    a->bf = b->bf = 0;
}

LR型平衡旋转：

void LR(node *&a){
    node *c = NULL;
    b = a->lch;
    c = b->rch;
    a->lch = c->rch;
    b->rch = c->lch;
    c->rch = a;
    c->lch = b;
    switch (c->bf)
    {
    case 1: {a->bf = -1; b->bf = 0; break;}
    case -1: {a->bf = 0; b->bf = 1; break;}
    case 0:{a->bf = b->bf = 0 ; break;}
    }
    c->bf = 0;
    b = c; //把b调整成已平衡的子根
}

RL型平衡旋转：

void RL(node *&a){
    node *c = NULL;
    b = a->rch;
    c = b->lch;
    a->rch = c->lch;
    b->lch = c->rch;
    c->lch = a;
    c->rch = b;
    switch (c->bf)
    {
    case 1:{a->bf = 0; b->bf = -1; break;}
    case -1:{a->bf = 1; b->bf = 0; break;}
    case 0:{a->bf = b->bf = 0; break;}
    }
    c->bf =0;
    b = c;
}

完整代码如下：

#include<cstdio>
using  namespace std;

struct node{
    int bf,key;
    node *lch,*rch;
};

node *bst = NULL,*b = NULL;
int n;

void LL(node *&a){
    b = a->lch;
    a->lch = b->rch;
    b->rch = a;
    a->bf = b->bf = 0;
}

void RR(node *&a){
    b = a->lch;
    a->rch = b->lch;
    b->lch = a;
    a->bf = b->bf = 0;
}

void LR(node *&a){
    node *c = NULL;
    b = a->lch;
    c = b->rch;
    a->lch = c->rch;
    b->rch = c->lch;
    c->rch = a;
    c->lch = b;
    switch (c->bf)
    {
    case 1: {a->bf = -1; b->bf = 0; break;}
    case -1: {a->bf = 0; b->bf = 1; break;}
    case 0:{a->bf = b->bf = 0 ; break;}
    }
    c->bf = 0;
    b = c; //把b调整成已平衡的子根
}

void RL(node *&a){
    node *c = NULL;
    b = a->rch;
    c = b->lch;
    a->rch = c->lch;
    b->lch = c->rch;
    c->lch = a;
    c->rch = b;
    switch (c->bf)
    {
    case 1:{a->bf = 0; b->bf = -1; break;}
    case -1:{a->bf = 1; b->bf = 0; break;}
    case 0:{a->bf = b->bf = 0; break;}
    }
    c->bf =0;
    b = c;
}

void Insert(node *&t, int k){
    node *s = NULL,*f = NULL, *p = NULL,*q = NULL, *a = NULL;
    int d = 0;;
    bool balanced = true;
    s = new node;
    s->lch = s->rch = NULL;
    s->bf =  0;
    s->key = k;
    if(t == NULL) t = s;
    else {   //在以节点t为根的平衡树上插入关键字等于k的新节点s
       
        a = p = t;
        while(p!= NULL){    //找到插入位置q
            if(p->bf!=0) {a = p; f = q;}
            q = p;
            if(s->key < p->key) p=p->lch;
            else p = p->rch;
        }
        if(s->key < q->key) q->lch = s;
        else q->rch = s;

        //修改a-s路径上的各节点的平衡因子值
        if(s->key < a->key)
        {p = a->lch; b = p; d = 1;}
        else 
        {p = a->rch; b = p; d = -1;}

        while(p!=s){
            if(s->key < p->key)
            {p->bf = 1; p= p->lch;}
            else
            {p->bf = -1; p=p->rch;}
        //判断a的子树是否失去平衡
        balanced = true;
        if(a->bf == 0) a->bf = d;
        else if(a->bf == -d) a->bf = 0;
             else {  //失去平衡，判别旋转类型
                balanced = false;
                if(d == 1){
                    switch (b->bf)
                    {
                    case 1:{LL(a); break;}
                    case -1:{LR(a); break;}
                    }
                }
                else {
                    switch (b->bf)
                    {
                    case -1:{RR(a); break;}
                    case 1:{RL(a); break;}
                    }
                }
             }
             if(!balanced)  //在RL和LR处理旋转结束时令b = c
                if(f == NULL) t = b;
                else if(f->lch == a) f->lch = b;
                else if(f->rch == a) f->rch = b;
     }
    }
}

void out(node *root){
    printf("(");
    if(root->lch != NULL) out(root->lch);
    printf("%d",root->key);
    if(root->rch != NULL) out(root->rch);
    printf(")");
}

int main(){
    printf("input data(if < 0 then over!):
");
    do{
        scanf("%d",&n);
        if(n >=0) Insert(bst,n);
    }while(n >=0);
    printf("output sorted data
");
    out(bst);
    return 0;
}