AVL树

定义 :高度平衡的二叉树.对每一个节点x,x的左子树与右子树的高度差至多为1

AVL树的数据结构

    struct AVLTreeNode
        bf ;          //平衡因子, 1(LH,左高出1); 0(EH,左右平衡); -1(RH,右高出1)
        key_t k ;     //关键字
        Data_t data ; //卫星数据  
        parent ;      //父节点
        left ;        //左孩子
        right ;       //右孩子

不平衡出项的情况

LL型

  • 即左子树高出2,且新插入节点再其父节点的左边
        PP                                P
       /        RightRotate 即可        /   \     #注意修改各节点的bf值
      P         ================>      x    PP    
     /
    x

LR型

  • 即左子树高出2,且新插入节点在其父节点的右边
        pp                     PP                        x           
       /    LeftRotate        /    RightRotate         /   \           
      p     ==========>      x     ===========>       P     PP    
       \                    /                                  
        x                  P                       
    #注意修改各节点的bf值
RR型,RL型分别与LL型和RL型对称
平衡算法
  • 该算法以失去平衡(bf=2)的节点为输入进行平衡
    LeftBalance( x )        //x左子树失去平衡
        y = left[x] ;
        case bf[y] in                   //  LL型
            LH :                        //        X
                bf[x] = EH ;            //       / \
                bf[y] = EH ;            //      Y   ^               Y
                RightRotate( T, x ) ;   //     / \      ==>       /   \
                                        //    Z   a              Z     X
                                        //   / \                / \   / \
                                        //  c   d              c   d a   ^

            RH :                        //  LR型
                z = right[y] ;          //
                case bf[z] in           //        X                X
                    LH :                //       / \              / \
                        bf[y] = EH ;    //      Y   ^            Z   ^  
                        bf[x] = RH ;    //     / \      ==>     / \        
                    EH :                //    a   Z            Y   c    
                        bf[y] = EH ;    //       / \          / \       
                        bf[x] = EH ;    //      b   c        a   b      
                    RH :                //             Y        
                        bf[y] = LH ;    //           /   \      特别要注意
                        bf[x] = EH ;    //  ==>     Z     X     平衡因子的
                    bf[z] = EH ;        //         / \   / \    取值变化
                    LeftRotate( T, y ) ;//        c   d a   ^
                    RightRotate( T, x ) ;

    /*右平衡与做平衡对称*/
AVL树的插入
    AVLTreeInsert( t, e, taller )   //t:子树根;e:要插入的节点;taller:布尔值,检测高度是否增加
        if t == nil                 //指向指针的指针 
            t = e ;
            taller = true ;         //只有树增高了,才需要平衡
        else
            if key[t] == key[e]     //不允许有相同关键字
                taller = false ;    //taller必须是可传递值(指针或全局变量)
                return false ;
            
            else if key[t] > key[e] //往左子树插
                if !AVLTreeInsert( left[t], e, taller )
                    return false ;
                if taller
                    case bf[t] in 
                        LH :
                            LeftBalance( t ) ;
                            taller = false ;
                        EH :
                            bf[t] = LH ;
                            taller = ture ;
                        RH :
                            bf[t] = EH ;
                            taller = false ;
            else                    //往右子树插
                /*与左子树对称*/
                ...
        return true ;