1、概述

为什么引入平衡二叉树？

$\quad \quad$含有n个结点的二叉排序树的平均查找长度ASL和树的形态有关

问题： 如何提高形态不均衡的二叉排序树的查找效率？

解决办法： 做平衡化处理，尽量让二叉树的形状均衡，转换成平衡二叉树。

2、定义

平衡二叉树（balanced binary tree)

• 又称AVL树（Adelson - VelskII and Landis)。

• 一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：

  • 1）左子树与右子树的高度之差的绝对值小于等于1；
  • 2）左子树与右子树也是平衡二叉树。

$\quad \quad$为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子（BF）。
$平衡因子=结点左子树的高度-结点右子树的高度$平衡因子=结点左子树的高度−结点右子树的高度

$\quad \quad$根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是-1、0、1。

$\quad \quad$对于一棵有n个结点的AVL树，其高度保持在$O(log_2n)$O(log2​n)数量级，ASL也保持在$O(log_2n)$O(log2​n)数量级。

3、失衡二叉排序树的分析与调整

$\quad \quad$当我们在平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现平衡因子绝对值大于1的结点，如：2、-2。

$\quad \quad$如果在一棵AVL树中插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡。

平衡调整的四种类型

• LL型：左子树高度大于右子树高度
• LR型：一部分结点左子树高度大于右子树高度，另一部分右子树高度大于左子树高度
• RL型：一部分右子树高度大于左子树高度，另一部分结点左子树高度大于右子树高度
• RR型：右子树高度大于左子树高度

如何进行平衡调整的四种类型

3.1 LL型—右旋转

3.2 RR型—左旋转

3.3 LR、RT型—双旋转

未完待续