AVL树的介绍及实现

（一）AVL的概念

AVL树是一棵高度平衡的二叉搜索树，通过控制高度差去控制平衡。AVL可以是一棵空树，若不是空树则需要具备以下性质：

1. 它的任意一棵左右子树都是AVL树
2. 任何一棵左右子树的高度差的绝对值不超过1

这篇文章我将引入一个平衡因子来完成AVL树的实现。平衡因子的概念，每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，而且任何结点的平衡因子只能为0/1/-1，若不是则需要进行旋转操作。AVL树并不是必须要平衡因子，但有了它能让我们更好地去观察和控制树是否平衡

AVL树见下图：

AVL树可以说它的整体结点数量及分布和完全二叉树类似，因为AVL树缺结点的话，缺的也就在树的最后两层上面，所以AVL树的高度可以控制在logN，那么增删查改的效率就是O(logN)，相比二叉搜索树有了本质的提升

（二）AVL树的实现

1.AVL树的结构

AVL树的结构与二叉搜索树的结构类似，在这里就不介绍了，不理解的可以看博主二叉搜索树的那篇文章，结构如下代码：

template<class K,class v>
struct AVLTNode
{pair<k, v> _kv;AVLTNode<k, v>* _left;AVLTNode<k, v>* _right;AVLTNode<k, v>* _parent;//需要parent指针，后续用来更新平衡因子int _bf; //balance factor用于存储平衡因子AVLTNode(const pair<k,v>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){ }
};template<class k,class v>
class AVLTree
{typedef AVLTNode<k, v> Node;
public:private:Node* _root = nullptr;
};

2.AVL树的插入

AVL树插入一个值的大致步骤如下：

1. 首先，插入一个值要按照二叉搜索树的插入规则来进行插入，插值比当前结点小，往左走；插值比当前结点大，往右走，走当空位置时，说明找到了插值的结点位置

代码的解析在二叉搜索树的那篇文章中，下面博主就直接放代码了：

bool insert(const pair<k, v>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}else{Node* cur = _root;Node* parent = nullptr;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 > cur->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//使插入的结点与父结点进行连接，以便更新平衡因子//更新平衡因子//....return true;}
}

2. 插入完结点之后，更新平衡因子

当插入完一个结点之后，我们要如何判断插入之后，该树是否还保持平衡。可知，新增结点的平衡因子都为0，那新增结点之后会影响到哪些结点的平衡因子呢，来看下图：

如图，当插入11这个结点之后，影响了祖先结点的高度，就会影响全部祖先或者部分祖先的平衡因子，所以要更新从新增结点到根结点路径上的平衡因子，最坏的情况就是要更新平衡因子更新到根结点，如何判断是否需要更新到根结点的平衡因子，具体详解如下：

看上面的图，当新增结点11，新增在10的右边，结点10的高度就增加了1，而且增加在结点10 的右边，所以结点10的平衡因子就要++，因为平衡因子等于右子树的高度减左子树的高度，右子树的高度增加了1，那么就是平衡因子++，再继续看，新增的结点11对结点10的上一层也有影响，因为结点10的高度变了，变了就会对上一层有影响，那么结点10在结点8的右边，那么结点8的平衡因子也要++，新增节点也影响了结点8的高度，那么也会对根结点产生影响，根结点的平衡因子也要更新。

总结平衡因子更新原则：

• 平衡因子 = 右子树的高度 - 左子树的高度
• 只有子树高度变化才会影响当前结点平衡因子
• 插入结点，会增加高度，所以当新增结点在parent的右子树，那么parent的平衡因子++；若新增结点在parent的左子树，那么parent的平衡因子–
• parent所在子树高度是否变化决定了是否需要继续向上更新平衡因子

判断更新平衡因子停止的条件：

• 新增结点后，更新parent的平衡因子，若更新后平衡因子为1/-1，说明更新前到更新后parent的平衡因子的变化为0->1/0->-1，更新前parent的左右子树的高度相等，更新后变成了一高一低，parent所在的子树符合平衡的要求，但是高度增加了1，符合更新原则的最后一条规则，所以需要继续向上更新平衡因子
  
