前言
在之前的文章中曾提到 map 和 set 的底层实现基于红黑树，虽然红黑树会在后续讨论，但由于其难度较高，本文将先介绍另一种特殊的二叉搜索树——AVL 树，即平衡二叉搜索树。这里的'平衡'二字非常巧妙，下文将详细解释其中的奥妙。
AVL 树与红黑树一样，都是非常重要的自平衡二叉搜索树。相较于红黑树，AVL 树的复杂度相对较低，且其旋转操作与红黑树相似。本文将为大家详细讲解 AVL 树，带大家一步步理解这一数据结构。
1. AVL 树的概念
1. AVL 树的来源以及简单的介绍
AVL 树是最先被发明出来的平衡二叉搜索树。AVL 树是一颗空树，或者是具备下面性质的二叉搜索树：它的左右子树均是 AVL 树，并且左右子树的高度差不能大于 1（即平衡因子）。AVL 树是一颗高度平衡二叉搜索树，通过控制它的高度来控制平衡。当然，AVL 树还是遵从二叉搜索树的性质的，即根节点大于左边节点，小于右边节点。
AVL 树的得名是因为发明它的两个前苏联科学家：G. M. Adelson-Velsky 和 E. M. Landis，他们在 1962 年的论文中首次提出了平衡二叉搜索树这个概念（论文名《An algorithm for the organization of information》）。
为了后期更好地理解以及去实现 AVL 树，我们需要清楚一个概念：平衡因子。
2. 平衡因子
在 AVL 树中，每个结点都有平衡因子，平衡因子就是为了让我们更好更容易地去检测树是否是平衡的。由于每本教材对平衡因子的定义不同，这里确认一下定义：平衡因子是右边子树的高度减去左边子树的高度。也就是说如果一颗二叉搜索树平衡了，那么就需要让平衡因子等于 -1、0 或 1，因为树的高度差不能大于 1，也就是平衡因子的绝对值不可以大于 1。当然，AVL 树不一定必须要有平衡因子，但是它在开头说了，它可以帮助我们更容易去检测树是否平衡。
3. 思考
当我们提到 AVL 树的平衡因子时，很多读者可能会问，为什么平衡因子允许为 -1 或 1，而不是要求为 0？这个问题的根源在于 AVL 树的设计目标是保持平衡，而不是要求每个节点的左右子树高度完全相等。虽然平衡因子为 0 的情况下树是最平衡的，但要求每个节点的平衡因子为 0 实际上是过于苛刻的。举个例子，当插入的节点数是偶数时，树中不可能每个节点的左右子树高度完全相同，这样就不可避免地会有一些节点的平衡因子为 -1 或 1。实际上，AVL 树允许平衡因子为 -1 或 1，这是为了保持树的平衡，同时避免不必要的旋转操作。
4. 见一见平衡二叉搜索树的样子
说了这么多 AVL 树的概念，为了让各位更好的去了解 AVL 树，可以参考相关图示了解其形态。
2. AVL 树的实现——预备工作
AVL 树的预备工作其实很简单，我们需要先把每个节点的结构体定义出来。由于键值对我们后期经常使用，所以本文直接定义一个键值对类型的结构体。由于结构体的实现难度不是很大，下面简单说一下结构体里面有什么：里面需要有一个 pair 类型的对象，它存储着键值对。另外补充一个知识点：AVL 树是一颗三叉链的树，即，它是有左、右、父三个节点的，存储父节点的原因是为了后续更新平衡因子。
