数据结构 平衡二叉排序树有话说

• 平衡二叉排序树又称AVL树。

• 平衡二叉排序树性质：

① 左右子树的高度之差的绝对值小于等于1。
② 左右子树也是平衡二叉排序树。

平衡二叉排序树比普通的二叉排序树查询效率要高。

• 平衡因子：结点的左子树深度与右子树深度之差。对于一棵平衡二叉排序树，其所有结点的平衡因子只能是-1、0或1。

• 求平衡二叉排序树各结点因子：

每个结点旁边的数字就是每个结点的平衡因子。

计算过程：
如A结点，它的左右子树是根节点为B和C的子树
对于根节点为B的子树，树的深度是1，对于C，深度是2，则可以得到A结点的平衡因子为 1-2=-1。其他结点以此类推。

• 如何恢复失去平衡的平衡二叉排序树：

  1️⃣ LR型
  现将B改为C的左孩子，而C原来的左孩子改为B的右孩子；然后将A改为C的右孩子，C原来的右孩子改为A的左孩子。这相当于对B做了一次逆时针旋转，对A做一次顺时针旋转。
  

  2️⃣ RL型
  现将B改为C的右孩子，而C原来的右孩子改为B的左孩子；然后将A改为C的左孩子，C原来的左孩子改为A的右孩子。这相当于对B做了一次顺时针旋转，对A做一次逆时针旋转。
  
  RR型，LL型以此类推。