平衡的二叉搜索树 —— AVL树
AVL树的引入 ：
在二叉搜索树插入的数据有序时，二叉搜索树会退化为单链，这时效率就由 （O（logN），降为了 O（N）），为了保证效率。
G.M. Adelson-Velsky和E.M. Landis在1962年发明，通过把树旋转使得二叉搜索树每个左右子树高度差不超过1 ， 就平衡了树的高度保证了O（logN）的效率
AVL树的性质 ：
1. AVL树每个左右子树高度差不超过1
2. 每个节点都有一个平衡因子，该平衡因子定义为左子树高度减去右子树高度。对于AVL树中的每一个节点，其平衡因子只能是-1, 0, 或者 1。
3. 自平衡机制：当向AVL树中插入或删除节点后，如果树失去了平衡，即某个节点的平衡因子不再是-1, 0, 或1，则通过一系列旋转操作来恢复平衡。
AVL树的旋转介绍（主要以插入为例）：
我们引入平衡因子，和三叉链（作用是维护平衡因子）去实现 AVL树
AVLTree的insert：
前面的步骤跟二叉搜索树的插入没啥区别（就是双指针法），主要是如何更新平衡因子
如果平衡因子等于2，则要开始旋转树了
更新平衡因子 ：
因为平衡因子是右子树高度减去左子树高度，所以有一个非常重要的规则
1. 插入的是右边，那么右子树高度+1，平衡因子+1
2. 插入的是左边，那么左子树高度+1，平衡因子 - 1
如图，插入在8的左边，所以 8 的平衡因子 = 1 - 1 = 0
插入在9的右边，所以9的平衡因子 = 0 + 1 = 1；
在插入后，改节点的1因子有 3 种情况 即 = 0 ， = +-1 ，= +-2；
分类讨论了 ：
1 . 插入后等于0，说明整棵树的高度没有变化，这次的插入就是补了同高度一个的空位
插入成功
2.插入后等于 +-1 ， 说明整棵树的高度变化了，要算祖先的平衡因子（插入只影响祖先的平衡因子）
这时，9的平衡因子等于 1 ， 我们去判断 8的平衡因子， 发现9是8的右孩子
（
1. 插入的是右边，那么右子树高度+1，平衡因子+1
2. 插入的是左边，那么左子树高度+1，平衡因子 - 1
）
这时 8 的平衡因子更新为 1 + 1 = 2 ;
这就不满足平衡搜索树了，开始旋转调整该树
左右旋转( 要会画图 ) ：
需要调整的为直线形时（一边高），就单旋转就可解决问题
一边高对于60来说是左边高，对于30来说是也是左边高。
通过左右旋转可以使这颗树的高度平衡
旋转的要求 ：
1. 保证旋转后还是一颗二叉搜索树
2. 平衡因子为2的节点要变为平衡
1.左单旋 ：
如图，subR大于parent , 大于b，所以他有资格当该子树的新根
把parent旋转下来连接到subR的右边，b链到parent的右边，subR做这颗子树的新根
这就实现了同时满足两个条件
2.右单旋 : 与左单转同理
如图 ： 30 小于b，小于60，有资格当他们的新根
把60旋转下来链接到30的右边，b链接60的左边，30作为这颗子树的新根
两次旋转 ：
当需要旋转的是折线形（不是一边高的情况），先要旋转一次让树达到一边高，然后就返回
上面笔记的情况。
对于90，是左边高，对于30是右边高，先左单旋到直线形（一边高），后右单旋
对于另一种方向同理解决 ， 先右单旋，后左单旋
平衡因子的调节： 因为单次旋转都能复用上面的，而插入在b或c最后的平衡因子结果是不一样的，
易错点 ：
1.这是3叉链，旋转时忘记调整父节点的关系
答： 没有调整父节点之间的关系
在旋转中， b，parent，subR的父亲都变了
2.忘记了subR要顶替parent当新子树的根
1. 如果 parent本来就是该树的根 ，那就让subR当新大根
2. 如果 parent本身是一颗子树的根，那么让subR当新的子树根
第一种情况就是 if语句里面的
第二种情况就是 else 语句里面的 （ppNode 是 parent的父亲）
关键就是看ppNode到底存不存在
AVL树的应用 ：
AVL树是绝对平衡，如果经常插入经常要进行旋转，旋转是有消耗的 ，所以STL map和set的底层其实是相对平衡的红黑树，红黑树我们会在后面介绍
由于AVL树要保证绝对平衡，所以在实际应用中，如果只是侧重查找可以用AVL树，如果要经常的增删，那么用相对平衡的空黑树
AVL树的实现代码（C++）：
1. 树节点的成员
使用三叉链 ， 维护左右孩子和父亲 ，_bf 维护平衡因子
2 . 右单旋转
注意好好维护平衡因子和parent
3. 左单旋转
注意好好维护平衡因子和parent
4 . 先左后右双旋
双旋可以复用单旋 ，一定要注意维护好平衡因子
4. 先右后左双旋
双旋可以复用单旋 ，一定要注意维护好平衡因子
