C++ AVLTree高度平衡的二叉搜索树怎么实现
这篇“C++AVLTree高度平衡的二叉搜索树怎么实现”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C++AVLTree高度平衡的二叉搜索树怎么实现”文章吧。
一、AVL树的概念
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。
因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
平衡因子= 右子树高度-左子树高度
如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在O(log2N) ,搜索时间复杂度O(log2N)
二、AVL树节点的定义
节点结构:三叉链结构(左、右、父),以及平衡因子bf+构造函数(左右为空,平衡因子初始化为0)
template<classK,classV>structAVLTreeNode{pair<K,V>_kv;AVLTreeNode<K,V>*_left;AVLTreeNode<K,V>*_right;AVLTreeNode<K,V>*_parent;int_bf;//balancefactorAVLTreeNode(constpair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};三、AVL树的插入
AVL树在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。步骤过程:
找到插入的位置:根据二叉搜索树的做法
进行插入:判断插入的位置是parent的左还是右
更新平衡因子:如果不平衡的话,就要进行旋转
找到插入位置(比较节点大小即可):
插入的节点key值 > 当前位置的key值,往右子树走
插入的节点key值 < 当前位置的key值,往左子树走
插入的节点key值等于当前位置的key值,不能插入,返回false
插入之后,与二叉搜索树不同的是:我们还需要去进行平衡因子的更新,调平衡:
如果新增加的在右,平衡因子加加
如果新增加的在左,平衡因子减减
更新一个结点之后我们需要去进行判断,子树的高度是否发生了变化:
1.如果parent的平衡因子是0:说明之前parent的平衡因子是1或-1,说明之前parent一边高、一边低;这次插入之后填入矮的那边,parent所在的子树高度不变,不需要继续往上更新
2.如果parent的平衡因子是1或者-1:说明之前parent的平衡因子是0,两边一样高,插入之后一边更高,parent所在的子树高度发生变化,继续往上更新
3.平衡因子是2或-2,说明之前parent的平衡因子是1或-1,现在插入严重不平衡,违反规则,需要进行旋转处理
最坏的情况下:需要一直更新到根root:
我们更新平衡因子时第一个更新的就是parent,如果parent->_bf1或parent->_bf-1需要继续往上进行平衡因子的更新,向上迭代,直到parent为空的情况:
elseif(parent->_bf==1||parent->_bf==-1){cur=parent;parent=parent->_parent;}
当parent->_bf = 2或parent->_bf==-2时,我们就需要进行旋转了:
????如果parent的平衡因子是2,cur的平衡因子是1时,说明右边的右边比较高,我们需要进行左单旋
????如果parent的平衡因子是-2,cur的平衡因子是-1时,说明左边的左边比较高,我们需要进行右单旋
????如果parent的平衡因子是-2,cur的平衡因子是1时,我们需要进行左右双旋
????如果parent的平衡因子是2,cur的平衡因子是-1时,我们需要进行右左双旋
boolInsert(constpair<K,V>&kv){if(_root==nullptr){_root=newNode(kv);returntrue;}Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_kv.first<kv.first){parent=cur;cur=cur->_right;}elseif(cur->_kv.first>kv.first){parent=cur;cur=cur->_left;}else{returnfalse;}}cur=newNode(kv);if(parent->_kv.first<kv.first){parent->_right=cur;cur->_parent=parent;}else{parent->_left=cur;cur->_parent=parent;}//更新平衡因子while(parent){if(cur==parent->_left){parent->_bf--;}else{parent->_bf++;}if(parent->_bf==0){break;}elseif(parent->_bf==1||parent->_bf==-1){cur=parent;parent=parent->_parent;}elseif(parent->_bf==2||parent->_bf==-2){//左旋转if(parent->_bf==2&&cur->_bf==1){RotateL(parent);}//右旋elseif(parent->_bf==-2&&cur->_bf==-1){RotateR(parent);}//左右双旋elseif(parent->_bf==-2&&cur->_bf==1){RotateLR(parent);}//右左双旋elseif(parent->_bf==2&&cur->_bf==-1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}returntrue;}四、AVL树的旋转
在一棵原本是平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,使之平衡化。根据节点插入位置的不同,AVL树的旋转分为四种。
旋转规则:
1.让这颗子树左右高度差不超过1
2.旋转过程中继续保持它是搜索树
3.更新调整孩子节点的平衡因子
4.让这颗子树的高度根插入前保持一致
1.左单旋
新节点插入较高右子树的右侧—右右:左单旋
抽象图:
a/b/c是高度为h的AVL子树,代表多数情况:h>=0,其中h可以等于0、1、2…,不过都可以抽象成h,处理情况都一样:此时parent等于2,subR等于1。
具体左旋的步骤:
subRL成为parent的右子树:注意subL和parent的关系,调整parent的右以及subRL的父(subRL可能为空)
parent成为subR的左子树:调整parent的父与subR的左
subR成为相对的根节点:调整subR与ppNode:注意parent是不是整棵树的root,如果是,则让subR为_root,同时让_root->_parent置为空
更新平衡因子
左旋调整:subR的左子树值(subRL)本身就比parent的值要大,所以可以作为parent的右子树;而parent及其左子树当中结点的值本身就比subR的值小,所以可以作为subR的左子树。
**更新平衡因子bf:**subR与parent的bf都更新为0
代码实现左旋转:
//左单旋voidRotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL)subRL->_parent=parent;Node*ppNode=parent->_parent;subR->_left=parent;parent->_parent=subR;if(ppNode==nullptr){_root=subR;_root->_parent=nullptr;}else{if(ppNode->_left==parent){ppNode->_left=subR;}else{ppNode->_right=subR;}subR->_parent=ppNode;}parent->_bf=subR->_bf=0;}2.右单旋
新节点插入较高左子树的左侧—左左:右单旋
有了前面左旋的基础,我们在来看右旋就没有那么费劲了:
a/b/c是高度为h的AVL树,右旋旋转动作:b变成60的左边,60变成30的右边,30变成子树的根。
30比60小,b值是处于30和60之间,此时作为60的左边是没有问题的。
有了这个图,在结合前面左单旋的基础,我们就能很快实现我们的右单旋代码:
//右单旋voidRotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;parent->_left=subLR;if(subLR)subLR->_parent=parent;Node*ppNode=parent->_parent;parent->_parent=subL;subL->_right=parent;//if(_root==parent)if(ppNode==nullptr){_root=subL;_root->_parent=nullptr;}else{if(ppNode->_left==parent){ppNode->_left=subL;}else{ppNode->_right=subL;}subL->_parent=ppNode;}subL->_bf=parent->_bf=0;}3.左右双旋
新节点插入较高左子树的右侧—左右:先左单旋再右单旋
a/d是高度为h的AVL树,b/c是高度为h-1的AVL树。
以30为轴点进行左单旋:b变成30的右边,30变成60的左边,60变成子树根
以90为轴点进行右单旋:c变成90的左边,90变成60的右边,60变成子树的根
左右双旋:以subL为轴点左旋,以parent为轴点进行右旋,在进行平衡因子的更新(最大的问题)
我们从总体的角度来看,左右双旋的结果就是:就是把subLR的左子树和右子树,分别作为subL和parent的右子树和左子树,同时subL和parent分别作为subLR的左右子树,最后让subLR作为整个子树的根
subLR的左子树作为subL的右子树:因为subLR的左子树结点比subL的大
subLR的右子树作为parent的左子树:因为subLR的右子树结点比parent的小
平衡因子的更新:重新判断(识别插入节点是在b还是在c)根据subLR平衡因子的初始情况进行分类:
如果subLR初始平衡因子是-1时,左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0(插入在b)
如果subLR的初始平衡因子是1时,左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0(插入在c)
如果subLR初始平衡因子是0时,左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0(subLR自己新增)
代码实现:
//左右双旋voidRotateLR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;intbf=subLR->_bf;RotateL(parent->_left);RotateR(parent);//更新平衡因子if(bf==-1)//b插入,subLR左子树新增{subL->_bf=0;parent->_bf=1;subLR->_bf=0;}elseif(bf==1)//c插入,subLR右子树新增{parent->_bf=0;subL->_bf=-1;subLR->_bf=0;}elseif(bf==0)//subLR自己新增加{parent->_bf=0;subL->_bf=0;subLR->_bf=0;}else{assert(false);}}4.右左双旋
新节点插入较高右子树的左侧—右左:先右单旋再左单旋
插入
subR为轴点进行右单旋:
parent为轴进行左单旋:
既右左双旋:
右左双旋后,根据subRL 初始平衡因子的不同分为三种情况分别对应subRL = 0、1、-1情况,与左右双旋情况类似。
voidRotateRL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;intbf=subRL->_bf;RotateR(subR);RotateL(parent);if(bf==1){subR->_bf=0;subRL->_bf=0;parent->_bf=-1;}elseif(bf==-1){subR->_bf=1;subRL->_bf=0;parent->_bf=0;}elseif(bf==0){subR->_bf=0;subRL->_bf=0;parent->_bf=0;}else{assert(false);}}五、进行验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证AVL树,可以分两步:
验证其为二叉搜索树
如果中序遍历可得到一个有序的序列,就说明为二叉搜索树
void_InOrder(Node*root){if(root==nullptr)return;_InOrder(root->_left);cout<<root->_kv.first<<":"<<root->_kv.second<<endl;_InOrder(root->_right);}
验证其为平衡树
每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确
如果是空树,是AVL树;高度差不大于2,并且递归左右子树的高度差都不大于2,也是AVL树;判断平衡因子和该点的高度差是否相等
//求高度intHeight(Node*root){if(root==nullptr)return0;intlh=Height(root->_left);intrh=Height(root->_right);returnlh>rh?lh+1:rh+1;}//判断平衡boolIsBalance(Node*root){if(root==nullptr){returntrue;}intleftHeight=Height(root->_left);intrightHeight=Height(root->_right);if(rightHeight-leftHeight!=root->_bf){cout<<root->_kv.first<<"平衡因子异常"<<endl;returnfalse;}returnabs(rightHeight-leftHeight)<2&&IsBalance(root->_left)&&IsBalance(root->_right);}六、AVLTree的性能
AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证查询时高效的时间复杂度即log2( N) 。但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。
因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合.
送上源码:
#pragmaonce#include<iostream>#include<assert.h>#include<time.h>usingnamespacestd;template<classK,classV>structAVLTreeNode{pair<K,V>_kv;AVLTreeNode<K,V>*_left;AVLTreeNode<K,V>*_right;AVLTreeNode<K,V>*_parent;int_bf;//balancefactorAVLTreeNode(constpair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};template<classK,classV>structAVLTree{typedefAVLTreeNode<K,V>Node;public:boolInsert(constpair<K,V>&kv){if(_root==nullptr){_root=newNode(kv);returntrue;}Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_kv.first<kv.first){parent=cur;cur=cur->_right;}elseif(cur->_kv.first>kv.first){parent=cur;cur=cur->_left;}else{returnfalse;}}cur=newNode(kv);if(parent->_kv.first<kv.first){parent->_right=cur;cur->_parent=parent;}else{parent->_left=cur;cur->_parent=parent;}//更新平衡因子while(parent){if(cur==parent->_left){parent->_bf--;}else{parent->_bf++;}if(parent->_bf==0){break;}elseif(parent->_bf==1||parent->_bf==-1){cur=parent;parent=parent->_parent;}elseif(parent->_bf==2||parent->_bf==-2){//左旋转if(parent->_bf==2&&cur->_bf==1){RotateL(parent);}//右旋elseif(parent->_bf==-2&&cur->_bf==-1){RotateR(parent);}//左右双旋elseif(parent->_bf==-2&&cur->_bf==1){RotateLR(parent);}//右左双旋elseif(parent->_bf==2&&cur->_bf==-1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}returntrue;}//左单旋voidRotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL)subRL->_parent=parent;Node*ppNode=parent->_parent;subR->_left=parent;parent->_parent=subR;if(ppNode==nullptr){_root=subR;_root->_parent=nullptr;}else{if(ppNode->_left==parent){ppNode->_left=subR;}else{ppNode->_right=subR;}subR->_parent=ppNode;}parent->_bf=subR->_bf=0;}voidRotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;parent->_left=subLR;if(subLR)subLR->_parent=parent;Node*ppNode=parent->_parent;parent->_parent=subL;subL->_right=parent;//if(_root==parent)if(ppNode==nullptr){_root=subL;_root->_parent=nullptr;}else{if(ppNode->_left==parent){ppNode->_left=subL;}else{ppNode->_right=subL;}subL->_parent=ppNode;}subL->_bf=parent->_bf=0;}//左右双旋voidRotateLR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;intbf=subLR->_bf;RotateL(parent->_left);RotateR(parent);//更新平衡因子if(bf==-1)//b插入,subLR左子树新增{subL->_bf=0;parent->_bf=1;subLR->_bf=0;}elseif(bf==1)//c插入,subLR右子树新增{parent->_bf=0;subL->_bf=-1;subLR->_bf=0;}elseif(bf==0)//subLR自己新增加{parent->_bf=0;subL->_bf=0;subLR->_bf=0;}else{assert(false);}}//右左双旋voidRotateRL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;intbf=subRL->_bf;RotateR(subR);RotateL(parent);if(bf==1){subR->_bf=0;subRL->_bf=0;parent->_bf=-1;}elseif(bf==-1){subR->_bf=1;subRL->_bf=0;parent->_bf=0;}elseif(bf==0){subR->_bf=0;subRL->_bf=0;parent->_bf=0;}else{assert(false);}}voidInOrder(){_InOrder(_root);}void_InOrder(Node*root){if(root==nullptr)return;_InOrder(root->_left);cout<<root->_kv.first<<":"<<root->_kv.second<<endl;_InOrder(root->_right);}intHeight(Node*root){if(root==nullptr)return0;intlh=Height(root->_left);intrh=Height(root->_right);returnlh>rh?lh+1:rh+1;}boolIsBalance(){returnIsBalance(_root);}boolIsBalance(Node*root){if(root==nullptr){returntrue;}intleftHeight=Height(root->_left);intrightHeight=Height(root->_right);if(rightHeight-leftHeight!=root->_bf){cout<<root->_kv.first<<"平衡因子异常"<<endl;returnfalse;}returnabs(rightHeight-leftHeight)<2&&IsBalance(root->_left)&&IsBalance(root->_right);}private:Node*_root=nullptr;};//测试voidTestAVLTree(){//inta[]={8,3,1,10,6,4,7,14,13};//inta[]={16,3,7,11,9,26,18,14,15};inta[]={4,2,6,1,3,5,15,7,16,14};AVLTree<int,int>t;for(autoe:a){t.Insert(make_pair(e,e));}t.InOrder();cout<<t.IsBalance()<<endl;}voidTestAVLTree2(){srand(time(0));constsize_tN=100000;AVLTree<int,int>t;for(size_ti=0;i<N;i++){size_tx=rand();t.Insert(make_pair(x,x));}//t.InOrder();cout<<t.IsBalance()<<endl;}
以上就是关于“C++AVLTree高度平衡的二叉搜索树怎么实现”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注行业资讯频道。