1.平衡二叉树概念

AVL树是根据它的发明者G.M. Adelson-Velsky和E.M. Landis命名的。它是最先发明的自平衡二叉查找树，也被称为高度平衡树。相比于"二叉查找树"，它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。

AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理。

2.平衡二叉树修复方法

image.png image.png

当插入一个元素使平衡二叉树不平衡时，可能出现以下的四种情况：

• LL：称为"左左"。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。
  例如，在上面LL情况中，由于"根节点(8)的左子树(4)的左子树(2)还有非空子节点"，而"根节点(8)的右子树(12)没有子节点"；导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

• LR：称为"左右"。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。
  例如，在上面LR情况中，由于"根节点(8)的左子树(4)的左子树(6)还有非空子节点"，而"根节点(8)的右子树(12)没有子节点"；导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

• RL：称为"右左"。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。
  例如，在上面RL情况中，由于"根节点(8)的右子树(12)的左子树(10)还有非空子节点"，而"根节点(8)的左子树(4)没有子节点"；导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

• RR：称为"右右"。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。
  例如，在上面RR情况中，由于"根节点(8)的右子树(12)的右子树(14)还有非空子节点"，而"根节点(8)的左子树(4)没有子节点"；导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

3.修复

3.1 LL旋转

当平衡二叉树失去平衡，显示出上面LL的情况时，可以用下面的一次调整使其恢复平衡。

image.png

从上图看出，只需要将高度较大的左子树的根节点作为其父节点，然后，将其父节点作为右子树的根节点；这时，原来左子树的右子树需要移动到现在的右子树下，作为其左子树。

3.2 RR旋转

当平衡二叉树失去平衡，显示出上面RR的情况时，可以用下面的一次调整使其恢复平衡。

image.png

从上图看出，只需要将高度较大的右子树的根节点作为其父节点，然后，将其父节点作为左子树的根节点；这时，原来右子树的左子树需要移动到现在的左子树下，作为其右子树。

3.3 LR旋转

当平衡二叉树失去平衡，显示出上面LR的情况时，可以用下面的两次调整使其恢复平衡。

image.png

如上图，先将k1为树根的子树向左旋转，即和前面的RR调整的方向类似，然后在将以k3为树根的子树向右旋转。

3.4 RL旋转

当平衡二叉树失去平衡，显示出上面RL的情况时，可以用下面的两次调整使其恢复平衡。

image.png

如上图，先将k3为树根的子树向右旋转，即和前面的LL调整的方向类似，然后在将以k1为树根的子树向左旋转。