二叉平衡树(AVL树）
什么是平衡二叉树
前戏~
树的高度
树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度或者高度
平衡因子
平衡因子（Balance Factor，简称BF）: BF(T) = hL-hR，
其中hL和hR分别为T的左、右子树的高度
平衡二叉树
平衡二叉树（Balanced Binary Tree）（AVL树），平衡二叉树中不存在平衡因子大于 1 的节点，即|BF(T) |≤ 1。在一棵平衡二叉树中，节点的平衡因子只能取 0 、1 或者 -1 ，分别对应着左右子树等高，左子树比较高，右子树比较高。
注意：平衡二叉树也是一棵搜索树，所以搜索呀，删除呀等操作，对它一样是适用的，只是插入以后，可能会破坏平衡因子，所以待会要单独讲解平衡二叉树插入以后的调整问题，让树仍然保持是棵查找树
平衡二叉树的性质
给定结点数为 n的AVL树的最大高度为O(log2n)
平衡二叉树的作用
可能有小伙伴读完什么树高、平衡因子，吧啦吧啦又来了一串定义、要求、性质，头已经大了
平衡二叉树的调整（难点）
右单旋
形象化例子：将Mar 、 May 、 Nov依次插入
不平衡的发现者是Mar，麻烦结点Nov 在发现者右子树的右边，因而叫 RR 插入，需要RR 旋转（右单旋）
右单旋原理图如下：
右单旋理解
小伙伴们看着原理图。现在可以把这棵树想象得很柔软，然后你握住了平衡因子处于中间地位的B结点，闭上双眼，使劲摇动它，在重力的作用下，发现者B结点变成了新的根。由搜索二叉树的性质告诉我们，在原来的树中，B结点是大于A结点的，于是现在新树中A结点成为了B结点的左子树，BL因为比B结点小但是又比A结点大，所以挂在了A的右子树上。
左单旋
形象化例子：将Aug 和 Apr插入到原本的平衡二叉树中
不平衡的发现者是Mar，麻烦结点Apr在发现者左子树的左边，因而叫 LL 插入，需要LL 旋转（左单旋）
左单旋原理图如下：
左单旋理解
咱们继续看着原理图。现在可以把这棵树想象得很柔软，然后你握住了平衡因子处于中间地位的B，闭上双眼，使劲摇动它，在重力的作用下，发现者B变成了新的根。二叉查找树的性质告诉我们，在原来的树中，B是小于A的，于是新树中，A变成了B的右子树，BL因为还是比B小，依旧挂在B的左子树，BR了，也是根据二叉查找树的性质，它只能到现在A的左子树挂着了。
左右双旋
形象化例子：将Jan插入到Mar的左子树上
不平衡的发现者是May，麻烦结点Jan在左子树的右边，
因而叫 LR 插入，需要LR 旋转（左右单旋）
左右双旋原理图如下：
左右双旋理解
重点关注那三个结点，只要它们三平衡了，根据二叉搜索树的性质，其他点也可以相应调整平衡了。咱们继续看着原理图。现在子树C，对应上图的Mar。现在确实有一项插入进来了，无论它在插入到C的左子树还是C的右子树，它都来破坏平衡了。于是，我们可以将现在的树看作四棵子树由3个结点连接。为了重新平衡，我们可以看到不能让A再做根了，唯一的选择就是把平衡因子的大小是中间值C作为新的根结点，再结合二叉查找树的性质，迫使B做C的左儿子，A左C的右儿子，从而完全确定整棵树的最终位置。
右左双旋
形象化例子：将Fer插入到原本平衡的Dec的上面
不平衡的发现者是Aug，麻烦结点Feb在右子树的左边，
因而叫 RL 插入，需要RL 旋转
右左双旋原理图：
左右双旋理解
因为和上文的左右双旋类似，相信大家也理解啦。所以这里不在赘述啦~
总结
到这里为止，平衡二叉树为了调整插入而带来的不平衡的四种四种方式已经讲完啦~
数起来是四种，实际就是一种，有没有发现了。左单旋、右单旋要关注的核心结点是被破坏以后衡因子居中的结点
对于左右双旋和右左双旋也是类似的，我上文着重说，注意那三个结点，咱们要去处理它们三个中平衡因子居中的那个结点。其实也可以做这种想，小学集合站队的时候，中等高度的小盆友出来出来站好了，其他的位置就可以类推了，这里就是取平衡因子居中的点为标杆。
