数据结构 —

1. AVL的概念

2.AVL树的结构

3.AVL树的插入

3.1 平衡因子更新

4. 旋转

4.1 旋转的原则

4.2 右单旋

4.2.1 右单旋代码实现

4.3 左单旋

4.3.1 左单旋代码实现

4.4 左右双旋

4.4.1 左右双旋代码实现

4.5 右左双旋

编辑 4.5.1 右左双旋代码实现

5. AVL树的判断

6. AVL树的查找

1. AVL的概念

1. AVL树是最先发明的⾃平衡⼆叉查找树，AVL是⼀颗空树或者具备下列性质的⼆叉搜索树：它的左右⼦树都是AV树，且左右⼦树的⾼度差的绝对值不超过1

2. AVL树是⼀颗⾼度平衡搜索⼆叉树，通过控制⾼度差去控制平衡

3. AVL树实现这⾥我们引⼊⼀个平衡因⼦(balance factor)的概念：每个结点都有⼀个平衡因⼦，任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度，也就是说任何结点的平衡因⼦等于0/1/-1

AVL树并不是必须要平衡因⼦，但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡，就像⼀个⻛向标⼀样

4. AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在 logN ，那么增删查改的效率也可以控制在 O(logN) ，相⽐⼆叉搜索树有了本质的提升

5. 为什么AVL树是⾼度平衡搜索⼆叉树，要求⾼度差不超过1，⽽不是⾼度差是0呢？因为有些情况是做不到⾼度差是0的

比如⼀棵树是2个结点，4个结点等情况下，⾼度差最好就是1，⽆法作为⾼度差是0

2.AVL树的结构

//节点
template<class K, class V>
struct AVLTreeNode
{//需要parent指针，后续更新平衡因?可以看到 pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;//加上一个_parent构成三叉列int _bf; // balance factor 平衡因子AVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};//整棵树
template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:
private:Node* _root = nullptr;
};

3.AVL树的插入

1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊

2. 新增结点以后，只会影响祖先结点的⾼度，也就是可能会影响部分祖先结点的平衡因⼦，所以更新从新增结点->根结点路径上的平衡因⼦，实际中最坏情况下要更新到根，有些情况更新到中间就可以停⽌了（更新平衡因子）

3. 更新平衡因⼦过程中没有出现问题，则插⼊结束（所有的平衡因子绝对值都是小于2的，新增节点的平衡因子一定是0，因为新增的左右孩子都为空）

4. 更新平衡因⼦过程中出现不平衡，对不平衡⼦树进行旋转，旋转后本质调平衡的同时，本质降低了⼦树的⾼度，不会再影响上⼀层，所以插⼊结束

//按二叉搜索树规则进行插入
bool Insert(const pair<K, V>& 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->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}//链接父节点cur->_parent = parent;return true;
}

3.1 平衡因子更新

更新原则：

1. 平衡因⼦ = 右⼦树⾼度-左⼦树⾼度（左 - 右也可以）

2. 只有⼦树⾼度变化才会影响当前结点平衡因⼦

3. 插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在parent的左⼦树，parent平衡因⼦--

4. 是否会继续往上更新取决于parent所在⼦树的⾼度是否变化

更新停⽌条件：


1. 更新后parent的平衡因⼦等于0，更新中parent的平衡因⼦变化为-1->0 或者 1->0，说明更新前parent⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后parent所在的⼦树⾼度不变，不会影响parent的⽗亲结点的平衡因⼦，更新结束


2. 更新后parent的平衡因⼦等于1 或 -1，更新前更新中parent的平衡因⼦变化为0->1 或者 0->-1，说明更新前parent⼦树两边⼀样⾼，新增的插⼊结点后，parent所在的⼦树⼀边⾼⼀边低，parent所在的⼦树符合平衡要求，但是⾼度增加了1，会影响arent的⽗亲结点的平衡因⼦，所以要继续向上更新

3. 更新后parent的平衡因⼦等于2 或 -2，更新前更新中parent的平衡因⼦变化为1->2 或者 -1->-2，说明更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理



旋转的⽬标有两个：

                                1、把parent⼦树旋转平衡

                                2、降低parent⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新，插⼊结束