• 新增结点后，更新parent的平衡因子，若更新后平衡因子为2/-2，说明更新前到更新后的变化为1->2/-1->-2，更新前parent的左右子树的高度是一边高一边低的，新增结点插入到了高的那一边，导致高的那棵子树变得更高了，破坏了树的平衡，parent所在的子树不符合平衡要求，需要进行旋转操作来控制平衡，旋转的目标有两个：1.把parent子树旋转平衡 2.降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后不需要继续向上更新，更新结束，即插入结束（旋转操作，在下面有介绍）
  
• 新增结点后，更新parent的平衡因子，若更新后平衡因子为0，说明更新前到更新后的变化为1->0/-1->0，插入结点前parent左右子树的高度为一高一低，新插入的结点在parent低的那一边，左右子树的高度相等，使parent所在子树的高度不变，不会影响祖先结点的高度，停止更新，即插入结束

• 还有可能最坏的情况下一直更新到根结点，更完根结点的平衡因子之后，也结束了

实现代码如下：

//更新平衡因子
while (parent) //最坏情况下更新到根，若parent为空说明结束，因为只有根结点是没有父结点的
{if (parent->_right == cur){//若新增结点在父结点的右子树，那么平衡因子++parent->_bf++;}else{//若新增结点在父结点的左子树，那么平衡因子--parent->_bf--;}//判断是否需要继续向上更新平衡因子if (parent->_bf == 0){//若父结点平衡因子等于0，说明不影响祖先所在结点的高度，更新结束break;}else if (parent->_bf == 1 || parent->_bf == -1){//若父结点平衡因子等于1/-1，说明影响祖先所在结点的高度，继续更新cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//若父结点平衡因子等于2/-2，破坏平衡要求，旋转处理// 旋转操作，旋转之后停止更新break;}
}

3. 破坏了平衡要求后需要进行旋转处理，旋转详解如下

旋转的原则：

• 保持搜索树的规则
• 让旋转的树从不满足平衡到满足平衡，其次降低旋转树的高度

旋转分为：左单旋、右单旋、左右双旋、右左双旋

右单旋：
右单旋的情况有很多种，这里就通过抽象出来进行讲解，如下图：

当新增结点在a位置时，树的平衡遭到破坏，此时结点10的平衡因子变成了-2，就需要进行旋转处理，旋转步骤：以结点10为旋转点，由于b的范围在结点5到结点10之间，所以可以将b给结点10的左子树，再将结点10给结点5的右子树，该旋转过程就叫作右单旋。如下图：

新增结点可分为三种情况：

第一种，当h = 1时，新增在a的左子树，旋转示例如下：

第二种情况，当h = 1时，新增在a的右子树，旋转示例如下：

第三种情况，当h = 0 时，新增在a位置，旋转示例如下：

从这三种情况，我们可以看到，在进行右单旋后，parent结点和subL结点的平衡因子都为0，而且只有这两个结点发生变化，因为想要发生右单旋的情况，b结点和c结点是必须要共同出现或消失的，有c结点时，再将b结点给parent的左孩子，那么parent的平衡因子一定为0，反之平衡因子也为0；同样的若有c结点，要想进行右单旋，新增节点必然在a的左右子树，再进行旋转后，subL两边的高度肯定会保持一致，反之若无结点c，新增结点必然在a位置，只有三个结点的旋转，旋转后sbL左右高度必然是平衡的

注：在旋转的过程中，也要注意更新旋转结点的父指针

右单旋总结：
1.将b给根结点的左子树，再将根结点给subL的右子树，将subL变成根结点
2.旋转后parent和subL结点的平衡因子都为0
3.发生右单旋的条件，parent的平衡因子为-2，parent的左子树的根的平衡因子为-1

代码如下：

//右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left;//subL为旋转点的左孩子Node* subLR = subL->_right;//subLR也就是图中的b位置parent->_left = subLR;//将b给旋转点的左子树if (subLR) //可能为空，就不需要更新父结点subLR->_parent = parent;Node* pparent = parent->_parent; //记录旋转点的父结点subL->_right = parent;//将subL的右指向旋转点parent->_parent = subL;//更新旋转点的父结点if (pparent == nullptr) //判断旋转前的根结点是否为旋转点{_root = subL; // 直接将subL变成树的根subL->_parent = nullptr;}else{//判断subL结在父结点的左子树还是右子树if (pparent->_left == parent){pparent->_left = subL;}else{pparent->_right = subL;}//更新subL的父结点subL->_parent = pparent;}//更新平衡因子subL->_bf = parent->_bf = 0;
}

