数据结构——平衡二叉树

平衡二叉树（AVL）

任意结点的平衡因子的绝对值不超过1（左子树高度$-$右子树高度）。

高度为$h$的最小平衡二叉树的结点数$N_h$：

右子树可以有三种选择：$N_{h}$、$N_{h-1}$、$N_{h-2}$。

• 如果是$N_{h}$，则加上根结点高度会超过$h$，不可能；
• $h-1$层的结点数一定大于$h-2$层的结点数，因此最小的平衡二叉树应在$h-2$层的子树上。

$$N_h=N_{h-1}+N_{h-2}+1$$

$N_0=0$，$N_1=1$。

判断

利用递归遍历的后序遍历过程：

1. 判断左子树是一棵平衡二叉树
2. 判断右子树是一棵平衡二叉树
3. 判断该结点为根的二叉树为平衡二叉树

判断条件：

若左子树和右子树均为平衡二叉树

且左子树与右子树高度的绝对值小于等于$1$，则平衡。

void Judge_AVL(BiTree bt, int &balance, int &h){
    int bl=0,br=0mhl=0,hr=0;
    if(bt==NULL){
        h=0;
        balance=1;
    }
    else if(bt->lchild==NULL&&bt->rchild==NULL){
        h=1;
        balance=1;
    }
    else{
        Judge_AVL(bt->lchild,bl,hl);
        Judge_AVL(bt->rchild,br,hr);
        if(hl>hr)
            h=hl+1;
        else
            h=hr+1；
        if(abs(hl-hr)<2&&bl=1&&br=1)
            balance=1;
        else
            balance=0;
    }
}

插入

对二叉排序树进行优化：先插入，再调整，每次调整最小不平衡二叉树

LL平衡旋转（右单旋转）

原因：在结点$A$的左孩子的左子树上插入了新结点。

调整方法：右旋操作——将$A$的左孩子$B$代替$A$，将$A$结点称为$B$的右子树根结点，而$B$的原右子树则作为$A$的左子树。

RR平衡旋转（左单旋转）

原因：在结点$A$的右孩子的右子树上插入了新结点。

调整方法：左旋操作——将$A$的右孩子$B$代替$A$，将$A$结点称为$B$的左子树根结点，而$B$的原左子树则作为$A$的右子树。

LR平衡旋转（先左后右双旋转）

原因：在结点$A$的左孩子的右子树上插入了新结点。

调整方法：先左后右双旋转——将$A$的左孩子$B$的右孩子结点$C$代替$B$，然后再将$C$结点向上代替$A$的位置。

RL平衡旋转（先右后左双旋转）

原因：在结点$A$的右孩子的左子树上插入了新结点。

调整方法：先右后左双旋转——将$A$的右孩子$B$的左孩子结点$C$代替$B$，然后再将$C$结点向上代替$A$的位置。