文章目录一、AVL树的概念二、AVL树的实现1、AVL树的节点2、 AVL的插入的过程3、平衡因子的更新三、旋转1、右单旋2、左单旋3、左右双旋4、右左双旋四、AVL树平衡检测五、AVL树查找一、AVL树的概念二、AVL树的实现1、AVL树的节点key,vaule的二叉搜索树需要用三叉链多定义的父亲指针用来更新平衡因子templateclassK,classVstructAVLTreeNode{pairk,v_kv;AVLTreeNode*_left;AVLTreeNode*_right;AVLTreeNode*_parent;int_bf;//banlance factor平衡因子AVLTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};2、 AVL的插入的过程3、平衡因子的更新boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_left;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_right;}elsereturnfalse;}curnewNode(kv);cur-_parentparent;if(parent-_kv.firstkv.first){parent-_leftcur;}else{parent-_rightcur;}//更新平衡因子while(parent){if(parent-_leftcur){--parent-_bf;}else{parent-_bf;}if(parent-_bf0){//平衡后结束break;}elseif(parent-_bf-1||parent-_bf1){//不平衡继续向上更新curparent;parentparent-_parent;}elseif(parent-_bf-2||parent-_bf2){//高度差大于1进行旋转//右单旋左边高if(parent-_bf-2cur-_bf-1)RotateR(parent);elseif(parent-_bf2cur-_bf1)//纯粹的右边高进行左单旋RotateL(parent);elseif(parent-_bf-2cur-_bf1)//进行左右双旋{RotateLR(parent);}elseif(parent-_bf2cur-_bf-1)//进行右左双旋{RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}returntrue;}三、旋转1、持搜索树的规则2、让旋转的树从不满⾜变平衡其次降低旋转树的⾼度旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋。1、右单旋左边的高度大于右边时右旋转//右单旋voidRotateR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;Node*ppNodeparent-_parent;parent-_leftsubLR;subL-_rightparent;if(subLR)subLR-_parentparent;parent-_parentsubL;subL-_parentppNode;if(ppNodenullptr){_rootsubL;}else{if(ppNode-_leftparent){ppNode-_leftsubL;}else{ppNode-_rightsubL;}}parent-_bf0;subL-_bf0;}2、左单旋右边高进行左单旋//左单旋voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;Node*ppNodeparent-_parent;parent-_rightsubRL;subR-_leftparent;if(subRL)subRL-_parentparent;parent-_parentsubR;subR-_parentppNode;if(ppNodenullptr){_rootsubR;}else{if(ppNode-_leftparent){ppNode-_leftsubR;}else{ppNode-_rightsubR;}}parent-_bf0;subR-_bf0;}3、左右双旋//左右双旋voidRotateLR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;intbfsubLR-_bf;RotateL(parent-_left);RotateR(parent);if(bf-1){subL-_bf0;parent-_bf1;subLR-_bf0;}elseif(bf1){subL-_bf-1;parent-_bf0;subLR-_bf0;}elseif(bf0){subL-_bf0;parent-_bf0;subLR-_bf0;}else{assert(false);}}4、右左双旋//右左双旋voidRotateRL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;intbfsubRL-_bf;RotateR(parent-_right);RotateL(parent);if(bf1){subR-_bf0;parent-_bf-1;subRL-_bf0;}elseif(bf-1){subR-_bf1;parent-_bf0;subRL-_bf0;}elseif(bf0){subR-_bf0;parent-_bf0;subRL-_bf0;}else{assert(false);}}四、AVL树平衡检测boolIsBalanceTree(){return_IsBalanceTree(_root)!-1;}int_IsBalanceTree(Node*root){if(rootnullptr)return0;intleft_IsBalanceTree(root-_left);if(left-1)return-1;intright_IsBalanceTree(root-_right);if(right-1)return-1;intdifright-left;if(abs(dif)2){coutroot-_kv.first高度异常endl;return-1;}if(dif!root-_bf){coutroot-_kv.first平衡因子异常endl;return-1;}returnabs(left-right)2?max(left,right)1:-1;}五、AVL树查找Node*Find(constKkey){Node*cur_root;while(cur){if(cur-_kv.firstkey){curcur-_left;}elseif(cur-_kv.firstkey){curcur-_right;}elsereturncur;}returnnullptr;}