文章目录
  1. AVL树的定义
  2. 单旋转
  3. 双旋转

AVL树的定义

AVL树是其每个节点的左右子树高度最多差1的二叉查找树。为了保持AVL树的这个性质，它的插入、删除操作相对于二叉查找树的插入、删除操作还需要进行一定的调整。这种调整称为旋转。

关于调整，先要分析有哪些不平衡的情况。记最深的不平衡点为A。

  • 对A的左子节点的左子树进行一次插入；
  • 对A的左子节点的右子树进行一次插入；
  • 对A的右子节点的左子树进行一次插入；
  • 对A的右子节点的右子树进行一次插入；

对于第1和第4种情形，只需要对树进行一次单旋转；对于第2和第3种情形，需要对树进行双旋转。

单旋转

对于情形1。

 

对于情形4。

双旋转

对于情形2。

 

对于情形3。

注：在实现时只需要保存每个节点的左右子树高度之差，即平衡因子。