AVL树的概念

二叉搜索树虽然可以缩短查找的效率,但如果数据有序或接近有序,那么二叉搜索树将退化为单支树,查找元素则相当于在顺序表中搜索元素,是将复杂度为O(n),效率低下.
如果当向二叉搜索树中插入新的结点后,如果能保证每个结点的左右子树高度只差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,减少平均搜索长度.

AVL树的性质:
1: 它的左右子树AVL树.
2: 任意一个子树左右高度差都不超过1(-1 / 0 / 1 )

如果一棵二叉搜索树是高度平衡的如果它有N个结点,其高度可保持在O(log2N),搜索时间复杂度也为O(log2N).

AVL树结点定义

我们实现的是KV模型的AVL树,为了方便后续的操作,这里AVL树结点定义为三叉链结构,并且引入平衡因子,方便判断每棵树的平衡情况,并且还需要一个初始化列表将结点成员全部初始化.

template<class K, class V>
struct AVLTreeNode
{//三叉链AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;//存储键值对int _bf; //平衡因子AVLTreeNode(const pair<K, V>& kv) //初始化列表:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv)       //调用键值对的构造函数, _bf(0){}
};

AVL树的插入

AVL树的插入总共有三个步骤:
1: 找到要插入结点的位置.

2:插入成功后,控制平衡,更新平衡因子.

3:当插入时parent所在子树已经不平衡了,则需要旋转.

1:找到需要插入结点的位置
我们可以利用搜索二叉树基本思想进行查找插入位置:
1: 如果插入的结点值大于当前结点值,向右遍历.

2: 如果插入的结点值小于当前结点值,向左遍历.

3:如果插入的结点值等于当前结点值,则不需要插入.

2:插入成功后,更新平衡因子:
(a): 插入成功,将当前结点的parent指向插入结点,将插入结点的_parent指向parent,建立插入结点与parent结点的联系.
(b): 向上循环更新平衡因子
更新平衡因子时,我们将cur代表新插入的结点,parent代表插入结点的父亲结点,一直向上循环更新平衡因子知道parent为空.
1:如果新增在右,_bf++,如果新增在左,_bf–.

2: 如果更新后,abs( parent->_bf ) ==1,说明parent插入之前的平衡因子是0,即插入前左右子树高度相等,插入后,parent所在树的高度发生改变,即左右子树一边高一边低,进而导致parent的平衡因子改变,需要继续向上更新(因为会对parent的祖先平衡因子造成影响)

3:如果更新后,abs(parent->_bf ) == 0, 说明parent插入之前的平衡因子是1or-1,插入之后,parent所在树的高度不变,即对祖先无影响,此时不需要往上更新平衡因子.

4: 如果更新后,abs(parent->_bf) == 2,说明parent插入之前的平衡因子是1or-1,已经达到平衡临界值,插入新结点变成2or-2.此时,已经打破平衡,parent所在子树需要旋转处理.

5: 如果更新后,parent->_bf > 2或者parent->_bf < -2,此时说明在插入之前,这个AVL树已经不平衡了,此时需要断言处理,检查之前的操作问题.

3:当插入时parent所在子树已经不平衡了,则需要旋转

当更新完平衡因子,此时parent已经不平衡了,此时分为四种情况

1: 当parent的平衡因子为2,cur的平衡因子为1时,进行左单旋.

2: 当parent的平衡因子为-2,cur的平衡因子为-1时,进行右单旋.

3:当parent的平衡因子为-2,cur的平衡因子为1时,进行左右单旋.

4: 当parent的平衡因子为2,cur的平衡因子为-1时,进行右左单旋.

插入代码如下:

