平衡二叉树

二叉排序树中,对其查找性能进行分析时,其平均查找长度和二叉树的形态有关,而它的形态取决于其数据集。
最好: $O(log_2n)$ (形态均匀,结构合理)
最坏: $O(n)$ (数据呈有序排列)

数据集(24,37,55,12,40),对应的两种情形分别如下:

平衡二叉树(AVL树)即是为了提高二叉排序树的查找效率,尽量让二叉树的形状均衡。

平衡二叉树或者是空树,或者是具有以下特征的二叉排序树:

  1. 左子树和右子树的深度之差的绝对值不超过1
  2. 左子树和右子树也是平衡二叉树

平衡因子:该结点左子树和右子树的高度差

问题的关键在于如何将二叉排序树调整为平衡二叉树。

步骤:插入结点时,首先按照二叉排序树处理,若插入结点后破坏了平衡二叉树的特性,需对平衡二叉树进行调整。
调整方法为:找到离插入结点最近且平衡因子绝对值超过1的祖先结点,以该结点为根的子树称为最小不平衡子树,可将重新平衡的范围局限于这棵子树。调整的过程称为平衡旋转

一般有以下几种情况:

  • LL平衡旋转:若在A的左子树的左子树上插入结点,使A的平衡因子从1增加至2,需要进行一次顺时针旋转。
  • RR平衡旋转:若在A的右子树的右子树上插入结点,使A的平衡因子从-1增加至-2,需要进行一次逆时针旋转。
  • LR平衡旋转:若在A的左子树的右子树上插入结点,使A的平衡因子从1增加至2,需要先进行逆时针旋转,再顺时针旋转。
  • RL平衡旋转:若在A的右子树的左子树上插入结点,使A的平衡因子从-1增加至-2,需要先进行顺时针旋转,再逆时针旋转。
-------------The End-------------