1.AVL的概念●AVL树是最先发明的自平衡二叉查找树AVL是一颗空树或具备下列性质的二叉搜索树它的左右子树都是AVL树且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树通过控制高度差去控制平衡。●AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis他们在1962年的论文《An algorithm for the organization of information》中发表了它。●AVL树实现这里我们引入一个平衡因子balance facor的概念每个节点都有一个平衡因子任何节点的平衡因子等于右子树的高度减去左子树的高度也就是说任何节点的平衡因子等于0/1/-1AVL树并不是必须要平衡因子但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡就像一个风向标一样。●为什么AVL树是高度平衡搜索二叉树要求高度差不超过1而不是高度差是0呢0不是更好的平衡吗通过画图我们可以发现不是不想这样设计而是有些情况无法做到高度差为0。如一棵树是2个节点4个节点等情况下高度差最好就是1无法做到高度差是0.●AVL树整体节点数量和分布和完全二叉树类似高度可以控制在logN那么增删查改的效率也可以控制在OlogN相比二叉搜索树有了本质的提升。2.AVL树的实现2.1AVL树的结构1234567891011121314151617181920212223templateclassk,classvstructAVLTreeNode{//需要parent指针后续更新平衡因子需要pairk,v _kv;AVLTreeNodek,v* _left;AVLTreeNodek,v* _right;AVLTreeNodek,v* _parent;int_bf;//平衡因子AVLTreeNode(constpairk,v kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};templateclassk,classvclassAVLTree{typedefAVLTreeNodek,v Node;public:private:Node* _rootnullptr;};2.2AVL树的插入2.2.1AVL树插入一个值的大概过程1.插入一个值按二叉搜索树规则进行插入。2.新增节点后只会影响祖先节点的高度也就是可能会影响部分祖先节点的平衡因子所以更新从新增节点-根节点路径上的平衡因子实际中最坏情况下要更新到根有些情况更新到中间就可以停止了。3.更新平衡因子过程中没有出现问题则插入结束。4.更新平衡因子过程中出现不平衡对不平衡子树旋转旋转后本质调平衡的同时本质降低了子树的高度不会再影响上一层所以插入结束。2.2.2平衡因子更新更新原则●平衡因子右子树高度-左子树高度●只有子树高度变化才会影响当前节点平衡因子●插入节点会增加高度所以新增节点再parent的右子树parent的平衡因子新增节点在parent的左子树parent平衡因子--●parent所在子树的高度是否变化决定了是否会继续往上更新更新停止条件●更新后parent的平衡因子等于0更新中parent的平衡因子变化为-1-0说明更新前parent子树一边高一边低新增的节点插入在低的那边插入后parent所在的子树高度不变不会影响parent的父亲节点的平衡因子更新结束。●更新后parent的平衡因子等于1或-1更新前更新中parent的平衡因子变化为0-1或0--1说明更新前parent子树两边一样高新增的插入节点后parent所在的子树一边高一边低parent所在的子树符合平衡要求但是高度增加了1会影响parent的父亲节点的平衡因子所以要继续向上更新。●更新后parent的平衡因子等于2或-2更新前更新中parent的平衡因子变化为1-2或-1--2说明更新前parent子树一边高一边低新增的插入节点在高的那边parent所在的子树高的那边更高了破坏了平衡parent所在的子树不符合平衡要求需要旋转处理旋转的目标有两个1、把parent子树旋转平衡。2、降低parent子树的高度恢复到插入节点以前的高度。所以旋转后也不需要继续向上更新插入结束。●不断更新更新到根根的平衡因子是1或-1也停止了。更新到10节点平衡因子为210所在的子树已经不平衡需要旋转处理更新到中间节点3为根的子树高度不变不会影响上一层更新结束最坏更新到根停止2.2.3插入节点更新平衡因子的代码实现1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950boolInsert(constpairk,v kv){if(!_root){_rootnewNode(kv);returntrue;}Node* parentnullptr;Node* cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}elsereturnfalse;}//开始插入curnewNode(kv);if(cur-_kv.firstparent-_kv.first)parent-_leftcur;elseparent-_rightcur;//父指针指向父节点cur-_parentparent;//控制平衡while(parent){//当节点插入左边时父节点平衡因子--if(curparent-_left)parent-_bf--;//当节点插入右边时父节点平衡因子elseparent-_bf;//查看树是否依旧平衡if(parent-_bf0){//说明父节点之前是1或-1插入新节点后树可能不平衡break;}elseif(parent-_bf1||parent-_bf-1){curparent;parentcur-_parent;}elseif(parent-_bf2||parent-_bf-2){//不平衡旋转break;}//防止树一开始就不平衡elseassert(false);}returntrue;}2.3旋转2.3.1旋转的原则1.保持搜索树的规则2.让旋转的树从不满足并平衡其次降低旋转树的高度旋转总共分为四种左单选/右单旋/左右双旋/右左双旋。2.3.2右单旋●图1展示的是10为根的树有a/b/c抽象为三颗高度为h的子树h0a/b/c均符合AVL树的要求。10可能是整棵树的根也可能是一整棵树中局部的子树的根。这里a/b/c是高度为h的子树是一种概括抽象表示它代表了所有右单旋的场景实际右单旋形态有很多种图2/图3/图4/图5进行详细描述。●在a子树中插入一个新节点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平衡因子从-1变成-210为根的树左右高度差超过1违反平衡规则。10为根的树左边太高了需要往右边旋转控制两棵树的平衡。●旋转核心步骤因为5b子树的值10将b变成10的左子树10变成5的右子树5变成这棵树新的根符合搜索树的规则控制了平衡同时这棵树的高度恢复到了插入之前的h2符合旋转原则。若插入之前10整棵树的局部子树旋转后不会再影响上一层插入结束。2.3.3右单旋代码实现12345678910111213141516171819202122232425voidRotateR(Node* parent){Node* subLparent-_left;Node* subLRsubL-_right;parent-_leftsubLR;//链接父节点if(subLR)subLR-_parentparent;//防止找不到父结点的父结点Node* pparentparent-_parent;subL-_rightparent;parent-_parentsubL;if(parent_root){_rootsubL;subL-_parentnullptr;}else{if(pparent-_leftparent)pparent-_leftsubL;elsepparent-_rightsubL;subL-_parentpparent;}//更新平衡因子parent-_bf0;subL-_bf0;}2.3.4左单旋●图6展示的是10为根的树有a/b/c抽象为三棵高度为h的子树h0a/b/c均符合AVL树的要求。10可能是整棵树的根也可能是一整棵树中局部的子树的根。这里a/b/c是高度为h的子树是一种概括抽象表示它代表了所有右单旋的场景实际右单旋形态有很多种具体跟上面左旋类似。●在a子树中插入一个新节点导致a子树的高度从h变成h1不断向上跟新平衡因子导致10的平衡因子从1变成210为跟的树左右高度差超过1违反平衡规则。10为跟的树右边太高了需要往左边旋转控制两棵树的平衡。●旋转核心步骤因为10b子树的值15将b变成10的右子树10变成15的左子树15变成这棵树新的根符合搜索树的规则控制了平衡同时这颗的高度恢复到了插入之前的h2符合旋转原则。若插入之前10整棵树的一个局部子树旋转后不会再影响上一层插入结束。2.3.5左单旋的实现123456789101112131415161718192021222324voidRotateL(Node* parent){Node* subRparent-_right;Node* subRLsubR-_left;parent-_rightsubRL;//链接父节点if(subRL)subRL-_parentparent;//防止找不到父结点的父结点Node* pparentparent-_parent;subR-_leftparent;parent-_parentsubR;if(pparentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentpparent-_left)pparent-_leftsubR;elsepparent-_rightsubR;subR-_parentpparent;}//更新平衡因子parent-_bfsubR-_bf0;}2.3.6左右双旋通过图7和图8可以看到左边高时若插入位置不是在a子树而是插入在b子树b子树高度从h变成h1引发旋转右单旋无法解决问题右单旋后我们的树依旧不平衡。右单旋解决的是存粹的左边高需要用两次旋转才能解决以5为旋转点进行一个左单旋以10为旋转点进行一个右单旋这棵树就平衡了。●图7和图8分别为左右双旋中h0和h1具体场景分析下面将a/b/c子树抽象为高度h的AVL子树进行分析另外把b子树的细节进一步展开为8和左子树高度为h-1的e和f子树因为我们要对b的父亲5为旋转点进行左单旋左单旋需要动b树中的左子树。b子树中新增节点的位置不同平衡因子更新的细节也不同通过观察8的平衡因子不同这里可以分3个场景讨论。●场景1h1时新增节点插入在e子树e子树高度从h-1并为h并不断更新8-5-10平衡因子引发旋转其中8的平衡因子为-1旋转后8和5平衡因子为010平衡因子为1。●场景2h1时新增节点插入在f子树f子树高度从h-1变为h并不断更新8-5-10平衡因子引发旋转其中8的平衡因子为1旋转后8和10平衡因子为05平衡因子为-1.●场景3h0a/b/c都是空树b自己就是一个新增节点不断更新5-10平衡因子引发旋转其中8的平衡因子为0旋转后8和10和5平衡因子均为0。2.3.7左右双旋代码实现12345678910111213141516171819202122232425oid RotateLR(Node* parent){Node* subLparent-_left;Node* subLRsubL-_right;intbfsubLR-_bf;RotateL(parent-_left);RotateR(parent);if(bf0){//更新平衡因子subL-_bf0;subLR-_bf0;parent-_bf0;}elseif(bf-1){subL-_bf0;subLR-_bf0;parent-_bf1;}elseif(bf1){subL-_bf-1;subLR-_bf0;parent-_bf0;}else{assert(false);}}2.3.8右左双旋●跟左右双旋类似下面将a/b/c子树抽象为高度h的AVL子树进行分析另外需要把b子树的细节进一步展开为12和左子树高度为h-1的e和f子树因为我们要对b的父亲15为旋转点进行右单旋右单旋需要动b树中的右子树。b子树中新增节点的位置不同平衡因子更新的细节也不同通过观察12的平衡因子不同这里可以分三个场景讨论。●场景1h1时新增节点插入在e子树e子树高度从h-1变为h并不断更新12-15-10平衡因子引发旋转其中12的平衡因子为-1旋转后10和12平衡因子为015平衡因子为1.●场景2h1时新增节点插入在f子树f子树高度从h-1变为h并不断更新12-15-10平衡因子引发旋转其中12的平衡因子为1旋转后15和12平衡因子为010平衡因子为-1。●场景3h0时a/b/c都是空树b自己就是一个新增节点不断更新15-10平衡因子引发旋转其中12的平衡因子为0旋转后10和12和15平衡因子均为0.2.3.9右左双旋代码实现12345678910111213141516171819202122232425voidRotateRL(Node* parent){Node* subRparent-_right;Node* subRLsubR-_left;intbfsubRL-_bf;RotateR(parent-_right);RotateL(parent);if(bf0){//更新平衡因子subR-_bf0;subRL-_bf0;parent-_bf0;}elseif(bf-1){subR-_bf1;subRL-_bf0;parent-_bf0;}elseif(bf1){subR-_bf0;subRL-_bf0;parent-_bf-1;}else{assert(false);}}2.4AVL树的查找拿二叉搜索树的逻辑就可以实现搜索效率为OlogN12345678910111213Node* Find(constk key){Node* cur_root;while(cur){if(cur-_kv.firstkey){curcur-_right;}elseif(cur-_kv.firstkey){curcur-_left;}elsereturncur;}returnnullptr;}2.5AVL树平衡检查实现的AVL树是否合格可以通过检查左右子树高度差的程度进行反向验证同时检查节点的平衡因子更新是否出现问题。1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677int_Height(Node* root){if(root nullptr)return0;intleftHeight _Height(root-_left);intrightHeight _Height(root-_right);returnleftHeight rightHeight ? leftHeight 1 : rightHeight 1;}bool_IsBalanceTree(Node* root){// 空树也是AVL树if(nullptr root)returntrue;// 计算pRoot结点的平衡因子即pRoot左右子树的高度差intleftHeight _Height(root-_left);intrightHeight _Height(root-_right);intdiff rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等或者// pRoot平衡因子的绝对值超过1则一定不是AVL树if(abs(diff) 2){cout root-_kv.first 高度差异常 endl;returnfalse;}if(root-_bf ! diff){cout root-_kv.first 平衡因子异常 endl;returnfalse;}// pRoot的左和右如果都是AVL树则该树一定是AVL树return_IsBalanceTree(root-_left) _IsBalanceTree(root-_right);}voidTestAVLTree1(){AVLTreeint,int t;// 常规的测试用例inta[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例//int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for(auto e : a){t.Insert({ e, e });}t.InOrder();cout t.IsBalanceTree() endl;}voidTestAVLTree2(){constintN 1000000;vectorint v;v.reserve(N);srand(time(0));for(size_ti 0; i N; i){v.push_back(rand() i);}size_tbegin2 clock();AVLTreeint,int t;for(auto e : v){t.Insert(make_pair(e, e));}size_tend2 clock();cout Insert: end2 - begin2 endl;cout t.IsBalanceTree() endl;cout Height: t.Height() endl;cout Size: t.Size() endl;size_tbegin1 clock();// 确定在的值for(auto e : v){t.Find(e);}// 随机值/*for (size_t i 0; i N; i){t.Find((rand() i));}*/size_tend1 clock();cout Find: end1 - begin1 endl;}以上就是C AVL树概念与实现详解的详细内容 C++ AVL树概念与实现详解
1.AVL的概念●AVL树是最先发明的自平衡二叉查找树AVL是一颗空树或具备下列性质的二叉搜索树它的左右子树都是AVL树且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树通过控制高度差去控制平衡。●AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis他们在1962年的论文《An algorithm for the organization of information》中发表了它。●AVL树实现这里我们引入一个平衡因子balance facor的概念每个节点都有一个平衡因子任何节点的平衡因子等于右子树的高度减去左子树的高度也就是说任何节点的平衡因子等于0/1/-1AVL树并不是必须要平衡因子但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡就像一个风向标一样。●为什么AVL树是高度平衡搜索二叉树要求高度差不超过1而不是高度差是0呢0不是更好的平衡吗通过画图我们可以发现不是不想这样设计而是有些情况无法做到高度差为0。如一棵树是2个节点4个节点等情况下高度差最好就是1无法做到高度差是0.●AVL树整体节点数量和分布和完全二叉树类似高度可以控制在logN那么增删查改的效率也可以控制在OlogN相比二叉搜索树有了本质的提升。2.AVL树的实现2.1AVL树的结构1234567891011121314151617181920212223templateclassk,classvstructAVLTreeNode{//需要parent指针后续更新平衡因子需要pairk,v _kv;AVLTreeNodek,v* _left;AVLTreeNodek,v* _right;AVLTreeNodek,v* _parent;int_bf;//平衡因子AVLTreeNode(constpairk,v kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};templateclassk,classvclassAVLTree{typedefAVLTreeNodek,v Node;public:private:Node* _rootnullptr;};2.2AVL树的插入2.2.1AVL树插入一个值的大概过程1.插入一个值按二叉搜索树规则进行插入。2.新增节点后只会影响祖先节点的高度也就是可能会影响部分祖先节点的平衡因子所以更新从新增节点-根节点路径上的平衡因子实际中最坏情况下要更新到根有些情况更新到中间就可以停止了。3.更新平衡因子过程中没有出现问题则插入结束。4.更新平衡因子过程中出现不平衡对不平衡子树旋转旋转后本质调平衡的同时本质降低了子树的高度不会再影响上一层所以插入结束。2.2.2平衡因子更新更新原则●平衡因子右子树高度-左子树高度●只有子树高度变化才会影响当前节点平衡因子●插入节点会增加高度所以新增节点再parent的右子树parent的平衡因子新增节点在parent的左子树parent平衡因子--●parent所在子树的高度是否变化决定了是否会继续往上更新更新停止条件●更新后parent的平衡因子等于0更新中parent的平衡因子变化为-1-0说明更新前parent子树一边高一边低新增的节点插入在低的那边插入后parent所在的子树高度不变不会影响parent的父亲节点的平衡因子更新结束。●更新后parent的平衡因子等于1或-1更新前更新中parent的平衡因子变化为0-1或0--1说明更新前parent子树两边一样高新增的插入节点后parent所在的子树一边高一边低parent所在的子树符合平衡要求但是高度增加了1会影响parent的父亲节点的平衡因子所以要继续向上更新。●更新后parent的平衡因子等于2或-2更新前更新中parent的平衡因子变化为1-2或-1--2说明更新前parent子树一边高一边低新增的插入节点在高的那边parent所在的子树高的那边更高了破坏了平衡parent所在的子树不符合平衡要求需要旋转处理旋转的目标有两个1、把parent子树旋转平衡。2、降低parent子树的高度恢复到插入节点以前的高度。所以旋转后也不需要继续向上更新插入结束。●不断更新更新到根根的平衡因子是1或-1也停止了。更新到10节点平衡因子为210所在的子树已经不平衡需要旋转处理更新到中间节点3为根的子树高度不变不会影响上一层更新结束最坏更新到根停止2.2.3插入节点更新平衡因子的代码实现1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950boolInsert(constpairk,v kv){if(!_root){_rootnewNode(kv);returntrue;}Node* parentnullptr;Node* cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}elsereturnfalse;}//开始插入curnewNode(kv);if(cur-_kv.firstparent-_kv.first)parent-_leftcur;elseparent-_rightcur;//父指针指向父节点cur-_parentparent;//控制平衡while(parent){//当节点插入左边时父节点平衡因子--if(curparent-_left)parent-_bf--;//当节点插入右边时父节点平衡因子elseparent-_bf;//查看树是否依旧平衡if(parent-_bf0){//说明父节点之前是1或-1插入新节点后树可能不平衡break;}elseif(parent-_bf1||parent-_bf-1){curparent;parentcur-_parent;}elseif(parent-_bf2||parent-_bf-2){//不平衡旋转break;}//防止树一开始就不平衡elseassert(false);}returntrue;}2.3旋转2.3.1旋转的原则1.保持搜索树的规则2.让旋转的树从不满足并平衡其次降低旋转树的高度旋转总共分为四种左单选/右单旋/左右双旋/右左双旋。2.3.2右单旋●图1展示的是10为根的树有a/b/c抽象为三颗高度为h的子树h0a/b/c均符合AVL树的要求。10可能是整棵树的根也可能是一整棵树中局部的子树的根。这里a/b/c是高度为h的子树是一种概括抽象表示它代表了所有右单旋的场景实际右单旋形态有很多种图2/图3/图4/图5进行详细描述。●在a子树中插入一个新节点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平衡因子从-1变成-210为根的树左右高度差超过1违反平衡规则。10为根的树左边太高了需要往右边旋转控制两棵树的平衡。●旋转核心步骤因为5b子树的值10将b变成10的左子树10变成5的右子树5变成这棵树新的根符合搜索树的规则控制了平衡同时这棵树的高度恢复到了插入之前的h2符合旋转原则。若插入之前10整棵树的局部子树旋转后不会再影响上一层插入结束。2.3.3右单旋代码实现12345678910111213141516171819202122232425voidRotateR(Node* parent){Node* subLparent-_left;Node* subLRsubL-_right;parent-_leftsubLR;//链接父节点if(subLR)subLR-_parentparent;//防止找不到父结点的父结点Node* pparentparent-_parent;subL-_rightparent;parent-_parentsubL;if(parent_root){_rootsubL;subL-_parentnullptr;}else{if(pparent-_leftparent)pparent-_leftsubL;elsepparent-_rightsubL;subL-_parentpparent;}//更新平衡因子parent-_bf0;subL-_bf0;}2.3.4左单旋●图6展示的是10为根的树有a/b/c抽象为三棵高度为h的子树h0a/b/c均符合AVL树的要求。10可能是整棵树的根也可能是一整棵树中局部的子树的根。这里a/b/c是高度为h的子树是一种概括抽象表示它代表了所有右单旋的场景实际右单旋形态有很多种具体跟上面左旋类似。●在a子树中插入一个新节点导致a子树的高度从h变成h1不断向上跟新平衡因子导致10的平衡因子从1变成210为跟的树左右高度差超过1违反平衡规则。10为跟的树右边太高了需要往左边旋转控制两棵树的平衡。●旋转核心步骤因为10b子树的值15将b变成10的右子树10变成15的左子树15变成这棵树新的根符合搜索树的规则控制了平衡同时这颗的高度恢复到了插入之前的h2符合旋转原则。若插入之前10整棵树的一个局部子树旋转后不会再影响上一层插入结束。2.3.5左单旋的实现123456789101112131415161718192021222324voidRotateL(Node* parent){Node* subRparent-_right;Node* subRLsubR-_left;parent-_rightsubRL;//链接父节点if(subRL)subRL-_parentparent;//防止找不到父结点的父结点Node* pparentparent-_parent;subR-_leftparent;parent-_parentsubR;if(pparentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentpparent-_left)pparent-_leftsubR;elsepparent-_rightsubR;subR-_parentpparent;}//更新平衡因子parent-_bfsubR-_bf0;}2.3.6左右双旋通过图7和图8可以看到左边高时若插入位置不是在a子树而是插入在b子树b子树高度从h变成h1引发旋转右单旋无法解决问题右单旋后我们的树依旧不平衡。右单旋解决的是存粹的左边高需要用两次旋转才能解决以5为旋转点进行一个左单旋以10为旋转点进行一个右单旋这棵树就平衡了。●图7和图8分别为左右双旋中h0和h1具体场景分析下面将a/b/c子树抽象为高度h的AVL子树进行分析另外把b子树的细节进一步展开为8和左子树高度为h-1的e和f子树因为我们要对b的父亲5为旋转点进行左单旋左单旋需要动b树中的左子树。b子树中新增节点的位置不同平衡因子更新的细节也不同通过观察8的平衡因子不同这里可以分3个场景讨论。●场景1h1时新增节点插入在e子树e子树高度从h-1并为h并不断更新8-5-10平衡因子引发旋转其中8的平衡因子为-1旋转后8和5平衡因子为010平衡因子为1。●场景2h1时新增节点插入在f子树f子树高度从h-1变为h并不断更新8-5-10平衡因子引发旋转其中8的平衡因子为1旋转后8和10平衡因子为05平衡因子为-1.●场景3h0a/b/c都是空树b自己就是一个新增节点不断更新5-10平衡因子引发旋转其中8的平衡因子为0旋转后8和10和5平衡因子均为0。2.3.7左右双旋代码实现12345678910111213141516171819202122232425oid RotateLR(Node* parent){Node* subLparent-_left;Node* subLRsubL-_right;intbfsubLR-_bf;RotateL(parent-_left);RotateR(parent);if(bf0){//更新平衡因子subL-_bf0;subLR-_bf0;parent-_bf0;}elseif(bf-1){subL-_bf0;subLR-_bf0;parent-_bf1;}elseif(bf1){subL-_bf-1;subLR-_bf0;parent-_bf0;}else{assert(false);}}2.3.8右左双旋●跟左右双旋类似下面将a/b/c子树抽象为高度h的AVL子树进行分析另外需要把b子树的细节进一步展开为12和左子树高度为h-1的e和f子树因为我们要对b的父亲15为旋转点进行右单旋右单旋需要动b树中的右子树。b子树中新增节点的位置不同平衡因子更新的细节也不同通过观察12的平衡因子不同这里可以分三个场景讨论。●场景1h1时新增节点插入在e子树e子树高度从h-1变为h并不断更新12-15-10平衡因子引发旋转其中12的平衡因子为-1旋转后10和12平衡因子为015平衡因子为1.●场景2h1时新增节点插入在f子树f子树高度从h-1变为h并不断更新12-15-10平衡因子引发旋转其中12的平衡因子为1旋转后15和12平衡因子为010平衡因子为-1。●场景3h0时a/b/c都是空树b自己就是一个新增节点不断更新15-10平衡因子引发旋转其中12的平衡因子为0旋转后10和12和15平衡因子均为0.2.3.9右左双旋代码实现12345678910111213141516171819202122232425voidRotateRL(Node* parent){Node* subRparent-_right;Node* subRLsubR-_left;intbfsubRL-_bf;RotateR(parent-_right);RotateL(parent);if(bf0){//更新平衡因子subR-_bf0;subRL-_bf0;parent-_bf0;}elseif(bf-1){subR-_bf1;subRL-_bf0;parent-_bf0;}elseif(bf1){subR-_bf0;subRL-_bf0;parent-_bf-1;}else{assert(false);}}2.4AVL树的查找拿二叉搜索树的逻辑就可以实现搜索效率为OlogN12345678910111213Node* Find(constk key){Node* cur_root;while(cur){if(cur-_kv.firstkey){curcur-_right;}elseif(cur-_kv.firstkey){curcur-_left;}elsereturncur;}returnnullptr;}2.5AVL树平衡检查实现的AVL树是否合格可以通过检查左右子树高度差的程度进行反向验证同时检查节点的平衡因子更新是否出现问题。1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677int_Height(Node* root){if(root nullptr)return0;intleftHeight _Height(root-_left);intrightHeight _Height(root-_right);returnleftHeight rightHeight ? leftHeight 1 : rightHeight 1;}bool_IsBalanceTree(Node* root){// 空树也是AVL树if(nullptr root)returntrue;// 计算pRoot结点的平衡因子即pRoot左右子树的高度差intleftHeight _Height(root-_left);intrightHeight _Height(root-_right);intdiff rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等或者// pRoot平衡因子的绝对值超过1则一定不是AVL树if(abs(diff) 2){cout root-_kv.first 高度差异常 endl;returnfalse;}if(root-_bf ! diff){cout root-_kv.first 平衡因子异常 endl;returnfalse;}// pRoot的左和右如果都是AVL树则该树一定是AVL树return_IsBalanceTree(root-_left) _IsBalanceTree(root-_right);}voidTestAVLTree1(){AVLTreeint,int t;// 常规的测试用例inta[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例//int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for(auto e : a){t.Insert({ e, e });}t.InOrder();cout t.IsBalanceTree() endl;}voidTestAVLTree2(){constintN 1000000;vectorint v;v.reserve(N);srand(time(0));for(size_ti 0; i N; i){v.push_back(rand() i);}size_tbegin2 clock();AVLTreeint,int t;for(auto e : v){t.Insert(make_pair(e, e));}size_tend2 clock();cout Insert: end2 - begin2 endl;cout t.IsBalanceTree() endl;cout Height: t.Height() endl;cout Size: t.Size() endl;size_tbegin1 clock();// 确定在的值for(auto e : v){t.Find(e);}// 随机值/*for (size_t i 0; i N; i){t.Find((rand() i));}*/size_tend1 clock();cout Find: end1 - begin1 endl;}以上就是C AVL树概念与实现详解的详细内容