AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单枝树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种方法：当二叉树搜索树中插入新节点后，如果能保证每个系欸但的左右子树的高度之差的绝对值不超过1，也就是说要降低树的高度，从而减少平均搜索长度。

一棵AVL树，它具有以下的性质：

它的左右子树都是AVL树
左右子树高度之差的绝对值不超过1

如果一棵搜索二叉树的高度是平衡的，它就是AVL树。如果它有n个结点，其高度可保持在log2(n)，搜索时间复杂度log2(n)。

AVL树结点的定义

struct AVLTreeNode
{AVLTreeNode<K, V>* _left;//左孩子AVLTreeNode<K, V>* _right;//右孩子AVLTreeNode<K, V>* _parent;//父节点std::pair<K, V> _kv;//键值对int _bf;//平衡因子AVLTreeNode(const std::pair<K, V>& kv) : _left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};

这里定义了对AVL树的结点的描述，一个结点应当有左右孩子结点，父节点，键值对，以及平衡因子。
左右孩子结点和键值对是基于搜索二叉树（AVL树是在搜索二叉树的基础上建立的）。
平衡因子用来衡量这颗树是否是平衡的。
平衡因子=右子树高度-左子树高度
至于父节点，则是未来方便平衡因子的更新而添加进去的。

AVL树的插入

AVL树是在搜索二叉树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。所以，插入的过程可以分为两步：

按照搜索二叉树的方式插入新节点
调整结点的平衡因子

bool Insert(const std::pair<K,V>&kv)
{Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{//已经存在结点了，插入失败return false;}}cur = new Node(kv);//可能是根节点if (parent == nullptr){_root = cur;return true;}if (parent->_kv.first < kv.first){parent->_right = cur;}elseparent->_left = cur;cur->_parent = parent;return true;
}

按照搜索二叉树的规则，查找到我们需要插入的地方。

插入的键比当前结点的键小，递归左子树
插入的键比当前节点的键大，递归右子树
插入的键等于当前节点的键，说明已经插入过了，本次插入是失败的
然后开始new一个新的结点，把结点之前的父子关系处理好

AVL树的调整（旋转）

如果在一棵原本是平衡的AVL树中插入一个新的结点，可能会造成不平衡的情况，此时就必须要调整A树的结构，使其平衡话。AVL树的旋转大致分为四种，这里采用画图的方式来理解这四种旋转的方式：

左左：右单旋

在这里插入图片描述

右右：左单旋

在这里插入图片描述

左右：先左旋，后右旋

在这里插入图片描述
这里的插入情况不唯一，但是值得一提的是
在调整之后，subLR的左子树一定是充当subL的右子树，subLR的右子树一定是充当了parent的左子树，可以根据这个来计算平衡因子

右左：先右旋，后左旋

在这里插入图片描述
同左右情况，这里也有相似的结论：
再调整之后，subRL的左子树充当为parent的右子树，subRL的右子树充当为subR的左子树

AVL树的完整实现代码

#include <iostream>
#include <cassert>template <class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;std::pair<K, V> _kv;int _bf;//平衡因子AVLTreeNode(const std::pair<K, V>& kv) : _left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};template <class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;public:bool Insert(const std::pair<K,V>&kv){Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent == nullptr){_root = cur;return true;}if (parent->_kv.first < kv.first){parent->_right = cur;}elseparent->_left = cur;cur->_parent = parent;//更新平衡因子while (parent){if (cur == parent->_left)parent->_bf--;elseparent->_bf++;if (parent->_bf==0)break;else if (parent->_bf == 1 || parent->_bf == -1){//说明之前是0，需要继续向上更新cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//这里需要进行旋转平衡if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}break;}else {//理论上不可能出现这种情况assert(false);}}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}void InOrder(){_InOrder(_root);}//右旋转void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;//整棵树的根节点if (parent == _root){_root = subL;_root->_parent = nullptr;}//某个子树的根节点else{subL->_parent = ppNode;if (ppNode->_left == parent){ppNode->_left = subL;}else {ppNode->_right = subL;}}parent->_bf = subL->_bf = 0;}//左单旋void RotateL(Node*parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else {subR->_parent = ppNode;if (parent == ppNode->_left){ppNode->_left = subR;}else {ppNode->_right = subR;}}parent->_bf = subR->_bf = 0;}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1){//说明是在subLR的左边插入subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){//说明是在subLR的右边插入subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else if (bf == 0) {subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else{assert(false);}}bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}
private:bool _IsBalance(Node*node){if (node == nullptr)return true;int leftHeight = _Height(node->_left);int rightHeight = _Height(node->_right);if (abs(leftHeight - rightHeight) >= 2)return false;//检查一下平衡因子是否是正确的if (rightHeight - leftHeight != node->_bf){std::cout << node->_kv.first << std::endl;return false;}return _IsBalance(node->_left) &&_IsBalance(node->_right);}int _Height(Node* node){if (node == nullptr)return 0;return std::max(_Height(node->_left), _Height(node->_right)) + 1;}void _InOrder(Node* node){//中序遍历if (node == nullptr)return;_InOrder(node->_left);std::cout << node->_kv.first << ": " << node->_kv.second << std::endl;_InOrder(node->_right);}
private:Node* _root = nullptr; // 根节点
};