聊聊数据结构与算法：平衡二叉树
二叉查找树
我们先了解一下二叉查找树。
二叉查找树（Binary Search Tree），也称为二叉搜索树、有序二叉树（Ordered Binary Tree）或排序二叉树（Sorted Binary Tree），是指一课空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
二叉查找树的结构如下图所示：
左图和右图都是二叉查找树， 左图为平均情况，右图为最坏情况。因此我们得知：
- 对于无序数组[6,2,8,1,4,3]，可以构建出左图的二叉查找树，查找的性能优于线性表，为O(log(n))。
- 对于有序数组[1,2,3,4,6,8]，构建的二叉查找树退化成了链表（右图），查找的性能与线性表一样差，都为O(n)，并且我们知道，有序数组可以使用性能为O(log(n))的二分查找算法，反而优于二叉查找树的查找性能。
因此，二叉查找树的查找性能主要取决于树的形状，如果想要保持查找性能在任何情况下都为O(log(n))，则需要避免二叉树的不平衡。
平衡二叉树
平衡二叉树（Balanced Binary Tree），也称平衡树、自平衡二叉查找树（Self-Balancing Binary Search Tree）、平衡二叉搜索树或AVL树。其中AVL树是最早发明的自平衡二叉查找树，得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，通常以AVL树泛指这类的自平衡二叉查找树。
平衡二叉树是一种结构平衡的二叉查找树，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log(n))。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。
平衡因子
我们将节点的左子树高度减去它的右子树高度（有时相反）的值称为平衡因子（Balance Factor），简称BF值。带有平衡因子1、0或 -1的节点被认为是平衡的，带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
上图是两棵二叉查找树，左图节点9的左边的高度是5，右边高度是4，所以节点9的平衡因子值是5-4=1，以此类推我们得到了所有节点的平衡因子值。可以看到左图节点7的平衡因子值为2，大于平衡二叉树定义的最大高度差1，不符合平衡条件，因此左图不是一棵平衡二叉树，而右图就是一棵平衡二叉树。
最小不平衡子树
距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树，我们称为最小不平衡子树。如下图所示：
平衡二叉树实现原理
平衡二叉树构建的基本思想就是在构建二叉查找树的过程中，每当插入一个节点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉查找树特性的前提下，调整最小不平衡子树中各节点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。大致步骤如下：
- 从根节点开始递归查找新节点的插入位置来新增节点
- 新增节点后逆向回溯途经节点，检查平衡因子的绝对值是否大于1来判断是否平衡
- 发现不平衡的节点x时，如果节点x平衡因子值为正值则说明左边高（即左边为不平衡边），为负值则说明右边高
- 获取节点x不平衡边的下一个节点y，检查节点y哪边高来判断需要的旋转操作，例如节点x左边高，节点y左边高，则为左左情况，需要以节点y为轴心点进行右旋转。
AVL树的旋转操作可分为四种：
Root：旋转前不平衡树的根节点
Pivot：旋转时的轴心点，也是旋转后的根节点
节点5左边高，节点3也是左边高，为左左情况，则以节点3为轴心点进行右旋转（顺时针旋转），从而使树达到平衡。
节点3右边高，节点5也是右边高，为右右情况，则以节点5为轴心点进行左旋转（逆时针旋转），从而使树达到平衡。
节点5左边高，节点3右边高，为左右情况，则先以节点4为轴心点进行左旋转，再以节点4为轴心点进行右旋转，从而使树达到平衡。
节点3右边高，节点5右边高，为右左情况，则先以节点4为轴心点进行右旋转，再以节点4为轴心点进行左旋转，从而使树达到平衡。
总结
AVL树的查找性能是很优越的，但在动态插入中保证树的完美平衡的代价太高，AVL树的缺点是频繁的旋转，需要维护树的节点的平衡以及总体上的复杂性，尤其是删除操作。但是通过旋转来重新平衡一棵二叉树的思想是富有成效的，也促使了很多基于AVL树改良和变种的数据结构被发明出来。