文章目录
  1. 1. avl
    1. 1.1. 平衡因子
    2. 1.2. 旋转
      1. 1.2.1. LL
      2. 1.2.2. RR
      3. 1.2.3. LR
      4. 1.2.4. RL
    3. 1.3. avl插入操作
      1. 1.3.1. RR插入
      2. 1.3.2. LR插入
      3. 1.3.3. RL插入
    4. 1.4. avl插入代码

avl

一种自平衡二叉查找树（self-balancing binary search tree）。
这种二叉查找树在插入和删除操作中，可以通过一系列的旋转操作来保持平衡，从而保证了二叉查找树的查找效率。
最终这种二叉查找树以他们的名字命名为“AVL-Tree”，它也被称为平衡二叉树（Balanced Binary Tree）。

平衡因子

为了保证平衡，AVL树中的每个结点都有一个平衡因子（balance factor，以下用BF表示），它表示这个结点的左、右子树的高度差，也就是左子树的高度减去右子树的高度的结果值。AVL树上所有结点的BF值只能是-1、0、1。反之，只要二叉树上一个结点的BF的绝对值大于1，则该二叉树就不是平衡二叉树。图1演示了平衡二叉树和非平衡二叉树。

avl_1

旋转

AVL树的旋转一共有四种情形，注意所有旋转情况都是围绕着使得二叉树不平衡的第一个节点展开的。
旋转就是一个圆圈的方向，逆时针或顺时针

LL

平衡二叉树某一节点的左孩子的左子树上插入一个新的节点，使得该节点不再平衡。这时只需要把树向右旋转一次即可，如图所示，原A的左孩子B变为父结点，A变为其右孩子，而原B的右子树变为A的左子树，注意旋转之后Brh是A的左子树（图上忘在A于Brh之间标实线）

avl_2

RR

平衡二叉树某一节点的右孩子的右子树上插入一个新的节点，使得该节点不再平衡。这时只需要把树向左旋转一次即可，如图所示，原A右孩子B变为父结点，A变为其左孩子，而原B的左子树Blh将变为A的右子树。

avl_3

LR

平衡二叉树某一节点的左孩子的右子树上插入一个新的节点，使得该节点不再平衡。这时需要旋转两次，仅一次的旋转是不能够使二叉树再次平衡。如图所示，在B节点按照RR型向左旋转一次之后，二叉树在A节点仍然不能保持平衡，这时还需要再向右旋转一次。

avl_4

RL

平衡二叉树某一节点的右孩子的左子树上插入一个新的节点，使得该节点不再平衡。同样，这时需要旋转两次，旋转方向刚好同LR型相反。

avl_5

avl插入操作

具体步骤如下：

  1. 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；

  2. 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；

  3. 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整:
    当最小不平衡子树的根节点的BF值为2时：

    如果最小不平衡树的根节点的左孩子的BF值为1，则进行LL型旋转；
    如果最小不平衡树的根节点的左孩子的BF值为-1，则进行LR型旋转。

    当最小不平衡子树根的BF值为-2时：

    如果最小不平衡树的根节点的右孩子的BF值为1，则进行RL型旋转；
    如果最小不平衡树的根节点的右孩子的BF值为-1，则进行RR型旋转。

如果是LL型或RR型，只需旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；
如果是LR型或LR型，则需旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，
第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；

最后计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。

RR插入

avl_9

avl_8

LR插入

avl_7

RL插入

avl_6

avl插入代码

https://github.com/don7hao/algorithm/tree/master/avl