4.6 平衡二叉树

4.6.1 平衡二叉树的定义

平衡二叉树,又被称为AVL树（有别于AVL算法），且具有以下性质：

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

AVL是两个人的名字，ASL是平均查找长度，不一样

结点的平衡因子=左子树高-右子树高

平衡二叉树结点的平衡因子的值只可能是-1、0、1。

img

4.6.2 平衡二叉树的存储结构（用链式存储）

平衡二叉树的类型表述（与二叉树不一样）

typedef struct AVLNode{
	int key;      //数据域
    int balance;  //平衡因子
	struct AVLNode *lchide, *rchild; //左、右孩子指针
}AVLNode, *AVLTree;

4.6.3 平衡二叉树的插入

在平衡的二叉排序树中插入一个结点导致不平衡，如何调整平衡？ 解决方法：调整“最小不平衡树”

四种调整方法：

• ①LL：在A的左孩子的左子树中插入导致A的不平衡，将A的左孩子右上旋。
• ②RR：在A的右孩子的右子树中插入导致A的不平衡，将A的右孩子左上旋。
• ③LR：在A的左孩子的右子树中插入导致A的不平衡，将A的左孩子的右孩子，先左上旋再右上旋。
• ④RL：在A的右孩子的左子树中插入导致A的不平衡，将A的右孩子的左孩子，先右上旋再左上旋。

4.6.4 查找效率分析

平均查找的时间复杂度=$O(log~2~h)$

4.6.5 高度为h的平衡二叉树的最少结点数

递推公式：$n_h=n_{h-1}+n_{h-2}+1$