平衡二叉树AVL|树

看过那么多次的调整平衡的策略,感觉都是假的,自己写(chao)一遍就懂了。
置简单说下思路:
数据结构:比二叉树多了一个平衡因子的参数。
程序利用递归自顶向下查找到要插入的点,以插入根节点的左节点为例,找到了就返回,返回的时候注意地检查平衡因子,若平衡因子显示右高,而我们插入的是左边,那么高度没有增加,从此结束;若平衡因子是左高,我们插入的是左边,那么这个时候就有可能是左左或者左右的情况了,要进行对应的调整,调整完就结束了;若平衡因子是平衡的,左边插入一个节点,高度增加1,但是还是保持平衡,高度增加1,继续向上检查。

参考文档:
1.平衡二叉树【注释无敌版】
2.Balancing a binary search tree

  • 节点的插入
///////////////////////////////////平衡二叉树
static bool BecomeTaller;
typedef enum
{
    LEFT_HIGH,
    RIGHT_HIGH,
    EQUALITY
}BF;
typedef struct AVLNode{
    ElemType data;
    struct AVLNode *lchild,*rchild;
    BF BalanceFactor;
}AVLNode,*AVLTree;

//向右旋转
void R_Rotate(AVLTree *Tree)
{
    AVLTree L=(*Tree)->lchild;

    (*Tree)->lchild = L->rchild;
    L->rchild = (*Tree);
    (*Tree) = L;
}

//向左旋转
void L_Rotate(AVLTree *Tree)
{
    AVLTree R = (*Tree)->rchild;

    (*Tree)->rchild = R->lchild;
    R->lchild = (*Tree);
    (*Tree) = R;
}

//左树的平衡因子为2
void BalanceLeft(AVLTree *Tree)
{
    AVLTree L = (*Tree)->lchild,Lr = L->rchild;

    switch(L->BalanceFactor)
    {
        //左左
        case LEFT_HIGH:
            (*Tree)->BalanceFactor = EQUALITY;
            (*Tree)->lchild->BalanceFactor = EQUALITY;
            R_Rotate(Tree);
            break;

        //左右
        case RIGHT_HIGH:
            
            //要理解下面这段,需要画出来慢慢分析对,似乎没有办法怎么理解
            switch(Lr->BalanceFactor)
            {
                case LEFT_HIGH:
                    (*Tree)->BalanceFactor = RIGHT_HIGH;
                    L->BalanceFactor = EQUALITY;
                    break;

                case EQUALITY:
                    (*Tree)->BalanceFactor = L->BalanceFactor =EQUALITY;
                    break;

                case RIGHT_HIGH:
                    (*Tree)->BalanceFactor = EQUALITY;
                    L->BalanceFactor = LEFT_HIGH;
                    break;
            }
            Lr->BalanceFactor = EQUALITY;

            L_Rotate(&L);
            R_Rotate(Tree);
            break;

        case EQUALITY:
            (*Tree)->BalanceFactor = LEFT_HIGH;
            BecomeTaller = true;
            break;
    }
}

void BalanceRight(AVLTree *Tree){

    AVLTree Lr= (*Tree)->rchild,L;

    switch(Lr->BalanceFactor)
    {

    case EQUALITY:
        BecomeTaller = true;
        (*Tree)->BalanceFactor = RIGHT_HIGH;
        break;

    case RIGHT_HIGH:
        (*Tree)->BalanceFactor=Lr->BalanceFactor=EQUALITY;
        L_Rotate(Tree);
        break;

    case LEFT_HIGH:
        L = Lr->lchild;
        switch(L->BalanceFactor)
        {
            case EQUALITY:
                (*Tree)->BalanceFactor = Lr->BalanceFactor = EQUALITY;
                break;

            case RIGHT_HIGH:
                Lr->BalanceFactor= EQUALITY;
                (*Tree)->BalanceFactor = LEFT_HIGH;
                break;

            case LEFT_HIGH:
                (*Tree)->BalanceFactor = LEFT_HIGH;
                Lr->BalanceFactor = EQUALITY;
                break;
        }
        L->BalanceFactor = EQUALITY;
        R_Rotate(&Lr);                
        L_Rotate(Tree);        

    }
}

//AVL树插入
//向下插入,向上调整,递归刚刚好
//如果插入的时候没有相同的数字,返回true,否则返回false
bool AVL_Insert(AVLTree *Tree,ElemType Num,bool *BecomeTaller)
{
    //插入新节点
    if((*Tree)==NULL)
    {
        (*Tree) = (AVLNode*)malloc(sizeof(AVLNode));
        (*Tree)->lchild = (*Tree)->rchild = NULL;
        (*Tree)->data = Num;
        (*Tree)->BalanceFactor = EQUALITY;
        (*BecomeTaller) = true;
        return true;
    }

    if (Num<((*Tree)->data))
    {
        if(!AVL_Insert(&((*Tree)->lchild),Num,BecomeTaller)) 
        {
            //还没有插入
            return false;
        }
        else
        {
            //插入成功,且子树长高了,要进行调整
            if (BecomeTaller)
            {
                switch ((*Tree)->BalanceFactor)
                {
                    //如果树是右高,左侧插入了节点,平衡因子变为EQUALITY
                    case RIGHT_HIGH:
                        (*Tree)->BalanceFactor = EQUALITY;
                        (*BecomeTaller) =  false;
                        break;

                    //左树高,还往左树插入新节点,属于左左类型,要调整
                    case LEFT_HIGH:
                        //这里的*Tree是新插入节点的爷爷!!!!!,不是爸爸,爸爸是不会到这里来的,
                        //所以问题简单多了,不用再找爷爷了;同时注意Tree就是左旋最上面的绳子。

                        //先调整树的平衡因子
                        BalanceLeft(Tree);
                        (*BecomeTaller) =  false;
                        break;

                    case EQUALITY:
                        (*Tree)->BalanceFactor = LEFT_HIGH;
                        (*BecomeTaller) =  true;
                        break;
                }//switch ((*Tree)->BalanceFactor)
                
            }//if (BecomeTaller)

            return true;
        }

    }
    else if(Num>((*Tree)->data))
    {
        if(!AVL_Insert(&((*Tree)->rchild),Num,BecomeTaller))
        {
            return false;
        }
        else
        {
            if ((*BecomeTaller)==true)
            {
                switch((*Tree)->BalanceFactor)
                {
                    case EQUALITY:
                        (*Tree)->BalanceFactor = RIGHT_HIGH;
                        *BecomeTaller = true;
                        break;

                    case LEFT_HIGH:
                        (*Tree)->BalanceFactor =EQUALITY;
                        (*BecomeTaller) = false;
                        break;

                    case RIGHT_HIGH:
                        BalanceRight(Tree);
                        (*BecomeTaller) = false;
                        break;
                }

            } 

            return true;
        }
    }
    else
    {
        return false;
    }
}

创建

void AVL_Create(AVLTree *Tree,ElemType Buff[],int len)
{
    for (int i=0;i<len;i++)
    {
        AVL_Insert(Tree,Buff[i],&BecomeTaller);
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,839评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,543评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,116评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,371评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,384评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,111评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,416评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,053评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,558评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,007评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,117评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,756评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,324评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,315评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,539评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,578评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,877评论 2 345

推荐阅读更多精彩内容