本文共 1511 字，大约阅读时间需要 5 分钟。
二叉查找树(BSTree)中进行查找、插入和删除操作的时间复杂度都是O（h），其中h为树的高度。
BST的高度直接影响到操作实现的性能，最坏情况下，二叉查找树会退化成一个单链表，比如插入的节点序列本身就有序，这时候性能会下降到O(n)。可见在树的规模固定的前提下，BST的高度越低越好。平衡二叉树
平衡二叉树是计算机科学中的一类改进的二叉查找树。
平衡二叉树具有以下性质：（1）一棵空树是平衡二叉树
（2）如果树不为空，它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。
这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。一棵好的平衡二叉树的特征：
（1）保证有n个结点的树的高度为O(logn)（2）容易维护，也就是说，在做数据项的插入或删除操作时，为平衡树所做的一些辅助操作时间开销为O(1)平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树等。
AVL树是最先发明的自平衡二叉查找树，所以一般提到平衡二叉树一般就指AVL树，区别于红黑树、伸展树等。
AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
AVL树如何保持平衡
平衡二叉树的关键在平衡，那么它的平衡是如何保持的呢？
Adelson-Velskii 和 Landis 提出了一个动态地保持二叉排序树平衡的方法，其基本思想是：在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。通常将这样得到的平衡二叉排序树简称为 AVL 树。 现在我们定义平衡因子和最小不平衡子树的概念。 （1）平衡因子 在二叉树中，任何一个节点v的平衡因子都定义为其左、右子树的高度差。空树的高度定义为-1。 在二叉查找树T中，若所有节点的平衡因子的绝对值均不超过1，则称T为一棵AVL树。 （2）最小不平衡子树 最小不平衡子树以离插入结点最近、且平衡因子绝对值大于 1 的结点作根结点的子树。旋转操作
旋转操作是一种调整树结构而不改变二叉查找树特性的手段。
这里要理解树旋转的意义，树的最终目的不是维护节点与节点之间的层级关系，关键是如何用AVL树这种数据结构进行更好的查找和搜索。
针对四种不平衡类型的调整
为了简化讨论，不妨假设二叉排序树的最小不平衡子树的根结点为 A ，则调整该子树的规律可归纳为下列四种情况：
（1）LL 型：LL情况需要右旋解决，如图所示：
RR情况需要左旋解决，如图所示：
LR情况需要左右（先B左旋转，后A右旋转）旋解决，如图所示：
RL情况需要右左旋解决（先B右旋转，后A左旋转），如图所示：
代码实现
AVL树是一棵二叉查找树，与普通二叉查找树不同的是，在插入和删除节点之后需要重新进行平衡，因此继承并重写普通二叉查找树的insert和delete方法，就可以实现一棵AVL树。
| 1 | 待续。 |
转载地址：http://ulolo.baihongyu.com/