C++:AVL树

一、AVL树的概念

二、AVL树的实现

1、AVL树的节点

key,vaule的二叉搜索树，需要用三叉链，多定义的父亲指针用来更新平衡因子

template<classK,classV>structAVLTreeNode{pair<k,v>_kv;AVLTreeNode*_left;AVLTreeNode*_right;AVLTreeNode*_parent;int_bf;//banlance factor平衡因子AVLTreeNode(constpair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};

2、 AVL的插入的过程

3、平衡因子的更新

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->_left;}elseif(cur->_kv.first<kv.first){parent=cur;cur=cur->_right;}elsereturnfalse;}cur=newNode(kv);cur->_parent=parent;if(parent->_kv.first>kv.first){parent->_left=cur;}else{parent->_right=cur;}//更新平衡因子while(parent){if(parent->_left==cur){--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){//高度差大于1，进行旋转//右单旋，左边高if(parent->_bf==-2&&cur->_bf==-1)RotateR(parent);elseif(parent->_bf==2&&cur->_bf==1)//纯粹的右边高，进行左单旋RotateL(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;}

三、旋转

1、持搜索树的规则
2、让旋转的树从不满⾜变平衡，其次降低旋转树的⾼度

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

1、右单旋

左边的高度大于右边时右旋转

//右单旋voidRotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;Node*ppNode=parent->_parent;parent->_left=subLR;subL->_right=parent;if(subLR)subLR->_parent=parent;parent->_parent=subL;subL->_parent=ppNode;if(ppNode==nullptr){_root=subL;}else{if(ppNode->_left==parent){ppNode->_left=subL;}else{ppNode->_right=subL;}}parent->_bf=0;subL->_bf=0;}

2、左单旋

右边高进行左单旋

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

3、左右双旋

//左右双旋voidRotateLR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;intbf=subLR->_bf;RotateL(parent->_left);RotateR(parent);if(bf==-1){subL->_bf=0;parent->_bf=1;subLR->_bf=0;}elseif(bf==1){subL->_bf=-1;parent->_bf=0;subLR->_bf=0;}elseif(bf==0){subL->_bf=0;parent->_bf=0;subLR->_bf=0;}else{assert(false);}}

4、右左双旋

//右左双旋voidRotateRL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;intbf=subRL->_bf;RotateR(parent->_right);RotateL(parent);if(bf==1){subR->_bf=0;parent->_bf=-1;subRL->_bf=0;}elseif(bf==-1){subR->_bf=1;parent->_bf=0;subRL->_bf=0;}elseif(bf==0){subR->_bf=0;parent->_bf=0;subRL->_bf=0;}else{assert(false);}}

四、AVL树平衡检测

boolIsBalanceTree(){return_IsBalanceTree(_root)!=-1;}int_IsBalanceTree(Node*root){if(root==nullptr)return0;intleft=_IsBalanceTree(root->_left);if(left==-1)return-1;intright=_IsBalanceTree(root->_right);if(right==-1)return-1;intdif=right-left;if(abs(dif)>=2){cout<<root->_kv.first<<"高度异常"<<endl;return-1;}if(dif!=root->_bf){cout<<root->_kv.first<<"平衡因子异常"<<endl;return-1;}returnabs(left-right)<2?max(left,right)+1:-1;}

五、AVL树查找

Node*Find(constK&key){Node*cur=_root;while(cur){if(cur->_kv.first>key){cur=cur->_left;}elseif(cur->_kv.first<key){cur=cur->_right;}elsereturncur;}returnnullptr;}