template <class K,class V>
struct AVLTree
{typedef AVLTreeNode<K, V> Node;
public: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->first < kv.first){parent = cur;cur = cur->_right;}else if (cur->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;//插入时,cur的parent也要维护.//控制平衡,如何更新平衡因子.while ( parent  ){if (cur == parent->_right){parent->_bf++;}else{parent->_bf--;}if (abs(parent->_bf) == 1){parent = parent->_parent;cur = cur->_parent;}else if (abs(parent->_bf) == 0 ) //对祖先的平衡因子没有影响,所以不需要再更新平衡因子.{break;                 }else if( abs( parent->_bf) == 2 ) //parent所在的子树已经不平衡了,需要旋转处理{if (parent->_bf == 2 && cur->_bf == 1)//parent的平衡因子等于2,且cur的平衡因子等于1的时候,需要左单旋.{RotateL(parent);      //左单旋}else if (parent->_bf == -2 && cur->_bf == -1) //parent的平衡因子等于-2,且cur的平衡因子等于-1的时候,需要右单旋.{RotateR(parent);     //右单旋}else if ( parent->_bf == -2 && cur->_bf == 1  )//符合parent的平衡因子等于-2,且cur的平衡因子等于1,采用左右双旋.{RotateLR(parent);}break;                 //例如,原来parent所在树的高度为h+2,插入新节点之后变成//h+3,可是右单旋之后又变成了h+2,此时parent高度并没有发生变化,//不必再往上更新平衡}else                             //走到这里,插入结点发现插入平衡因子的绝对值是大于2的.{assert(false);}	}return true;                       //插入,更新完平衡因子,即可插入成功.}

注意:当旋转完毕,在旋转时已经更新了平衡因子,此时parent的高度相较之前并没有发生改变,也就是说parent所在子树并不会影响祖先的平衡因子,此时可以退出,不必往上更新平衡因子了.

AVL树的旋转

左单旋

将新节点插入parent右子树较高的右侧:
左单旋的操作步骤:
1: 让parent作为subR的左子树.

2: 让subR的左子树作为parent的右子树.

3: 判断根,并相应作出调整
(a) : 如果parent是整棵树的根
如果parent是整棵树的根,旋转后subR就是这棵树的根,让_root指向subR.
(b): 如果parent是子树的根
如果parent是子树的根,此时要记录旋转前parent的parent为ppNode,将subR与
ppNode建立联系,此时又有两种情况:
(1): 如果旋转前,parent为ppNode的左子树,那么旋转后,subR就为ppNode的左子树.
(2): 如果旋转前,parent为ppNode的右子树,那么旋转后,subR就为ppNode的右子树.
4: 更新平衡因子
左单旋中,只有parent与subR的高度发生变化需要更新平衡因子,且二者的平衡因子单旋后都为0.

左单旋代码如下:

void RotateL(Node* parent)              //左旋{Node* subR = parent->_right;Node* subRL = subR->_left;Node* ppNode = parent->_parent;subR->_left = parent;parent->_right = subRL;if (subRL)                 //subRL的h有可能为0.{subRL->_parent = parent;}parent->_parent = subR;//判断parent是整棵树的根,还是其他树的子树.if (_root == parent)  //如果parent是整棵树的根{_root = subR;subR->_parent = nullptr;,}else{if (ppNode->_left == parent)  //如果parent在ppNode的左边{ppNode->_left = subR;}else                         //如果parent在ppNode的右边{ppNode->_right = subR;}subR->_parent = ppNode;  //subR的parent指向ppNode.}subR->_bf = parent->_bf = 0;              //旋转完毕答,即可更新平衡因子.}

注意:
当h==0时,即subRL为空时,此时不能访问subRL的父亲,所以针对它要额外进行判断.(包括右单旋)

右单旋

将新节点插入parent当前左子树较高的左侧:
右单旋的操作步骤:
1: 让parent作为subL的右子树.

2: 让subL的右子树作为parent的左子树.

3: 判断根,并相应作出调整
(a) : 如果parent是整棵树的根
如果parent是整棵树的根,旋转后subR就是这棵树的根,让_root指向subL.
(b): 如果parent是子树的根
如果parent是子树的根,此时要记录旋转前parent的parent为ppNode,将subL与
ppNode建立联系,此时又有两种情况:
(1): 如果旋转前,parent为ppNode的左子树,那么旋转后,subL就为ppNode的左子树.
(2): 如果旋转前,parent为ppNode的右子树,那么旋转后,subL就为ppNode的右子树.

4: 更新平衡因子
右单旋中,只有parent与subR的高度发生变化需要更新平衡因子,且二者的平衡因子单旋后都为0.

右单旋的代码如下:

void RotateR(Node* parent)    //右旋{Node* subL = parent->_left;Node* subLR = subL->_right;Node* ppNode = parent->_parent;subL->_right = parent;parent->_left = subLR;if (subLR)                 //subRL的h有可能为0.{subLR->_parent = parent;}parent->_parent = subL;//判断parent是整棵树的根,还是其他树的子树.if (_root == parent)  //如果parent是整棵树的根{_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent)  //如果parent在ppNode的左边{ppNode->_left = subL;}else                         //如果parent在ppNode的右边{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}

左右单旋

左右单旋主要有四个步骤:
1:在b处插入新结点.(假设在b处插入)

2: 以subL为旋转点左单旋.

3: 以subLR为旋转点右单旋.

4:更新平衡因子:
左右双旋中更新平衡因子根据插入新结点的位置有三种情况:

(1) 当在b处插入新结点时,即subRL->_bf 等于 1,左右双旋后,parent,subL,subLR的平衡因子分别为:0,-1,0.

(2)当在b处插入新结点时,即subLR等于-1,左右双旋后,parent,subL,subLR的平衡因子分别为:1,0,0

(3)当h==0,及subLR就为新插入的结时,左右双旋后,parent,subL,subLR的平衡因子都为0.

注意:
由以上更新平衡因子的情况可以看出,在插入新结点后,经过旋转后,parent的高度还是插入之前的高度,及不会影响其祖先的平衡因子,所以左右当选之后即可从更新平衡因子循环中退出.
左右双旋代码如下:

void RotateLR(Node* parent)       //左右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;          //记录subLR的平衡因子,根据该平衡因子的情况分三种//方式进行更新平衡因子.RotateL(parent->_left);       //左单旋RotateR(parent);             //右单旋subLR->_bf = 0;              //结点60的平衡因子一定为0.if ( bf == 1  )             //在c处插入{parent->_bf = 0;subL->_bf = -1;}else if ( bf == -1 )      //在b处插入{parent->_bf = 1subL->_bf = 0;}else if( bf == 0 )       //b处自己便是新增.{parent->_bf = subL->_bf = 0;}else                   //如果都不是,那就是有错误的地方.{assert(false);}}

右左双旋

右左单旋主要分为四个步骤:
1:插入新节点(假设在b处插入)

2: 以subR结点右单旋.

3: 以subRL结点左单旋.

4: 更新平衡因子
右左双旋中更新平衡因子根据插入新结点的位置有三种情况:
(1) :如果在c处插入,即subRL->_bf等于1,parent,subR,subRL的平衡因子分别为:

(2): 如果在b处插入,即subRL->_bf等于-1,parent,subR,subRL的平衡因子分别为:

(3):当h==0,即subRL结点就为新增结点,此时parent,subR,subRL的平衡因子都为0.

右左双旋代码如下:

void RotateRL( Node* parent ){RotateR(parent->_right);RotateL(parent);Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;subRL->_bf = 0;if( bf == 1 ){parent->_bf = -1;subR->_bf = 0;}else if ( bf == -1 ){parent->_bf = 0;subR->_bf = 1;}else if (bf == 0){parent->_bf = subR->_bf = 0;}else{assert(false);}}
private:Node* _root = nullptr;
};

