概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
因此，两位苏联的数学家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;elsepparent->_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;elsepparent->_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，分以下情况考虑

1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
   当pSubR的平衡因子为1时，执行左单旋
   当pSubR的平衡因子为-1时，执行右左双旋
2. 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结点，那就是替换法。