平衡二叉树（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$，则平衡。

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$的位置。