概念

在之前介绍了搜索二叉树，但是当我们插入的数据若是有序或者接近于有序，那么此时查找的效率底下，于是俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，是二叉树更加平衡，从而减少平均搜索长度。

AVL树的性质

1. 它的左右子树都是AVL树
2. 左右子树的高度之差的绝对值不超过1(-1/0/1)(高度之差简称为平衡因
   

AVL树实现

在AVL树的实现这里我们只来实现一下它的插入，我们采用记录平衡因子的方式来定义完成AVL树的实现。
我们先来定义它的节点

template
struct AVLTreeNode
{AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;pair _kv;int _bf;//平衡因子  balance factorAVLTreeNode(const pair& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};

这里的_bf我们当作这个节点的平衡因子，我们默认这里的平衡因子为右子树的高度减去左子树的高度。
在我们插入之前，我们首先要遵循搜索树的规则，找到空的位置

bool Insert(const pair& kv){if (_root == nullptr){_root = new Node(KV);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){cur->_parent = parent;parent->_right = cur;}else{cur->_parent = parent;parent->_left = cur;}}

在找到位置之后我们需要去更新平衡因子，这里有五种情况

1. 插入的cur的位置为parent的右边的时，此时右子树的高度加一，那么parent->_bt++;
2. 插入的cur的位置为parent的左边的时，此时右子树的高度加一，那么parent->_bt–;
3. 更新以后，parent的平衡因子要是是0，那么更新结束，因为插入一个节点之后这个节点的_bf变为了0，代表这个新增的节点一定是插入在高度小的那边的，因此parent的所在的子树高度不变。
4. 更新以后，parent的平衡因子要是是1或者-1，那么继续向上更新，因为插入一个节点前parent->_bf就是0，那么parent的高度变化了，因此parent的父亲的平衡因子也肯定要变化。
5. 更新之后，parent->_bt==-2/2,parent已经不平衡了，需要进行旋转处理

旋转

右单旋

新节点插入较高左子树的左侧—左左

代码实现

void RotateR(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right;parent->_left = SubLR;//此时SubLR可能为空if (SubLR){SubLR->_parent = parent;}Node* parentparent = parent->_parent;SubL->_right = parent;parent->_parent = SubL;if (parent == _root){_root = SubL;SubL->_parent = nullptr;}else{if (parent == parentparent->_left){parentparent->_left = SubL;SubL->_parent = parentparent;}else{parentparent->_right = SubL;SubL->_parent = parentparent;}}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;}Node* parentparent = parent->_parent;SubR->_left = parent;parent->_parent = SubR;if (parent == _root){_root = SubR;SubR->_parent = nullptr;}else{if (parent == parentparent->_left){parentparent->_left = SubR;}else{parentparent->_right = SubR;}SubR->_parent = parentparent;}SubRL->_bf = SubR->_bf = 0;}

左右双旋

新节点插入较高左子树的右侧—左右

代码实现

void RotateLR(Node* parent){RotateL(parent->_left);RotateR(parent);}

右左双旋

新节点插入较高右子树的左侧—右左

代码实现

void RotateRL(Node* parent){RotateR(parent->_right);RotateL(parent);}

双旋平衡因子更正

上面的就是针对于插入导致树不平衡之后对其节点进行旋转的处理，那么针对于双旋，我们都是举例插在C的位置，那么当h要是等于0和h等于一的时候插入在b/c不同的位置，又需要对平衡因子进行更正

左右双旋

针对于以上三种情况，我们要对平衡因子进行处理

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 = 1;Subl->_bf = 0;SubLR->_bf = 0;}else if (bf == 1){parent->_bf = 0;Subl->_bf = -1;SubLR->_bf = 0}else if (bf == 0){parent->_bf = Subl->_bf = 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 = SubR->_bf = SubRL->_bf = 0;}else{assert(false);}}

完整代码

#pragma once
#include
template
struct AVLTreeNode
{AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;pair _kv;int _bf;//平衡因子  balance factorAVLTreeNode(const pair& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};template
class AVLTree
{typedef AVLTreeNode Node;
public:AVLTree():_root(nullptr){}bool Insert(const pair& kv){if (_root == nullptr){_root = new Node(KV);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){cur->_parent = parent;parent->_right = cur;}else{cur->_parent = parent;parent->_left = cur;}//接下来需要控制平衡while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0)//平衡因子等于0的时候就说明这里插入的位置是正确的，直接跳出{break;}//平衡因子等于1或-1的时候，此时需要向上调整else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}//平衡因子等于2或-2的时候，此时需要旋转处理else if (parent->_bf == 2 || parent->_bf == -2){//右单旋if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}//左单旋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);}else{assert(false);}}else{//当走到这里的时候就说明原本的树就有问题,直接报错assert(false);}}return true;}//右单旋void RotateR(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right;parent->_left = SubLR;//此时SubLR可能为空if (SubLR){SubLR->_parent = parent;}Node* parentparent = parent->_parent;SubL->_right = parent;parent->_parent = SubL;if (parent == _root){_root = SubL;SubL->_parent = nullptr;}else{if (parent == parentparent->_left){parentparent->_left = SubL;SubL->_parent = parentparent;}else{parentparent->_right = SubL;SubL->_parent = parentparent;}}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;}Node* parentparent = parent->_parent;SubR->_left = parent;parent->_parent = SubR;if (parent == _root){_root = SubR;SubR->_parent = nullptr;}else{if (parent == parentparent->_left){parentparent->_left = SubR;}else{parentparent->_right = SubR;}SubR->_parent = parentparent;}SubRL->_bf = SubR->_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 = 1;Subl->_bf = 0;SubLR->_bf = 0;}else if (bf == 1){parent->_bf = 0;Subl->_bf = -1;SubLR->_bf = 0}else if (bf == 0){parent->_bf = Subl->_bf = 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 = SubR->_bf = SubRL->_bf = 0;}else{assert(false);}}private:Node* _root;
};