左单旋：

左单旋的抽象图如下：

当新增结点在a位置时，树的平衡遭到破坏，此时结点10的平衡因子变成了2，就需要进行旋转处理，旋转步骤：以结点10为旋转点，由于b的范围在结点10到结点15之间，所以可以将b给结点10的右子树，再将结点10给结点15的左子树，该旋转过程就叫作左单旋。

新增结点的情况也有三种，跟右单旋一样，可以新增在a的左右子树，也可以新增在a位置，类似的旋转过程这里就省略了。左单旋也是只会影响parent和subR结点的平衡因子，以右单旋的方式类推，也可以得出左单旋中parent和subR结点的平衡因子也为0

左单旋总结：
1.将b给根结点的右子树，再将根结点给subR的左子树，将subR变成根结点
2.旋转后parent和subL结点的平衡因子都为0
3.发生左单旋的条件，parent的平衡因子为2，parent的左子树的根的平衡因子为1

代码如下：

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* pparent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (pparent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}subR->_parent = pparent;}subR->_bf = parent->_bf = 0;
}

左右双旋：

什么情况下才会发生左右双旋，请看下图：

两种情况对比，一个新增结点在a位置，另一个新增结点在b位置，为什么新增结点在b位置的情况下，右单旋之后依旧没有保持平衡呢，看到图中被我圈起来的位置，能发生右单旋的新增结点的长度是要纯粹的左边高的，当新增结点在b位置时，它的长度不是纯粹的左边高，它是左边高即右边也高，所以不能纯粹的只进行单旋转的操作，需要进行两次单旋转操作

左右双旋核心步骤：先对parent结点的左孩子进行左单旋，也就是图中结点10的左孩子，结点5进行左单旋，因为对结点5来说它的右子树较高，所以以结点5为旋转点进行左单旋，左单旋完之后，对结点10来说左子树较高，再以结点10为旋转点进行右单旋

左右双旋，可分三种情况来讨论：

第一种，当h = 1时，新增结点在b位置的左子树，旋转操作如下：

第二种，当h = 1时，新增结点在b的右子树，旋转操作如下：

第三种，当h = 0时，新增结点在b位置，旋转操作如下：

从上面三种情况可以得知，右边高即左边高时，用左右双旋，先以父结点的左孩子为旋转点，进行左单旋，再以父结点为旋转点进行右单旋。左右双旋只会影响parent、subL和subLR结点的平衡因子，它们的平衡因子，也分三种情况。

左右双旋后的平衡因子：

1.第一种情况，当h = 1且新增结点在b的左子树时，subL的平衡因子为0，因为h为1时，subL的高度为一高一低，当把subLR的左给subL的右时，subL就平衡了，所以平衡因子为0；parent的平衡因子为1，因为此时parent的左右子树为一高一低且新增结点在b的左子树，b的右子树为空，当进行右单旋时，b的右子树给parent的左子树，给的是空树，所以parent的平衡因子为1；subLR的平衡因子为0。

2.第二种情况，当h = 1且新增结点在b的右子树时，subL的平衡因子为-1，因为h为1时，subL的高度为一高一低，进行左单旋，当把subLR的左给subL的右时，由于subLR的左子树为空，所以subL的平衡因子为-1；parent的平衡因子为0，因为此时parent的左右子树为一高一低且新增结点在subLR的右子树，当进行右单旋时，subLR的右子树给parent的左子树，所以parent的平衡因子为0；subLR的平衡因子为0。

3.第三种情况，当h = 0且新增在b位置，b的左右子树都为空，即subL、parent和subLR的平衡因子都为0。

注：根据b结点的平衡因子即可判断新增节点在哪个位置

