AVL 树的模拟实现（入门必看，图文并茂）
前言
AVL树的底层也是搜索二叉树，由于搜索二叉树的在某种特殊情况下会变成单支树的情况，这种情况下的搜索二叉树进行插入和删除的效率就会从O(longN)变成O(N)，AVL的出现就是为了优化原始搜索二叉树的情况
相同的树节点的元素由于插入不同，形成类似于单支的情况
内容摘要
本文内容包括AVL树概念的理解、AVL树的两个特性、AVL树的四种旋转方式以及引发这四种旋转方式的条件、四种旋转方式的机理、四种旋转方式的的平衡因子更新、进行插入引发旋转的三种情况，以及如何进行将搜索二叉树优化成AVL树、AVL树的验证方式的思路分析，并且提供了两组测试用例进行验证。
AVL树的概念
AVL树就是通过普通搜索二叉树通过控制每个根节点的左右子树的高度差的不超过1进行优化形成的。至于这里为什么是1而不是0，按照常理来说，每个子树的高度差为0不应该插入删除查找等操作的效率更高吗？？当这棵树有2个节点对于根节点来说，是不能够将左右子树的高度差变成0，1已将是退而求其次的最优解了。
这里介绍一下平衡因子的概念，平衡因子就是用来记录每个节点左右子树的高度差，平衡因子的数值是通过右子树高度-左子树高度决定的
注意：平衡因子的概念不是每个每个AVL树都存在的，只是我们是通过平衡因子进行理解和优化搜索二叉树，从而实现AVL树的。
AVL树的特性
- 每个子树都是AVL树
- 左右子树的高度差（简称平衡因子）的绝对值不超过1
AVL树的旋转方式
旋转的作用：通过旋转进行降低树的高度，进而降低左右树的高度差，使其树的结构区域稳定。
右单旋
- 抽象图
将作为旋转的轴节点命名为parent节点，将parent的左孩子节点命名为subL节点，这里的60就是parent节点，30就是subL节点。
- 具象图
当h=2时，只有a位置的结构是①时，才能保证在左边进行插入时一定会引发树的高度变化，进而引发右单旋进行调整树的结构，至于b,c位置则是什么结构都是没有任何影响的可以是①②③中结构的任意一种，在a的叶子节点的孩子节点进行插入，都会引发右旋。
引发右单旋情况总结：
通过抽象图和具象图来看，在左树高度比右树的高度等于2时，会引发右旋，简称左边高的左边高
平衡因子的更新：
旋转完成后将parent节点和subL节点的平衡因子更新成0即可。
右单旋的实现方式
将subL的右子树作为parent的左子树，然后将parent为根节点的树作为subL的右子树
注意：这里进行节点的链接过程，一定要注意更新节点的父亲节点，防止破坏AVL树的结构
代码实现
左单旋
左单旋触发情况：右边高的右边高
- 抽象图
具象图的逻辑和上面的右单旋逻辑完全相同，这里就不再进行画图分析
将进行为轴进行旋转的节点命名为parent节点（平衡因子的绝对值为2），将parent节点的右孩子命名为subR节点。
平衡因子的更新
和右单旋的方式一致，将parent节点和subR节点中的平衡因子更新成0。
左单旋的实现方式
将subR的左节点作为parent的右节点，然后将以parent作为subL的左节点，然后更新节点的父亲节点。
代码实现
右左双旋
右左双旋触发情况：右边高的左边高
左边高又分为两种情况，分别是左边高的左边高和左边高的右边高，这两种情况虽然都是归属于左边高，但是这两种情况进行平衡因子的更新是不同的。
- 抽象图
- 具象图
将30节点（平衡因子的绝对值为2）命名为parent节点，将parent节点的右孩子命名为subR节点，subR的左孩子命名为subRL节点
右左双旋的本质其实就是通过第一次选装将原来右边高的左边高的结构转换成右边高的右边高，然后通过左单旋进行降低树的高度差。
平衡因子的更新
平衡因子的更新分为三种情况
- 当subRL的平衡因子的值为0时，将parent、subR、subRL的平衡因子更新成0.
- 当subRL的平衡因子的值为1时，将parent更新成-1，subR、subRL的平衡因子更新成0.
- 当subRL的平衡因子的值为-1时，将subR更新1，parent、subRL的平衡因子更新成0.
实现方式：通过复用左单旋和右单旋进行实现。
代码实现
左右双旋
- 抽象图
将30节点（平衡因子的绝对值为2）命名为parent节点，将parent节点的左孩子命名为subL节点，subL的右孩子命名为subLR节点
平衡因子的更新
平衡因子的更新分为三种情况
- 当subLR的平衡因子的值为0时，将parent、subR、subRL的平衡因子更新成0.
- 当subLR的平衡因子的值为1时，将subL平衡因子更新成-1，subR、subRL的平衡因子更新成0.
- 当subLR的平衡因子的值为-1时，将parent平衡因子更新成1、subL、subLR的平衡因子更新成0.
实现方式：通过复用左单旋和右单旋进行实现。
代码实现
AVL树的模拟实现
基本框架
节点类中和我们前面实现的搜索二叉树除了多了一个平衡因子的定义，还多了一个指针，通过三叉链的形式进行定义这个节点类，这个指针的用途用于记录父亲节点的位置，方便后续进行操作。
插入操作的实现
进行插入操作时，我们知道AVL树的左右子树的平衡因子的绝对值是不超过1的，当我们进行插入的过程中，可能出现插入这个节点后，这棵树中的某个节点的平衡因子的绝对值超过了1，这是后我们是不能继续进行插入的，而是需要对这棵树尽心调整，使其满足AVL树的特性（每个节点的平衡因子的绝对值不超过1），调整使得这棵树满足AVL树后才能继续进行插入操作。
如上图所示当进行差如10这个节点时，它的父节点，父节点的父节点.....一直到根节点，整条路径的平衡因子的值都会发生改变，所以进行插入时，需要根据这条链中的平衡因子进行判断（通过循环的形式进行解决）
是否进行调整的条件判断情况
- 情况一：
进行插入完成后，插入节点的父亲节点的平衡因子变成0，此时是不需要进行调整的，插入节点的父亲节点的平衡因子变成0，意味着没有插入这个节点的时候，这个节点的平衡因子是1或者-1，这个节点已经有了一个孩子节点，是在另一个空孩子节点位置插入的这个新节点，是没有改变父亲及到根节点这条链上的子树高度的，只有父亲节点的平衡因子发生改变，这条链上的其他节点的平衡因子是没有发生变化的。
ps:这里就解释了为什么当时在定义节点类时通过三叉链的方式进行定义，这里是需要频繁进行寻找节点的父亲节点的。
- 情况二：
当进行插入一个新节点后，它的父节点的平衡因子变成了1或-1，证明新节点的父节点在没有插入这个新节点时，平衡因子的值为0，插入新节点后父亲节点的平衡因子的绝对值变成了1，证明由于新节点的插入其所在的这条链的各个父节点的平衡因子都发生了变化。这里需要通过循环的方式进行遍历这条链的父节点，依次进行平衡因子的判断，如果出现平衡因子大于1（这里的大于1，其实就是平衡因子等于2的节点），则需要对于这个节点尽心调整。
- 情况三：
当进行插入一个新节点后，其父亲节点直接变成2或-2，立刻进行旋转调整
优化的搜索二叉树的代码实现
AVL树的验证
验证AVL树的高度
验证AVL树的是否为AVL树
验证搜索二叉树是否为AVL树的逻辑是首先是根据AVL树定义来看，看每个节点的左右子树的高度差是否超过２，若超过２则AVL树的结构出现问题；我们是根据平衡因子进行调整的，在进行搜索二叉树调整为AVL树的过程中都是进行旋转进行的，进行旋转后需要进行平衡因子的更新，还需要验证节点的平衡因子的问题。
测试用例
必须通过大量随机数的插入，AVL树的结构不出现问题，才能说明AVL树的结构没有问题，AVL_test1()只能证明基本的旋转没有问题，有可能会出现平衡因子的更新错误。
整体代码
