AVL树的平衡艺术：用C++写出会“站立”的二叉树（未完待续）

前言

        在前几日的文章中，我曾提到过map和set的底层实现是基于红黑树，可能有不少读者以为今天的文章会讲解红黑树——但NO，NO，NO，虽然红黑树我会在后续讨论，但由于其较高的难度，今天我并不会直接介绍红黑树。而是将带大家了解另一种特殊的二叉搜索树——AVL树，也就是俗称的“平衡二叉搜索树”。这里的“平衡”二字非常巧妙，接下来正文中我会详细解释这其中的奥妙。

        AVL树与红黑树一样，都是非常重要的自平衡二叉搜索树，但我认为相较于红黑树，AVL树的复杂度更低，且其旋转操作与红黑树的操作非常相似。今天，我将为大家详细讲解AVL树，带大家一步步攻克这个小“BOSS”。那么，系好安全带，准备好迎接这次有趣的挑战吧！

1.AVL树的概念

1.AVL树的来源以及简单的介绍

        AVL树是最先被发明出来的平衡二叉搜索树，AVL树是一颗空树（什么结点也木有），或者是具备下面性质的二叉搜索树：它的左右子树均是AVL树，并且左右子树的高度差不能大于1（后面即将叙述的平衡因子）。AVL树是一颗高度平衡二叉搜索树，通过控制它的高度来控制平衡（因为这个性质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树的样子，于是我自己制作一张图片来让各位更好的去了解AVL树。

2.AVL树的实现——预备工作

        AVL树的预备工作其实很简单，我们需要先把每个节点的结构体定义出来，由于键值对我们后期经常使用，所以小编这次直接定义一个键值对类型的结构体，由于结构体的实现难度不是很大，下面我就简单的说一下结构体里面有什么：里面需要有一个pair类型的对象，它存储着键值对，小编刚才漏说了一个知识点：AVL树是一颗三叉链的树，即，它是有左，右，父三个节点的，存储父节点的原因是和之后的更新平衡因