AVL树的验证

因为AVL树也是二叉搜索树,我们可以采用中序遍历的方式遍历AVL树:

void InOrder(){_InOrder(_root);}
void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}

但是中序遍历只能证明AVL树是二叉搜索树,并不能证明它具备平衡的性质,所以我们可以根据该树的平衡因子来判断这棵树是否平衡,而求平衡因子首先就要求这棵树(或者子树的高度).

获取二叉树的高度采用的是后序遍历的思想,判断AVL树的平衡必须要求得左右子树的高度差(即平衡因子),如果平衡因子的绝对值 < 2,说明概树处于平衡状态.

注意:
判断AVL树的平衡是要判断它本身以及左右子树的平衡.

int Height(Node* root)                 //求高度{if (root == nullptr){return 0;}int leftHT = Height(root->_left);int rightHT = Height(root->_right);return max(leftHT, rightHT) + 1;      //获取完这棵子树的高度,然后返回到上一层递归的地方.}bool IsBanlance()           {return _IsBanlance(_root);}bool _IsBanlance(Node* root)           //判断AVL树是否平衡.{if (root == nullptr){return true;}int leftHT = Height(root->_left);int rightHT = Height(root->_right);int diff = rightHT - leftHT;return abs(diff) < 2 && _IsBanlance(root->_left) && _IsBanlance(root->_right);//要判断整棵树以及这棵树的左右子树是否平衡.}

AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即O(log2N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且
数据的个数为静态的,可以考虑AV树,但是如果一个结构经常修改,就不适合.

AVL树及测试完整代码

#include <map>
#include <iostream>
#include <assert.h>
#include <algorithm>
using namespace std;
template <class K,class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K,V> _kv; //存储结构int _bf;        //平衡因子AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0),_kv(kv) //走pair的构造函数{}
};template <class K,class V>
struct AVLTree
{typedef AVLTreeNode<K, V> Node;
public: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;//插入时,cur的parent也要维护.//控制平衡,如何更新平衡因子.while (parent){if (cur == parent->_right){parent->_bf++;}else{parent->_bf--;}if (abs(parent->_bf) == 1){parent = parent->_parent;cur = cur->_parent;}else if (abs(parent->_bf) == 0) //对祖先的平衡因子没有影响,所以不需要再更新平衡因子.{break;}else if (abs(parent->_bf) == 2) //parent所在的子树已经不平衡了,需要旋转处理{if (parent->_bf == 2 && cur->_bf == 1)//parent的平衡因子等于2,且cur的平衡因子等于1的时候,需要左单旋.{RotateL(parent);      //左单旋}else if (parent->_bf == -2 && cur->_bf == -1) //parent的平衡因子等于-2,且cur的平衡因子等于-1的时候,需要右单旋.{RotateR(parent);     //右单旋}else if (parent->_bf == -2 && cur->_bf == 1)//符合parent的平衡因子等于-2,且cur的平衡因子等于1,采用左右双旋.{RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}break;               //例如,原来parent所在树的高度为h+2,插入新节点之后变成//h+3,可是右单旋之后又变成了h+2,此时parent高度并没有发生变化,//不必再往上更新平衡}else                             //走到这里,插入结点发现插入平衡因子的绝对值是大于2的.{assert(false);}}return true;                       //插入,更新完平衡因子,即可插入成功.}void InOrder(){_InOrder(_root);}bool IsBanlance(){return _IsBanlance(_root);}
private:bool _IsBanlance(Node* root){if (root == nullptr){return true;}int leftHT = Height(root->_left);int rightHT = Height(root->_right);int diff = rightHT - leftHT;return abs(diff) < 2 && _IsBanlance(root->_left) && _IsBanlance(root->_right); //整棵树平衡且左子树和右子树都是平衡的.}//求高度int Height(Node* root){if (root == nullptr){return 0;}int leftHT = Height(root->_left);int rightHT = Height(root->_right);return max(leftHT, rightHT) + 1;}//遍历void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}void RotateL(Node* parent)              //左旋{Node* subR = parent->_right;Node* subRL = subR->_left;Node* ppNode = parent->_parent;subR->_left = parent;parent->_right = subRL;if (subRL)                 //subRL的h有可能为0.{subRL->_parent = parent;}parent->_parent = subR;//判断parent是整棵树的根,还是其他树的子树.if (_root == parent)  //如果parent是整棵树的根{_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent)  //如果parent在ppNode的左边{ppNode->_left = subR;}else                         //如果parent在ppNode的右边{ppNode->_right = subR;}subR->_parent = ppNode;}subR->_bf = parent->_bf = 0;              //旋转完毕答,即可更新平衡因子.}void RotateR(Node* parent)    //右旋{Node* subL = parent->_left;Node* subLR = subL->_right;Node* ppNode = parent->_parent;subL->_right = parent;parent->_left = subLR;if (subLR)                 //subRL的h有可能为0.{subLR->_parent = parent;}parent->_parent = subL;//判断parent是整棵树的根,还是其他树的子树.if (_root == parent)  //如果parent是整棵树的根{_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent)  //如果parent在ppNode的左边{ppNode->_left = subL;}else                         //如果parent在ppNode的右边{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}void RotateLR(Node* parent)       //左右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;          //记录subLR的平衡因子,根据该平衡因子的情况分三种//方式进行更新平衡因子.RotateL(parent->_left);       //左单旋RotateR(parent);             //右单旋subLR->_bf = 0;              //结点60的平衡因子一定为0.if (bf == 1)             //在c处插入{parent->_bf = 0;subL->_bf = -1;}else if (bf == -1)      //在b处插入{parent->_bf = 1;subL->_bf = 0;}else if (bf == 0)       //b处自己便是新增.{parent->_bf = subL->_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);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;parent->_bf = 0;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;}else{assert(false);}}private:Node* _root = nullptr;
};//测试代码1:
void TestAVLTree1()
{int a[] = { 16,3,7,11,9,26,18,14,15 };AVLTree<int, int> t1;for (auto e : a){t1.Insert(make_pair(e, e));}t1.InOrder();
}
//测试代码2:
//随机样式
//查AVL树的高度
void TestAVLTree2()
{int a[] = {4,2,6,1,3,5,15,7,16,14 };AVLTree<int, int> t1;for (auto e : a){t1.Insert(make_pair(e, e));}t1.InOrder();cout << "IsBanlance:" << t1.IsBanlance();
}//测试3
//随机数测试,使用10000个随机数测试
void TestAVLTree3()
{size_t N = 10000;srand(time(0));AVLTree<int, int> t1;for (size_t i = 0; i < N; ++i){int x = rand();               //x接收产生的随机数.t1.Insert(make_pair(x, i));   //在树中插入随机数.}cout << "IsBanlance:" << t1.IsBanlance() << endl;
}