//如果更新后的parent平衡因子为0，那么就不更新
if (parent->_bf == 0)
{break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{//如果更新后的parent平衡因子为1/-1，那么就继续向上更新cur = parent;parent = parent->parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{//如果更新后的parent平衡因子为2/-2，那么就不符合平衡要求，需要继续旋转// 旋转break;
}
else
{//如果更新之后的平衡因子不为上面三种情况中的其中一种assert(false);
}

1. 更新到10结点，平衡因⼦为2，10所在的⼦树已经不平衡，需要旋转处理

2. 更新到中间结点，3为根的⼦树⾼度不变，不会影响上⼀层，更新结束

3. 最坏更新到根停⽌

4. 旋转

4.1 旋转的原则

1. 保持搜索树的规则

2. 让旋转的树从不平衡变平衡

3. 降低旋转树的高度，也就是恢复成插入之前的高度

旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋

4.2 右单旋

1. 本图1展⽰的是10为根的树，有a/b/c抽象为三棵⾼度为h的⼦树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树，是⼀种概括抽象表⽰，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体图2/图3/图4/图5进⾏了详细描述

2. 在a⼦树中插⼊⼀个新结点，导致a⼦树的⾼度从h变成h+1，不断向上更新平衡因⼦，导致10的平衡因⼦从-1变成-2，10为根的树左右⾼度差超过1，违反平衡规则。10为根的树左边太⾼了，需要往右边旋转，控制两棵树的平衡

3. 旋转核⼼步骤，因为5 < b⼦树的值 < 10，将b变成10的左⼦树，10变成5的右⼦树，5变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的⾼度恢复到了插⼊之前的h+2，符合旋转原则。如果插⼊之前10整棵树的⼀个局部⼦树，旋转后不会再影响上⼀层，插⼊结束了

图1

图2

图3

图4

图5

4.2.1 右单旋代码实现

下图的根节点的平衡因子为-2，即左子树深度过深，需要将左子树旋转，我们将根节点命名为parent，根节点的左节点命名为subL，parent的左孩子的右孩子命名为subLR，我们先将subLR接入parent的左节点，然后判断subLR是否为空，不为空就把subLR的父节点的指针指向parent，然后将subL调整为调整子树的根节点，最后更新平衡因子

//右单旋
void RotateR(Node* parent)
{//起始位置//subL是parent的左节点Node* subL = parent->_left;Node* subLR = subL->_right;//开始旋转//parent的左节点是subLRparent->_left = subLR;//如果subLR不为空  对subLR和parent的父节点进行更新if (subLR)subLR->_parent = parent;//subLR的父节点为parent//如果传入的根节点是一个子树的根节点则需要将旋转后的根节点重新接入原来的节点Node* pParent = parent->_parent;//subL作为新的根节点subL->_right = parent;parent->_parent = subL;//parent的根节点为subL//旋转的树可能是一个整棵树的子树，还需要和上一层进行链接//两种情况：1.parent之前就是根if (parent == _root){_root = subL;//subL作为新的根subL->_parent = nullptr;//subL为根，指向的parent置为空}else//不是根，那么就一定有parent的parent（pparent）{//判断之前parent是pparent的左还是右if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}//链接完之后将subL的Parent指向pParentsubL->_parent = pParent;}//更新平衡因子subL->_bf = 0;parent->_bf = 0;}

4.3 左单旋

1. 本图6展⽰的是10为根的树，有a/b/c抽象为三棵⾼度为h的⼦树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树，是⼀种概括抽象表⽰，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体跟上⾯左旋类似

2. 在a⼦树中插⼊⼀个新结点，导致a⼦树的⾼度从h变成h+1，不断向上更新平衡因⼦，导致10的平衡因⼦从1变成2，10为根的树左右⾼度差超过1，违反平衡规则。10为根的树右边太⾼了，需要往左边旋转，控制两棵树的平衡

3. 旋转核⼼步骤，因为10 < b⼦树的值 < 15，将b变成10的右⼦树，10变成15的左⼦树，15变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的⾼度恢复到了插⼊之前的h+2，符合旋转原则。如果插⼊之前10整棵树的⼀个局部⼦树，旋转后不会再影响上⼀层，插⼊结束了

图6

4.3.1 左单旋代码实现

左单旋和右单旋相反

//左单旋
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 (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}parent->_bf = subR->_bf = 0;
}

4.4 左右双旋

通过图7和图8可以看到，左边⾼时，如果插⼊位置不是在a⼦树，⽽是插⼊在b⼦树，b⼦树⾼度从h变成h+1，引发旋转，右单旋⽆法解决问题，右单旋后，我们的树依旧不平衡。右单旋解决的纯粹的左边⾼，但是插⼊在b⼦树中，10为跟的⼦树不再是单纯的左边⾼，对于10是左边⾼，但是对于5是右边⾼，需要⽤两次旋转才能解决，以5为旋转点进⾏⼀个左单旋，以10为旋转点进⾏⼀个右单旋，这棵树这棵树就平衡了

图7

图8

图7和图8分别为左右双旋中h==0和h==1具体场景分析，下⾯我们将a/b/c⼦树抽象为⾼度h的AVL⼦树进⾏分析，另外我们需要把b⼦树的细节进⼀步展开为8和左⼦树⾼度为h-1的e和f⼦树，因为我们要对b的⽗亲5为旋转点进⾏左单旋，左单旋需要动b树中的左⼦树。b⼦树中新增结点的位置不同，平衡因⼦更新的细节也不同，通过观察8的平衡因⼦不同，这⾥我们要分三个场景讨论

场景1：h >= 1时，新增结点插⼊在e⼦树，e⼦树⾼度从h-1并为h并不断更新8->5->10平衡因⼦，引发旋转，其中8的平衡因⼦为-1，旋转后8和5平衡因⼦为0，10平衡因⼦为1

场景2：h >= 1时，新增结点插⼊在f⼦树，f⼦树⾼度从h-1变为h并不断更新8->5->10平衡因⼦，引发旋转，其中8的平衡因⼦为1，旋转后8和10平衡因⼦为0，5平衡因⼦为-1

场景3：h == 0时，a/b/c都是空树，b⾃⼰就是⼀个新增结点，不断更新5->10平衡因⼦，引发旋转，其中8的平衡因⼦为0，旋转后8和10和5平衡因⼦均为0

和下面的图9结合看

图9

4.4.1 左右双旋代码实现

如果想区分上面的三种情况，只需要关注更新之后8这个节点的平衡因子，平衡因子更新之后是-1就是在e插入，是1就是在f插入，是0节点8自己就是新增

//左右双旋  先进行左旋再进行右旋
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;//双旋需要记录subLR的平衡因子int bf = subLR->_bf;//调用左右单旋RotateL(parent->_left);RotateR(parent);//按照图上的三种情况讨论 if (bf == -1)//如果节点8的平衡因子为-1（结合图看）{//旋转之后subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else//出现错误直接断言，避免调试{assert(false);}}

4.5 右左双旋

跟左右双旋类似，下⾯我们将a/b/c⼦树抽象为⾼度h的AVL⼦树进⾏分析，另外我们需要把b⼦树的细节进⼀步展开为12和左⼦树⾼度为h-1的e和f⼦树，因为我们要对b的⽗亲15为旋转点进⾏右单旋，右单旋需要动b树中的右⼦树。b⼦树中新增结点的位置不同，平衡因⼦更新的细节也不同，通过观察12的平衡因⼦不同，这⾥我们要分三个场景讨论

场景1：h >= 1时，新增结点插⼊在e⼦树，e⼦树⾼度从h-1变为h并不断更新12->15->10平衡因⼦，引发旋转，其中12的平衡因⼦为-1，旋转后10和12平衡因⼦为0，15平衡因⼦为1

场景2：h >= 1时，新增结点插⼊在f⼦树，f⼦树⾼度从h-1变为h并不断更新12->15->10平衡因⼦，引发旋转，其中12的平衡因⼦为1，旋转后15和12平衡因⼦为0，10平衡因⼦为-1

场景3：h == 0时，a/b/c都是空树，b⾃⼰就是⼀个新增结点，不断更新15->10平衡因⼦，引发旋转，其中12的平衡因⼦为0，旋转后10和12和15平衡因⼦均为0

4.5.1 右左双旋代码实现

//右左双旋
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else 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{assert(false);}
}

5. AVL树的判断

int _Height(Node* root)
{if (root == nullptr){return 0;}int leftheight = _Height(root->_left);int rightheight = _Height(root->_right);return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}bool _IsAVLTree(Node* root)
{if (root == nullptr){return true;}int leftheight = _Heighr(root->_left);int rightheight = _Height(root->_right);int diff = rightheight - leftheight;if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}if (diff != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;}return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
}

6. AVL树的查找

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;
}

完结撒花~