【C++篇】AVL树的实现

前言 

本篇是基于二叉搜索树写的，详情可以去看上篇【二叉搜索树】

一，AVL树的概念

（1），AVL树是一颗二叉搜索树，它是一棵空树或者是具备以下性质的二叉搜索树：它的左右子树都是AVL树，且左右子树的高度差不超过1。AVL树是一颗高度平衡二叉搜索树，通过控制高度差去控制平衡。

（2）， AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis是两个前苏联的科学家，他们在1962 年的论⽂《Analgorithmfortheorganizationofinformation》中发表了它。

（3），AVL树的实现这里引入一个平衡因子（balabce factor）的概念，每个节点都有一个平衡因子，平衡因子等于右子树的高度减去左子树的高度，所以说AVL树的所有节点的平衡因子都是0/1/-1。

（4），AVL树整体节点数量的分布和完全二叉树类似，高度可以控制字在logN,那么增删查改的效率也可以控制在logN,,相比二叉搜索树有了本质的提升。

二，AVL树的实现 

2.1，AVL树的结构

//树节点的定义  存储的时key/value结构
template<class k,class v>
struct AVLTreeNode
{pair<k, v> _kv;AVLTreeNode<k, v>* _left;AVLTreeNode<k, v>* _right;//需记录父节点，后面更新平衡因子时会使用AVLTreeNode<k, v>* _parent;//平衡因子  右子树高度-左子树高度int _bf; 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;
};

 2.2，AVL树的插入

2.2.1，插入一个值的大致过程

1，插入一个值按照二叉搜索树的规则。（比当前节点值大去右子树找，比当前节点值小去左子树找）

2，新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新 从新增结点->根结点路径上的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可 以停止了，具体情况我们下面再详细分析。

3，更新平衡因子过程中没有出现问题，则插入结束。

4，更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后调平衡的同时，本质降低了子树 的高度，不会再影响上一层，所以插入结束。

2.2.2，平衡因子的更新

更新原则：

 （1），平衡因子=右子树高度-左子树高度

 （2），只有子树⾼度变化才会影响当前结点平衡因子。

 （3），插子结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在parent的左子树，parent平衡因子--。

（4），parent所在子树的高度是否变化决定了是否会继续往上更新。

更新停止条件：

一共有3种情况：

（1），插入后parent的平衡因子更新为0，说明parent的平衡因子是由1->0或者-1->0,那么插入前parent子树是一边高一边低，插入的节点插入在parent子树低的一边，所以插入后parent子树的高度不变，不会影响parent的父节点的平衡因子，更新结束。

（2），插入后parent的平衡因子更新为1或-1，说明parent的平衡因子是由0->1或者0->-1,那么插入前parent子树两边一样高，插入后parent子树一边高一边低，parent所在子树符合要求，parent子树的高度增加了1，所以会影响parent的父节点的平衡因子，需要继续向上更新。

（3），插入后parent的平衡因子更新为2或者-2，说明parent的平衡因子是由1->2或者-1->-2,那么插入前parent子树是一边高一边低，插入的节点插入在子树高的一边，导致高的那边更高了，破坏了平衡，parent所在子树不符合平衡要求，需进行旋转处理。

旋转处理后的子树：parent所在子树已经平衡，降低了parent所在子树的高度，所以旋转后不需要再向上更新平衡因子。

2.2.3，插入节点及平衡因子更新的代码实现 

bool Insert(const pair<k, v>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}//找插入的位置并记录父节点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->_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)//继续向上更新{cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//旋转处理break;}else{//防止更新平衡因子过程中出错assert(false);}}return true;}

2.3，旋转

2.3.1，旋转的原则：

（1），保持AVL树的规则。

（2），让旋转的树从不满足变平衡，其次降低旋转树的高度。

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

2.3.2，右单旋

1，如下图，展示的是一颗以10为根的子树，10可能是是整棵树的根，也可能只是局部的子树的根。a/b/c是三颗抽象的子树，它们都满足AVL树，他们的高度h>=0.

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

