下面我们再看h==1的情况：
h==1有两种情况，要不在60的左树插入，要不在60的右树插入，不同的是如果插入在60的左树那么parent的平衡因子会变成1，其他两个节点的平衡因子还是0.当插入的节点在60的右边，那么只有subL的平衡因子变成-1,其他的平衡因子变成0，下面我们写先左旋再右旋的代码：
void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); if (bf == 1) { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else if (bf == -1) { parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else if (bf == 0) { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } else { assert(false); } }
首先我们要记住，要满足先左旋再右旋的条件，一定是这棵树或者这颗子树的整体高度是左边高度高，并且左边的第一个节点的右边高度高，因为我们先左旋就是将这个左边第一个节点的右边左旋（因为右边高度高），这个时候整体都变成了纯粹的左边高，如果是纯粹的左边高我们再使用右旋，所以这就是先左旋再右旋的由来。条件一定是：parent的平衡因子为-2（代表整体左边高），cur的平衡因子为1（代表左边的第一个节点右边高度高）。首先我们保存parent的左边节点也就是subL,然后保存这个左边节点的右边节点subLR,并且我们要记录这个subLR的平衡因子，因为我们前面说过只有这个位置插入才会发生旋转，并且插入到这个位置的左树还是右树后面的平衡因子都是不一样的，所以我们先保存这个节点的平衡因子，先左旋parent的左边节点后，再整体右旋，然后判断（用平衡因子判断）新增的节点在subLR的左边还是右边，如果为1说明在右边，我们要将平衡因子更新，这里要对照着图，发现subL的平衡因子变成-1，如果为-1说明在左边parent的平衡因子变成1，如果等于0说明自己就是新增的节点，然后我们的先左旋再右旋就结束了。
下面是先右旋再左旋：
同样我们先以h==0为例，如果h==0那么60就是新增的节点，这个时候旋转完后subRL,subR和parent的平衡因子都为0.
当h==1同样有两种，其实也就是从b插入或者从c插入，在这两个位置都会引发双旋，只不过现在h==1无b,c这两个位置而已，在60的左边插入和60的右边插入结果都是不一样的，下面我们直接看代码：
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); if (bf == 1) { parent->_bf = -1; subR->_bf = 0; subRL->_bf = 0; } else if (bf == -1) { parent->_bf = 0; subR->_bf = 1; subRL->_bf = 0; } else if (bf == 0) { parent->_bf = 0; subR->_bf = 0; subRL->_bf = 0; } else { assert(false); } }
与先左旋再右旋不一样的地方在于平衡因子的要选择的节点，因为要满足先右旋再左旋的条件，所以这棵树一定是整体右边高度高，右边的第一个节点左边高度高，也就是parent的平衡因子为2（说明整体右边高）并且cur的平衡因子为-1（说明右边第一个节点的左边高度高）。我们保存右边第一个节点和右边第一个节点的左边节点，然后保存subRL的平衡因子，然后先右旋parent的右边节点，然后整体左旋。旋转完毕后继续更新平衡因子即可。所有的else我们都用assert报错，因为有可能一棵树一开始的平衡因子就有问题。当我们旋转完成这棵树一定是高度降低并且平衡了，所以我们直接退出循环返回true即可。
以上就是AVL树的插入，除了erase接口其他接口都与搜索二叉树一样，下面我们将代码测试一下：
namespace AVLTreeK { template<class K> struct AVLTreeNode { AVLTreeNode<K>* _left; AVLTreeNode<K>* _right; AVLTreeNode<K>* _parent; K _kv; int _bf; AVLTreeNode(const K& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _bf(0) { } }; template<class K> class AVLTree { typedef AVLTreeNode<K> Node; public: void Inorder() { _Inorder(_root); } void _Inorder(Node* root) { if (root == nullptr) { return; } cout << root->_kv << " "; _Inorder(root->_left); _Inorder(root->_right); } bool insert(const K& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv < kv) { parent = cur; cur = cur->_right; } else if (cur->_kv > kv) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); if (parent->_kv < kv) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; //开始控制平衡因子 while (parent) { if (parent->_left == cur) { parent->_bf--; } else if (parent->_right == cur) { parent->_bf++; } if (parent->_bf == 0) { //已经平衡了 break; } else if (parent->_bf == 1 || parent->_bf == -1) { //需要继续向上调节 parent = parent->_parent; cur = cur->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { //需要旋转控制，旋转的目的是降低高度+平衡，所以旋转完毕后退出循环。 //首先是单纯右边高，需要左单旋 if (parent->_bf == 2 && cur->_bf == 1) { RotateL(parent); } //如果是单纯左边高，需要右单旋 else if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent); } //如果是整体左边高，并且左边的第一个节点的右子树高，就需要先左单旋，再右单旋 else if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent); } //如果整体右边高，但是右边第一个节点的左边高，就需要先右单旋，再左单旋 else if (parent->_bf == 2 && cur->_bf == -1) { RotateRL(parent); } else { assert(false); } //当任何一个旋转结束了当前树都会平衡，所以需要直接退出循环 break; } else { assert(false); } } return true; } private: void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; Node* ppnode = parent->_parent; parent->_right = subRL; if (subRL) { subRL->_parent = parent; } subR->_left = parent; parent->_parent = subR; if (ppnode == nullptr) { _root = subR; _root->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subR; } else { ppnode->_right = subR; } subR->_parent = ppnode; } parent->_bf = subR->_bf = 0; } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* ppnode = parent->_parent; parent->_left = subLR; if (subLR) { subLR->_parent = parent; } subL->_right = parent; parent->_parent = subL; if (ppnode == nullptr) { _root = subL; _root->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subL; } else { ppnode->_right = subL; } subL->_parent = ppnode; } parent->_bf = subL->_bf = 0; } void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); if (bf == 1) { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else if (bf == -1) { parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else if (bf == 0) { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } else { assert(false); } } void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); if (bf == 1) { parent->_bf = -1; subR->_bf = 0; subRL->_bf = 0; } else if (bf == -1) { parent->_bf = 0; subR->_bf = 1; subRL->_bf = 0; } else if (bf == 0) { parent->_bf = 0; subR->_bf = 0; subRL->_bf = 0; } else { assert(false); } } private: Node* _root = nullptr; }; }
测试的时候我们以K模型测试，下面是测试样例：
void test() { AVLTreeK::AVLTree<int> at; int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14 }; int b[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; for (auto& e : a) { at.insert(e); } at.Inorder(); }
我们自己画一个经过旋转后的图与前序遍历结果看是否一样：
我们可以看到答案是正确的，以上就是我们AVL树的所有内容了。
总结
AVL 树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过 1 ，这样可以保证查询时高效的时间复杂度，即O（logN） 。但是如果要对 AVL 树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的 ( 即不会改变 ) ，可以考虑 AVL 树，但一个结构经常修改，就不太适合。