左右双旋总结：
1.以parent结点的左孩子为旋转点进行左单旋，再以parent结点进行右单旋
2.旋转后根据b结点的平衡因子判断新增结点的位置，再判断更新平衡因子
3.发生左右双旋的条件，parent的平衡因子为-2，parent的左子树的根的平衡因子为1

代码如下：

//左右双旋
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);//先进行左单旋RotateR(parent);//再进行右单旋if (bf == 0)//新增结点在b位置{subL->_bf = 0;parent->_bf = 0;subLR->_bf = 0;}else if (bf == -1)//新增结点在b的左子树{subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1)//新增结点在b的右子树{subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}else{assert(false);}
}

右左双旋：

右左双旋的抽象图，如下：

在b位置进行新增结点，就会导致右边高及左边高，它不是纯粹的右边高，所以不能直接进行左单旋，需要先进行右单旋，降低左边的高度，再进行左单旋，降低右边的高度

右左双旋核心步骤：先对parent结点的右孩子进行右单旋，也就是图中结点10的右孩子，结点15进行右单旋，因为对结点15来说它的左子树较高，所以以结点15为旋转点进行右单旋，右单旋完之后，对结点10来说右子树较高，再以结点10为旋转点进行左单旋

右左双旋也是根据新增结点的位置，即h的高度分三种情况来讨论，与左右双旋的情况类似，这里就不做展开分析

右左双旋后平衡因子的更新，同样也是分三种情况来讨论，与左右双旋的推到过程类似，当h = 1，新增结点在b的左子树时，subR的平衡因子为1，parent的平衡因子为0，subRL的平衡因子为0；当h = 1,新增结点在b的右子树时，subR的平衡因子为0，parent的平衡因子为-1，subRL的平衡因子为0；当h = 0，新增结点在b位置时，三个结点的平衡因子都为0

注：根据b结点的平衡因子即可判断新增节点在哪个位置

右左双旋总结：
1.以parent结点的右孩子为旋转点进行右单旋，再以parent结点进行左单旋
2.旋转后根据b结点的平衡因子判断新增结点的位置，再判断更新平衡因子
3.发生右左双旋的条件，parent的平衡因子为2，parent的左子树的根的平衡因子为-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;parent->_bf = 0;subRL->_bf = 0;}else if (bf == 1){subR->_bf = 0;parent->_bf = -1;subRL->_bf = 0;}else if (bf == -1){subR->_bf = 1;parent->_bf = 0;subRL->_bf = 0;}else{assert(false);}
}

完成以上三种大的步骤，插入才算完成

3.AVL树的查找

AVL树的查找，是通过key关键值查找的，比当前结点的值大就往右查找，比当前结点的值小，就左继续查找，走到空说明要查找的值不存在。想详细了解可看博主二叉搜索树那篇文章的内容，代码实现如下：

Node* find(const k& key)
{Node* cur = _root;while (cur){if (cur->_kv.first > key){cur = cur->_left;}else if (cur->_kv.first < key){cur = cur->_right;}else{return cur;}}return nullptr;
}

（三）检查一棵树是否是AVL树

方法：通过遍历每个结点，计算每个结点左右子树的高度，用右子树的高度-左子树的高度，计算结果与结点的平衡因子进行比较。可用前序、中序或者后序对整个树进行遍历一遍，进行计算和检查

代码如下：

int _Hight(Node* root)
{if (root == nullptr){return 0;}int lefthight = _Hight(root->_left);int righthight = _Hight(root->_right);return lefthight > righthight ? lefthight + 1 : righthight + 1;
}bool _IsBalanceTree(Node* root)
{if (root == nullptr){return true;//空树也是AVL树}int lefthight = _Hight(root->_left);int righthight = _Hight(root->_right);int ret = righthight - lefthight;//若ret的绝对值>=2，或者与结点的平衡因子不相等，则说明不是AVL树if (abs(ret) >= 2){cout << root->_kv.first << ":" << "高度有差异" << endl;return false;}if (ret != root->_bf){cout << root->_kv.first << ":" << "平衡因子有差异" << endl;return false;}//继续往下遍历每个结点，若都是AVL树，则该树就是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}