3，旋转核心步骤，因为5<b子树的值<10,将b变成10的左子树，10变成5的右子树，5变成这棵树新的根，符合搜索树的规则。控制了平衡，同时这棵树的高度恢复到了插入之前的h+2。如果插入之前10是整棵树的根，那么旋转后5成为新的根；如果插入之前10是局部子树的根，那么旋转后5成为新的根，需要和上层连接起来。

示例：

2.3.3，右单旋的代码 

//右单旋  纯粹的左边高void RotateR(Node* parent){//以parent为旋转点进行旋转Node* subL = parent->_left;Node* subLR = subL->_right;//记录parent的父节点Node* pparent = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;//parent为整棵树的根if (parent == _root){_root=subL;_root->_parent = nullptr;}//parent为局部子树的根，需要连接上一层pparentelse{if (pparent->_left == parent)pparent->_left = subL;elsepparent->_right = subL;subL->_parent = pparent;}//旋转结束后，更新平衡因子parent->_bf = subL->_bf = 0;}

2.3.4，左单旋

左单旋和右单旋类似：

1，下图所示，10可能是是整棵树的根，也可能只是局部的子树的根。a/b/c是三颗抽象的子树，它们都满足AVL树，他们的高度h>=0.

2，在a子树中插入一个新节点，导致a子树的高度从h变为h+1,不断向上更新平衡因子，导致10的平衡因子变为2，10为根的左右子树高度差超过1，破坏了平衡。10为根的子树右边太高了，需要往左边旋转，控制两棵树的平衡。

3，旋转核心步骤，因为10<b子树的值<15,将b变成10的右子树，10变成15的左子树，15变成这棵树新的根，符合搜索树的规则，控制了平衡。同时这棵树的高度恢复到了插入之前的h+2,如果插入之前10是整棵树的根，那么旋转后5成为新的根；如果插入之前10是局部子树的根，那么旋转后5成为新的根，需要和上层连接起来。

 2.3.5，左单旋的代码

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

2.3.6，左右双旋

前面我们讲的左单旋和右单旋都是纯粹的一边高，下面的双旋与之相反

1，观察下图，当插入的位置在b子树而不是在a子树时，此时的单旋就不能解决问题了。b子树高度从h变成h+1，引发旋转，右单旋无法解决问题，右单旋后，我们的树依旧不平衡。

可以看到，上面的情况经过单旋，结果还是不能解决问题；就第二张图而言，插入新节点后，以10为根的子树，它的左子树高，而以5为根的子树，它的右子树高，我们可以看成，对于以10为根的子树，不是纯粹的一边高。前面我们讲的单旋的场景，都是纯粹的一边高，经过单旋后，可以降低它的高度，控制平衡。

2，对于这种不是纯粹的一边高的情况，我们就需要进行双旋；

这样就解决了问题，控制了平衡。

3，以上只是两个例子，下面我们看抽象图。

 

 4，旋转完成后，接下来是平衡因子的更新

通过上图可以发现，我们只需更新parent,subL,subLR的平衡因子，旋转后的平衡因子取决与旋转前subLR的平衡因子。

上图只反映了两种情况，旋转前，subLR的平衡因子等于1或者-1两种情况，还有一种情况是等于0，也就是一开始举的那个例子。

可以发现旋转后的平衡因子都为0.

2.3.7，左右双旋的代码 

//左右双旋
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;//记录旋转前subLR的平衡因子int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == -1){subLR->_bf = 0;subL-> _bf = 0;parent->_bf = 1;}else{assert(false);}
}

2.3.8，右左双旋

和左右双旋类似：

平衡因子的更新依旧取决于subRL的平衡因子。 

2.3.9，右左双旋的代码

//右左双旋
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);}
}

 2.4，AVL树平衡检测

