什么是 AVL 树？

前面我们有学过 BST（二分搜索树），它唯一的不足是，当数据像 1-2-3-4-5 这样的时候，查询性能与单链表一致，无法发挥出 BST 的优势。在下面的 BST 中查找 4 这个节点，只能逐个查找。

为了解决 BST 性能问题。1962 年 G. M. A delson- V elsky 和 E. M. L andis 在他们的论文《An algorithm for the organization of information》中提到了一种方法可以解决这个问题。它就是 AVL 这种数据结构，AVL 由两位发明者的姓名首字母命名。

AVL 树需要满足两个条件：

1. 是一颗 BST；

2. 所有节点的左子树高度与右子树高度差的绝对值不能大于 1；

为了满足第2个条件，需要 AVL 树的节点记录其高度和平衡因子（左子树高度与右子树高度差）。通俗地讲，AVL是一颗可以自平衡的 BST，也就是说当有新的节点插入后，一但破坏了第二个条件，就需要调整平衡性让其满足第二个条件。采用的方式有两种：左旋转和右旋转。

我们先看一颗 AVL 树：

上面这课二叉树满足 AVL 树的条件，如果插入元素 1，它将失去平衡性，3,4,5 这几个节点的平衡因子为 2，不满足 AVL 树的第二个条件，看图：

有两种方式可以解决这种不平衡性：右旋转和左旋转。我们下节内容将探讨这两个概念。

大家加油！！！

推荐阅读：

二分搜索树 BST（Binary Search Tree）

使用 Swift 实现一颗二分搜索树

图解数据结构和算法