在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。
节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。AVL树的基本操作一般涉及运作同在不平衡的二叉查找树所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的“AVL旋转”。
以下图表以四列表示四种情况，每行表示在该种情况下要进行的操作。在左左和右右的情况下，只需要进行一次旋转操作；在左右和右左的情况下，需要进行两次旋转操作。
删除
从AVL树中删除，可以通过把要删除的节点向下旋转成一个叶子节点，接着直接移除这个叶子节点来完成。因为在旋转成叶子节点期间最多有log n个节点被旋转，而每次AVL旋转耗费固定的时间，所以删除处理在整体上耗费O(log n) 时间。
搜索
可以像普通二叉查找树一样的进行，所以耗费O(log n)时间，因为AVL树总是保持平衡的。不需要特殊的准备，树的结构不会由于查找而改变。（这是与伸展树搜索相对立的，它会因为搜索而变更树结构。）
以上资料来自于维基百科：https://zh.wikipedia.org/wiki/AVL树
发展历史
描述
AVL树是最先发明的自平衡二叉查找树，也被称为高度平衡树。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。
鲁道夫·贝尔于1972年发明红黑书，是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在时间内做查找，插入和删除，这里的是树中元素的数目。
1985年 Daniel Sleator 和 Robert Tarjan发明伸展树（Splay Tree），它是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。
2006年中国广东中山纪念中学的陈启峰发明Size Balanced Tree（简称SBT）。相比红黑树、AVL树等自平衡二叉查找树，SBT更易于实现。据陈启峰在论文中称，SBT是“目前为止速度最快的高级二叉搜索树”。SBT能在O(log n)的时间内完成所有二叉搜索树（BST）的相关操作，而与普通二叉搜索树相比，SBT仅仅加入了简洁的核心操作Maintain。由于SBT赖以保持平衡的是size域而不是其他“无用”的域，它可以很方便地实现动态顺序统计中的select和rank操作。
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 1962 | G. M. Adelson-Velsky和Evgenii Landis 发明AVL树 | ADELSON-VELSKII, G. M., & LANDIS, Y. An algorithmfor the organization ofinformation. |
| 1972 | 鲁道夫·贝尔发明“对称二叉B树”，Leo J. Guibas和Robert Sedgewick 于1978年的论文中将其改名为红黑树 | Guibas, L. J., & Sedgewick, R. (1978, October). A dichromatic framework for balanced trees. In Foundations of Computer Science, 1978., 19th Annual Symposium on (pp. 8-21). IEEE. |
| 1985 | Daniel Sleator 和 Robert Tarjan发明伸展树 | Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3), 652-686. |
| 2006 | 陈启峰发明Size Balanced Tree（简称SBT） | Qifeng, C. (2006). Size Balanced Tree. |
发展分析
瓶颈
1) 借助高度或平衡因子，为此需要改造元素结构，或额外封装→伸展树可以避免。
2) 实测复杂度与理论复杂度上有差距。插入、删除后的旋转成本不菲。删除操作后，最多旋转O(logN)次，（Knuth证明，平均最坏情况下概率为0.21次），若频繁进行插入/删除操作，得不偿失。
3) 单词动态调整后，全树拓扑结构的变化量可达O(logN)次。红黑树为O(1)
以上内容来自于：https://blog.csdn.net/u010585135/article/details/41852945
未来发展方向
AVL树这种平衡策略比较老了，而且编程也比较复杂，现在用处不多，不过理解了AVL树可以帮助我们更好的理解红黑树，伸展树（Splay Tree），B-树等其他的平衡策略
Contributor: Zhixiang Chi
