目录
1.前言
2.AVL树
3.AVL树的插入
平衡因子的更新
更新停止的条件
旋转
1.前言
在学习了二叉搜索树，set和map之后，我们接下来趁热打铁，继续学习AVL树。
2.AVL树
1.AVL树具有二叉搜索树的性质，但是它的左右子树的高度差不超过1.是一颗高度平衡的二叉搜索树。
2.AVL树中我们引入了平衡因子概念，它的大小等于右子树的高度减去左子树的高度，在AVL树中，任何节点的平衡因子只能为1，-1,0，不是这个值说明这颗树就该调整了，他就像一个风向标一样，告诉我们这颗树是否平衡。
3.思考一下，为什么AVL树的高度差不可以只为0呢？试想一下，如果这颗树只有2个节点，它无论如何根节点的平衡因子都达不到0.
4.AVL树是高度平衡的二叉搜索树，它的搜索效率可以稳定控制在logN,对比二叉搜索树在特殊情况下的N方，有了质的提升。
3.AVL树的插入
1.他按照二叉搜索树的插入规则进行插入。
2.新增节点以后，只会影响祖先节点的平衡因子，所以需要更新祖先的平衡因子。
3.平衡因子未出问题，则插入结束，如果超出了1,-1,0的范围，就需要旋转来平衡树。
平衡因子的更新
1.平衡因子=左子树-右子树。
2.子树高度变化才会影响平衡因子。
3.插入右节点，平衡因子++，插入左节点，平衡因子--。
4.parent所在子树高度是否变化决定了是否向上更新。
更新停止的条件
1.更新后parent平衡因子为0，说明是由1或者-1变化而来。高度不变，平衡因子结束更新。雪中送炭。
2.更新后平衡因子为1或-1，说明原来是0，插入一个节点变为该值，影响了树的高度，需要向上更新。
3.更新后平衡因子为-2或2，更新前parent的平衡因子是1或-1，在高的一侧又再次插入节点变为2或-2，需要旋转处理。
4.不断更新，更新到根，根的平衡因子为0或-1停止了。
旋转
旋转的原则:1.保持搜索树的规则。2.让旋转的树从不满足变平衡，降低树的高度。
旋转由左旋，右旋，左右旋，右左旋。
由于内容比较多我们先介绍这么多，代码实现和旋转代码等下一篇博客再介绍。