1. AVL 树的概念
1.1 AVL 树的来源以及简单的介绍
AVL 树是最先被发明出来的平衡二叉搜索树。AVL 树是一颗空树，或者是具备下面性质的二叉搜索树：它的左右子树均是 AVL 树，并且左右子树的高度差不能大于 1（即平衡因子）。AVL 树是一颗高度平衡二叉搜索树，通过控制它的高度来控制平衡。当然，AVL 树还是遵从二叉搜索树的性质，即根节点大于左边节点，小于右边节点。
AVL 树的得名是因为发明它的两个前苏联科学家：G. M. Adelson-Velsky 和 E. M. Landis，他们在 1962 年的论文中首次提出了平衡二叉搜索树这个概念。
为了后期更好的理解以及去实现 AVL 树，我们需要清楚一个概念：平衡因子。
1.2 平衡因子
在 AVL 树中，每个结点都有平衡因子，平衡因子就是为了让我们更好更容易的去检测树是否是平衡的。由于每本教材对平衡因子的定义不同，这里确认一下定义：平衡因子是右子树的高度减去左子树的高度。也就是说如果一颗二叉搜索树平衡了，那么就需要让平衡因子等于 -1、0 或 1，因为树的高度差不能大于 1，也就是平衡因子的绝对值不可以大于 1。当然，AVL 树不一定必须要有平衡因子，但是它在帮助我们更容易去检测树是否平衡时非常有用。
1.3 思考
当我们提到 AVL 树的平衡因子时，很多读者可能会问，为什么平衡因子允许为 -1 或 1，而不是要求为 0？这个问题的根源在于 AVL 树的设计目标是保持平衡，而不是要求每个节点的左右子树高度完全相等。虽然平衡因子为 0 的情况下树是最平衡的，但要求每个节点的平衡因子为 0 实际上是过于苛刻的。举个例子，当插入的节点数是偶数时，树中不可能每个节点的左右子树高度完全相同，这样就不可避免地会有一些节点的平衡因子为 -1 或 1。实际上，AVL 树允许平衡因子为 -1 或 1，这是为了保持树的平衡，同时避免不必要的旋转操作。
1.4 见一见平衡二叉搜索树的样子
2. AVL 树的实现——预备工作
AVL 树的预备工作其实很简单，我们需要先把每个节点的结构体定义出来。由于键值对我们后期经常使用，所以这次直接定义一个键值对类型的结构体。由于结构体的实现难度不是很大，下面我就简单的说一下结构体里面有什么：里面需要有一个 pair 类型的对象，它存储着键值对。另外，AVL 树是一颗三叉链的树，即，它是有左、右、父三个节点的，存储父节点的原因是和之后的更新平衡因子有关。在插入或删除节点后，我们需要从新节点向上回溯到根节点，检查并更新沿途节点的平衡因子。如果某个节点的平衡因子绝对值超过 1，则需要进行旋转操作来恢复平衡。此外，父指针的存在也便于在删除节点时快速找到其兄弟节点或进行双亲调整。
template<typename K, typename V>
struct AVLTreeNode {
std::pair<K, V> _kv;
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
int _bf; // 平衡因子
AVLTreeNode(const std::pair<K, V>& kv)
: _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}
};
接下来我们将基于此结构体实现 AVL 树的插入与平衡维护逻辑。
