概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
因此，两位苏联的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
这里是在每个结点加入了一个平衡因子，这个平衡因子是通过右子树和左子树的高度差算出来的。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
右子树高度-左子树高度=平衡因子
这棵树是平衡的，也就是说时间复杂度为logN，效率非常高。
节点定义
对于AVL树结点的定义，不仅仅多了一个平衡因子，还多了一个父节点的指针，是一个三叉链的结构。
template<class T,class V> struct AVLTreeNode//AVL树结点 { AVLTreeNode(const pair<T, V>& data) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) ,_factor(0)//刚创建的结点平衡因子是0，因为平衡因子只受子树影响 { } AVLTreeNode* _left;//左子树结点 AVLTreeNode* _right;//右子树结点 AVLTreeNode* _parent;//父节结点 pair<T, V> _data;//结点的值，KV模型 int _factor;//平衡因子 };
插入
我们这里只研究插入即可。
插入首先要按照平衡二叉树那样找到对应的位置。
然后将他们链接起来。
连接起来之后还要更新平衡因子。
这里平衡因子已经是2或者-2了，没必要进行平衡因子的更新了。
这里就是最坏的情况了，可能需要更新到初始的根结点。
这里更改平衡因子其实就要用到parent结点了，这就是为什么需要一个_parent的指针了。
template<class T, class V> class AVLTree//AVL树 { typedef AVLTreeNode<T, V> Node; public: bool Insert(const pair<T, V>& x) { if (_root == nullptr) { _root = new Node(x); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_data.first > x.first) { parent = cur; cur = cur->_left; } else if(cur->_data.first < x.first) { parent = cur; cur = cur->_right; } else { return false; } } cur = new Node(x); if (parent->_data.first > cur->_data.first) { parent->_left = cur; cur->_parent = parent; } else { parent->_right = cur; cur->_parent = parent; } //这里调节平衡因子 while (parent)//如果parent为空就说明到了初始根结点 { if (parent->_left == cur) { parent->_factor--;//如果是父节点的左子树插入了新节点就-- } else if (parent->_right == cur) { parent->_factor++; //如果是父节点的右子树插入了新节点就++ } //旋转 if (parent->_factor == 0)//这里要判断parent结点是不是0，是0就说明不需要向上调整 { break; } else if (parent->_factor == 1 || parent->_factor == -1)//这里就需要向上调整平衡因子了 { cur = parent; parent = parent->_parent; } else if (parent->_factor == 2 || parent->_factor == -2)//这里就需要去旋转了 { if (parent->_factor == 2 && cur->_factor == 1) { RotateL(parent); } else if (parent->_factor == -2 && cur->_factor == -1) { RotateR(parent); } else if (parent->_factor == 2 && cur->_factor == -1) { RotateRL(parent); } else if (parent->_factor == -2 && cur->_factor == 1) { RotateLR(parent); } else//以防万一 { assert(false); } break; } else//以防万一 { assert(false); } } return true; } private: void _Inorder(Node* _root) { if (_root == nullptr) return; _Inorder(_root->_left); cout << _root->_data.first << ":" << _root->_data.second << endl; _Inorder(_root->_right); } Node* _root = nullptr;//AVL树的根节点 };
旋转
旋转的目的；
1.让这棵树的左右树高度差不超过1
2.旋转之后也要保持这棵树是AVL树
3.更新调节平衡因子
4.旋转后的高度要和插入前相同
左单旋与右单旋
左单旋：
对于左单旋这张图针对的是很多种情况，下面我用三种情况举例子。
在60结点插入，无论是左边还是右边都会让30结点的平衡因子变成2，都会发生旋转。
无论在60结点的左子树的子树插入还是右子树的子树插入，都会影响30的平衡因子，都会引发旋转。
其实这三种情况我们能看出来，旋转的核心就是：
30结点变成60结点的左子树，原本60结点的左子树内容变成了30结点的右子树。
这里要注意，30不一定是根，有可能是局部的一个子树而已，所以需要储存30结点之前的结点，之后让30的父节点指向60，或者是根指向60。
那么如何实现代码呢？储存30的父节点，储存30结点的右子树和30结点的右子树的左子树。
void RotateL(Node* parent)//左单旋 { Node* pparent = parent->_parent;//30的父节点 Node* subR = parent->_right;//60结点 Node* subRL = subR->_left;//60结点的左子树 parent->_right = subRL;//让30结点的右指针指向60结点的左子树 if (subRL)//60的左子树如果为空就不能访问 subRL->_parent = parent; subR->_left = parent;//让60结点的左指针指向30结点 parent->_parent = subR; if (pparent)//让30的结点父节点指向60结点 { if (pparent->_left == parent) pparent->_left = subR; else pparent->_right = subR; } else { _root = subR; } subR->_parent = pparent;//让60的结点与父节点链接 parent->_factor = subR->_factor = 0;//调节平衡因子 }
右单旋：
void RotateR(Node* parent)//右单旋 { Node* pparent = parent->_parent; Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; parent->_parent = subL; if (pparent) { if (pparent->_left == parent) pparent->_left = subL; else pparent->_right = subL; } else { _root = subL; } subL->_parent = pparent; subL->_factor = parent->_factor = 0; }
双旋转
右左
如果是这种情况怎么办呢？
上面的左单旋和右单旋已经行不通了。
其实只要先对3结点右单旋一次在对1结点左单旋一次就可以了。
这里难处理的不是过程，因为上面已经写过了，难处理的是平衡因子：
观察插入后的和最终结果的两个平衡因子，60结点的右子树给了90结点的左子树，60结点的左子树给了30结点的右子树。所以平衡因子也就能算出来了。
void RotateRL(Node* parent)//右左 { Node* subR = parent->_right; Node* subRL = subR->_left; int fb = subRL->_factor;//判断60结点哪边长 RotateR(parent->_right); RotateL(parent); if (fb == 1)//新插入的地方是在60结点的右 { subR->_factor = 0; subRL->_factor = 0; parent->_factor = -1; } else if (fb == -1)//新插入的地方是在60结点的左 { subR->_factor = 1; subRL->_factor = 0; parent->_factor = 0; } else//60结点是新插入的结点 { subR->_factor = 0; subRL->_factor = 0; parent->_factor = 0; } }
左右
void RotateLR(Node* parent)//左右 { Node* subL = parent->_left; Node* subLR = subL->_right; int fb = subLR->_factor; RotateL(parent->_left); RotateR(parent); if (fb == 1) { subL->_factor = -1; subLR->_factor = 0; parent->_factor = 0; } else if (fb == -1) { subL->_factor = 0; subLR->_factor = 0; parent->_factor = 1; } else { subL->_factor = 0; subLR->_factor = 0; parent->_factor = 0; } }
总结：
假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑
- pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
当pSubR的平衡因子为1时，执行左单旋
当pSubR的平衡因子为-1时，执行右左双旋 - pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
当pSubL的平衡因子为-1是，执行右单旋
当pSubL的平衡因子为1时，执行左右双旋
旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。
验证AVL树
这里还需要加一个平衡因子的判断；
int _Height(Node* root)//计算树的高度 { if (root == nullptr) return 0; int l = _Height(root->_left); int r = _Height(root->_right); return l > r ? l + 1 : r + 1;//返回左子树和右子树最高高度 } bool _IsBalanceTree(Node* root) { if (root == nullptr)//空树也是AVL树 return true; int L = _Height(root->_left); int R = _Height(root->_right); int diff = R - L;//右减去左的高度 if (diff != root->_factor || (diff > 1 || diff < -1))//检查这个结点的左右子树差是否合法 { cout << root->_data.first << ":" << "平衡因子异常" << ":" << root->_factor << endl; return false; } return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);//整棵树的每个节点都要检查 }
然后用两个测试用例试一下：
{16, 3, 7, 11, 9, 26, 18, 14, 15}
{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}
删除（了解）
其实删除就是类似于插入的流程，只不过更复杂了一些，需要逆向思维去推理。
假如删除9结点，对于8结点来说就要减减，删除左边就是加加。
这里8的结点平衡因子就是0了，这说明高度变了，所以需要继续往上调整平衡因子。
如果是删除6结点，那么也是四种旋转的方式。
如果是删除7结点，那就是替换法。
