AVL树的实现与测试

C实现AVL树完整代码本文实现了完整的C模板版AVL自平衡二叉搜索树包含核心功能和完整测试用例对AVL树节点的模板定义AVL树的插入含平衡因子更新AVL树中的节点查找各类旋转的实现左、右单旋左右双旋右左双旋其余辅助代码树高测量平衡检测节点数量统计中序遍历打印测试代码Test_01固定序列测试可打开查看中序遍历和平衡性检测结果Test_02为万级随机数压力测试可通过Debug 和 Release不同版本下进行AVL树形成时间差异AVLTree.h#pragmaonce#includemap#includeassert.h#includealgorithm#includevector#includeiostreamusingnamespacestd;templateclassK,classVstructAVLTreeNode{pairK,V_kv;AVLTreeNodeK,V*_left;AVLTreeNodeK,V*_right;AVLTreeNodeK,V*_parent;int_bf;AVLTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};templateclassK,classVclassAVLTree{typedefAVLTreeNodeK,VNode;public:boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);returntrue;}Node*cur_root;Node*parentnullptr;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_left;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_right;}else{returnfalse;}}curnewNode(kv);if(parent-_kv.firstkv.first){parent-_leftcur;}elseif(parent-_kv.firstkv.first){parent-_rightcur;}cur-_parentparent;while(parent){if(curparent-_left){parent-_bf--;}else{parent-_bf;}if(parent-_bf0){break;}elseif(parent-_bf2||parent-_bf-2){if(parent-_bf2cur-_bf1){RotateL(parent);}elseif(parent-_bf2cur-_bf-1){RotateRL(parent);}elseif(parent-_bf-2cur-_bf-1){RotateR(parent);}elseif(parent-_bf-2cur-_bf1){RotateLR(parent);}break;}elseif(parent-_bf1||parent-_bf-1){curparent;parentparent-_parent;}else{assert(false);}}returntrue;}Node*find(constKkey){Node*cur_root;while(cur){if(cur-_kv.firstkey){curcur-_left;}elseif(cur-_kv.firstkey){curcur-_right;}else{returncur;}}returnnullptr;}//右单旋voidRotateR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;parent-_leftsubLR;if(subLR){subLR-_parentparent;}Node*pparentparent-_parent;subL-_rightparent;parent-_parentsubL;if(pparentnullptr){_rootsubL;subL-_parentnullptr;}else{subL-_parentpparent;if(pparent-_leftparent){pparent-_leftsubL;}else{pparent-_rightsubL;}}parent-_bfsubL-_bf0;}//左单旋voidRotateL(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(pparent-_leftparent){pparent-_leftsubR;}else{pparent-_rightsubR;}subR-_parentpparent;}parent-_bfsubR-_bf0;}//左右双旋voidRotateLR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;intbfsubLR-_bf;RotateL(subL);RotateR(parent);if(bf0){subLR-_bf0;subL-_bf0;parent-_bf0;}elseif(bf1){subLR-_bf0;subL-_bf-1;parent-_bf0;}elseif(bf-1){subLR-_bf0;subL-_bf0;parent-_bf1;}else{assert(false);}}//右左双旋voidRotateRL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;intbfsubRL-_bf;RotateR(subR);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);}}intHeight(){return_Height(_root);}boolIsBalanceTree(){return_IsBalanceTree(_root);}intsize(){return_size(_root);}voidInOrder(){_InOrder(_root);}private:int_Height(Node*_root){if(_rootnullptr){return0;}intleft_h_Height(_root-_left);intright_h_Height(_root-_right);returnmax(left_h,right_h)1;}int_size(Node*_root){if(_rootnullptr){return0;}return_size(_root-_left)_size(_root-_right)1;}void_InOrder(Node*_root){if(_rootnullptr){return;}_InOrder(_root-_left);cout_root-_kv.first:_root-_kv.secondendl;_InOrder(_root-_right);}bool_IsBalanceTree(Node*root){if(rootnullptr){returntrue;}intleft_h_Height(root-_left);intright_h_Height(root-_right);intdiffright_h-left_h;if(abs(diff)2){coutroot-_kv.first高度差异常endl;returnfalse;}if(diff!root-_bf){coutroot-_kv.first平衡因子异常endl;returnfalse;}return_IsBalanceTree(root-_left)_IsBalanceTree(root-_right);}private:Node*_rootnullptr;};Test.cpp#define_CRT_SECURE_NO_WARNINGS1#includeAVL.hvoidTest_01(){AVLTreeint,intt;inta[]{16,3,7,11,9,26,18,14,15};for(autoe:a){t.Insert({e,e});}t.InOrder();coutt.IsBalanceTree()endl;}voidTest_02(){vectorintv;AVLTreeint,inta;intN10000;srand(time(0));for(inti0;iN;i){v.push_back(rand()i);}intbegin1clock();for(autoe:v){a.Insert({e,e});}intend1clock();coutInsert time: end1-begin1endl;coutSize: a.size()endl;coutheight: a.Height()endl;intbegin2clock();for(autoch:v){a.find(ch);}intend2clock();coutend2-begin2endl;}intmain(){//Test_01();Test_02();return0;}