平衡二叉树（AVL树）性质
- 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
- 平衡二叉树很好的解决了二叉查找树（二叉搜索树）退化成链表的问题，把插入、查找、删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，但是相对于二叉查找树来说，时间上稳定了很多。
- 平衡二叉树大部分操作和二叉查找树类似，主要不同在于插入删除的时候平衡二叉树可能被改变，并且只有从那些插入点到根结点的路径上的结点的平衡性可能被改变，因为只有这些结点的子树可能变化。
- 平衡二叉树不平衡的情形：
把需要重新平衡的结点叫做a，由于任意两个结点最多只有两个儿子，因此高度不平衡时，a结点的两棵子树的高度相差2.这种不平衡可能出现在下面4种情况中：
（1）对a的左儿子的左子树进行一次插入
（2）对a的左儿子的右子树进行一次插入
（3）对a的右儿子的左子树进行一次插入
（4）对a的右儿子的右子树进行一次插入
情形1和4是关于a的镜像对称，情形2和3也是关于a的镜像对称，因此理论上看只有两种情况，但编程的角度还是4种。第一种情况是插入发生在“外边”的情形（左左或右右），该情况可以通过一次单旋转完成调整；第二种情况是插入发生在“内部”的情形（左右或右左），这种情况比较复杂，需要通过双旋转来调整。
调整措施
- 单旋转：
左左就进行一次右旋，将需要调整平衡的a结点的左子结点b调整到a原本所在的位置，a调整到原左子节点b的右子节点，接着b的右子节点转换成a的左子节点，a的右子节点不变。
右右如上进行一次左旋，将需要调整平衡的a结点的右子节点b调整到a的位置，然后a调整为b的左子节点，b的左子节点调整为a的右子节点，而b的右子节点不变，a的左子节点不变。
- 双旋转：
对于左右和右左两种情况，单旋转不能解决问题，要经过两次旋转。对于左右情况，为使树恢复平衡，我们需要进行两步，第一步将需要平衡的结点a的左子节点b作为根进行一次左左旋转，使得b的右子节点c变为b所在位置，b成为c的左子节点，然后再进行一次右旋，使得c变为a原本所在位置，a变为c右子节点，c的右子结点变为a的左子节点，从而达到平衡。
对于右左情况则需要先进行一次右旋，再进行一次左旋即可完成平衡。
AVL树的删除操作
- 同插入操作一样，删除结点时也有可能破坏平衡性，这就要求我们删除的时候要进行平衡性调整。
- 删除分为以下几种情况：
首先在整个二叉树中搜索要删除的结点，如果没搜索到直接返回不作处理，否则执行以下操作：
（1）要删除的节点是当前根节点T。如果左右子树都非空，在高度较大的子树中实施删除操作。分两种情况：
①左子树高度大于右子树高度，将左子树中最大的那个元素赋给当前节点，然后删除左子树中元素值最大的那个节点。
②左子树高度小于右子树高度，将右子树中最小的那个元素赋给当前根节点，然后删除右子树中元素值最小的那个节点。
如果左右子树中有一个为空，那么直接使用那个非空子树或者是NULL替换当前根节点即可。
（2）要删除的节点元素小于当前根节点T的值，在左子树中删除。递归调用，在左子树中实施删除，这个需要判断当前根节点是否仍满足平衡条件，如果满足平衡条件，只需更新当前结点T的高度信息。否则需要进行旋转调整：
如果T的左子节点的左子树的高度大于T的左子节点的右子树高度，进行相应的单旋转，否则进行双旋转。
（3）要删除的结点元素值大于当前根节点T的值，在右子树中进行删除。