二叉树算法 - 平衡二叉树（AVL）的定义和实现原理
- 1 min数据结构与算法系列（三十二）
引子
上一篇我们介绍了二叉排序树，并且提到理想情况下，二叉排序树的插入、删除、查找时间复杂度都是 O(logn)，非常高效，而且它是一种动态的数据结构，插入删除性能合查找一样好，不像之前提到的二分查找，虽然查找性能也是 O(logn)，但是需要先对线性表进行排序，二排序的最好时间复杂度也是 O(nlogn)，所以二分查找不适合动态结构的排序。
但是我们也提到如果二叉排序树构造的不好的话就会退化成斜树：
此时按照之前的实现算法性能退化成了 O(n)，所以如何构造二叉排序树很重要，我们的理想情况是满二叉树和完全二叉树，它们的性能都是 O(logn)，所以我们在构造二叉排序树的时候要尽可能像它们靠近，才能得到最佳的操作性能，由此引出了我们今天的话题——平衡二叉树。
什么是平衡二叉树
平衡二叉树的英文名是 Self-Balancing Binary Search Tree 或者 Height-Balancing Binary Search Tree，译作自平衡的二叉查找树，或者高度平衡的二叉查找树，二叉查找树和二叉排序树是一个意思，只是叫法不同，简称平衡二叉树，也叫 AVL 树（平衡二叉树作者的名字首字母），所以平衡二叉树首先是二叉排序树，并且这个二叉排序树是左右高度平衡的，这么讲有点抽象，具体来说，平衡二叉树要求每个节点的左子树和右子树的高度差至多等于 1，这个高度（深度）差的值叫做平衡因子 BF，也就是说 BF 的值不能大于1，否则就不是平衡二叉树。
我们简单看几个例子：
- 图1满足平衡二叉树的定义，是平衡二叉树；
- 图2所示二叉树不是二叉排序树，所有不是平衡二叉树；
- 图3不满足平衡因子小于等于1的要求，对58这个节点来说，平衡因子BF的值是3，因而不是平衡二叉树；
- 图4满足平衡二叉树的定义，是平衡二叉树；
我们之所以这么约束平衡二叉树，是为了保证它能够始终做到插入、删除、查找的时间复杂度是 O(logn)。
了解了什么是平衡二叉树，下面我们来看看它的实现原理。
平衡二叉树的实现原理
平衡二叉树的基本实现思路，是在构建二叉排序树的时候，每插入一个节点，都要检查这个节点的插入是否破坏了原有的平衡性，如果是的话，则找出最小不平衡子树，在保证整体二叉排序树的前提下，通过左旋或者右旋的方式将其调整为平衡子树。从而动态维护这棵平衡二叉树。
1、最小不平衡子树
距离插入节点最近的，且平衡因子绝对值大于1的节点为根的子树，叫做最小不平衡子树：
比如上图中以存储元素58的节点为根的子树叫做最小不平衡子树。
2、左旋/右旋
所谓左旋和右旋指的是最小不平衡子树旋转的方向。
如果平衡因子小于 -1，即右子树高度值比较大，则需要左旋：
反之，如果平衡因子大于1，即左子树高度值比较大，则需要右旋：
当然为了方便你理解原理，我们这里给出的都是最简化的情况，实际处理过程中比这个更复杂，下一篇我们将具体给你演示如何通过代码在各种情况下实现平衡二叉树并讨论对应的时间复杂度。