我们实现的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 _isbalance(Node* root)
{if (root == nullptr)return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;if (abs(diff) >= 2){cout << root->_kv.first << "节点平衡因子异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "节点平衡因子不符合实际" << endl;return false;}return _isbalance(root->_left) && _isbalance(root->_right);
}

第二种方式是采用后序遍历的方式：

//后序
bool _isbalance2(Node* root,int& height)
{if (root == nullptr){height = 0;return true;}int leftHeight = 0;if (_isbalance2(root->_left, leftHeight) == false){cout << root->_kv.first << "平衡因子异常" << endl;return false;}int rightHeight = 0;if (_isbalance2(root->_right, rightHeight) == false){cout << root->_kv.first << "平衡因子异常" << endl;return false;}height = max(leftHeight, rightHeight) + 1;return abs(rightHeight - leftHeight) < 2;
}

2.5，整体代码

#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>
#include <assert.h>
using namespace std;//树节点的定义  存储的时key/value结构
template<class k,class v>
struct AVLTreeNode
{pair<k, v> _kv;AVLTreeNode<k, v>* _left;AVLTreeNode<k, v>* _right;//需记录父节点，后面更新平衡因子时会使用AVLTreeNode<k, v>* _parent;//平衡因子  右子树高度-左子树高度int _bf; 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:bool Insert(const pair<k, v>& kv){if (_root == nullptr){_root = new Node(kv);return true;}//找插入的位置并记录父节点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->_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)//继续向上更新{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);}else{assert(false);}break;}else{assert(false);}}return true;}//右单旋  纯粹的左边高void RotateR(Node* parent){//以parent为旋转点进行旋转Node* subL = parent->_left;Node* subLR = subL->_right;//记录parent的父节点Node* pparent = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;//parent为整棵树的根if (parent == _root){_root=subL;_root->_parent = nullptr;}//parent为局部子树的根，需要连接上一层pparentelse{if (pparent->_left == parent)pparent->_left = subL;elsepparent->_right = subL;subL->_parent = pparent;}//旋转结束后，更新平衡因子parent->_bf = subL->_bf = 0;}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* pparent = parent->_parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (pparent->_left == parent)pparent->_left = subR;elsepparent->_right = subR;subR->_parent = pparent;}parent->_bf = subR->_bf = 0;}//左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;//记录插入前subLR的平衡因子int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == -1){subLR->_bf = 0;subL-> _bf = 0;parent->_bf = 1;}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 == 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);}}void Inorder(){_Inorder(_root);cout << endl;}bool isbalance(){return _isbalance(_root);}bool isbalance2(){int height = 0;return _isbalance2(_root, height);}
private://后序bool _isbalance2(Node* root,int& height){if (root == nullptr){height = 0;return true;}int leftHeight = 0;if (_isbalance2(root->_left, leftHeight) == false){cout << root->_kv.first << "平衡因子异常" << endl;return false;}int rightHeight = 0;if (_isbalance2(root->_right, rightHeight) == false){cout << root->_kv.first << "平衡因子异常" << endl;return false;}height = max(leftHeight, rightHeight) + 1;return abs(rightHeight - leftHeight) < 2;}//计算高度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 _isbalance(Node* root){if (root == nullptr)return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;if (abs(diff) >= 2){cout << root->_kv.first << "节点平衡因子异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "节点平衡因子不符合实际" << endl;return false;}return _isbalance(root->_left) && _isbalance(root->_right);}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first<<":" << root->_kv.second << endl;_Inorder(root->_right);}
private://根节点Node* _root = nullptr;
};

 三，测试

#include "AVL-Tree.h"
#include <vector>
#include <time.h>void TestAVLTree1()
{srand(time(0));vector<int> v;int n = 10000;for (int i = 0; i < n; i++){v.push_back(rand() + i);}AVLTree<int, int> t;int begin1 = clock();for (auto e : v){t.Insert(make_pair(e, e));}int end1 = clock();cout << "insert:" << end1 - begin1 << endl;cout << t.isbalance2() << endl;
}
int main()
{TestAVLTree1();return 0;
}