数据结构与算法基础-学习-37-平衡二叉树（Avl树）之删除节点
目录
一、知识点回顾
1、二叉搜索树（BST）
2、平衡二叉树（Avl树）之查找
二、环境信息
三、实现思路
1、示例图
2、查询
3、删除
（1）叶子节点（无子树节点）
（2）有一棵子树节点
（3）有两棵子树节点
4、调整
（1）叶子节点（无子树节点）
（2）有一棵子树节点
（3）有两棵子树节点
四、代码分享
1、AvlTreeDelOne
2、AvlTreeCheck
3、AvlTreeCheckAll
五、虚机测试验证
1、编译
2、测试代码
3、运行结果
一、知识点回顾
1、二叉搜索树（BST）
链接：数据结构与算法基础-学习-15-二叉树之前序、后序、中序遍历的递归和非递归方法实现以及BST的初始化、插入、获取结点数
2、平衡二叉树（Avl树）之查找
链接：数据结构与算法基础-学习-21-查找之平衡二叉树（AVL树）
二、环境信息
| 名称 | 值 |
| CPU | Intel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz |
| 操作系统 | CentOS Linux release 7.9.2009 (Core) |
| 内存 | 4G |
| 逻辑核数 | 4 |
| gcc版本 | 4.8.5 20150623 (Red Hat 4.8.5-44) (GCC) |
| cmake版本 | 2.8.12.2 |
三、实现思路
1、示例图
2、查询
我们先找到需要删除的节点，Avl树本质还是一棵二叉搜索树，左子树小于本节点的键值，右子树大于本节点的键值，查找到的键值是否等于本节点的键值，等于找到删除节点，没有找到需比较大小，比本节点小需到左子树搜索，大需到右子树搜索，如果搜索的节点指针为空，说明此树中不存在需删除的节点。
从根节点到删除节点访问过的节点，本文称为访问路径，我们都需要记录下来，和添加节点时一样，后续需要用到。
3、删除
删除节点需要分情况讨论分别为：
（1）叶子节点（无子树节点）
直接删除，将父节点链接此节点的手置空。例如：我们删除80节点，
访问路径为40、53、70。我们再回溯（70，53，40），进行平衡因子的改变，如果有不平衡点，就可以用下一节的调整方法。
（2）有一棵子树节点
将父节点链接删除节点的手断开，链接到删除节点的子树上，然后删除待删除节点，就可以来到下一个调整阶段了。例如我们这边删除20节点。
（3）有两棵子树节点
讲解之前我们需要先说两个名词：前驱节点和后继节点。其实和数组中是一样的。我们用中序遍历拿到此树的一个升序结果，，例如我们删除40节点，图示如下：
这颗树右子树偏高，我们需要将右子树高度降低，来减少平衡调整次数，所以找后继节点49，将其替换40节点。寻找后继过程中访问的节点也需要加入到访问路径中，图示如下：
4、调整
回溯访问路径中的节点，计算平衡因子，如果出现不平衡，还是用之前添加节点时用到LL、LR、RR、RL四种来进行调整，如果有不懂得可以看《一、知识点回顾》->《2、平衡二叉树（Avl树）之查找》。实现这一块的代码基本没有变化和之前，并不区分是否是叶子节点、有一棵子树节点、有两棵子树节点，我这边只是举例为了大家能更好的理解，和上面还是一一对应的。
（1）叶子节点（无子树节点）
80节点被删除，访问路径按照栈的思路后进先出。
| 键值 | 平衡因子 | 备注 |
| 70 | 0 | 删除的是右子树节点，平衡因子加一。 |
| 53 | 0 | 删除的是右子树节点，平衡因子加一。 |
| 40 | 0 | 删除的是右子树节点，平衡因子加一。 |
代码测试验证：
[gbase@czg2 Exec]$ perf stat -e page-faults ./TestAvl
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreeInit : OK.
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreeAdd : OK, Key : 40, Root Node Key.
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreeAdd : OK, Key : 20.
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreeAdd : OK, Key : 53, No Rotation.
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreeAdd : OK, Key : 18.
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreeAdd : OK, Key : 49.
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreeAdd : OK, Key : 70, No Rotation.
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreeAdd : OK, Key : 80.
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreePrint :
Root : 0x1dd7560
TotalNodeNumsU : 7
TotalNodeNums : 7
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
18 (nil) 0 1 0x1dd75a0 (nil) (nil)
20 (nil) 1 1 0x1dd7450 0x1dd75a0 (nil)
40 (nil) -1 1 0x1dd7560 0x1dd7450 0x1dd7490
49 (nil) 0 1 0x1dd75e0 (nil) (nil)
53 (nil) -1 1 0x1dd7490 0x1dd75e0 0x1dd7620
70 (nil) -1 1 0x1dd7620 (nil) 0x1dd7660
80 (nil) 0 1 0x1dd7660 (nil) (nil)
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreeSearch : OK.
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreeDelOne : OK, Key : 80.
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreePrint :
Root : 0x1dd7560
TotalNodeNumsU : 6
TotalNodeNums : 6
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
18 (nil) 0 1 0x1dd75a0 (nil) (nil)
20 (nil) 1 1 0x1dd7450 0x1dd75a0 (nil)
40 (nil) 0 1 0x1dd7560 0x1dd7450 0x1dd7490
49 (nil) 0 1 0x1dd75e0 (nil) (nil)
53 (nil) 0 1 0x1dd7490 0x1dd75e0 0x1dd7620
70 (nil) 0 1 0x1dd7620 (nil) (nil)
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreeClear : OK.
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreeClear : OK.
2024-06-12 15:57:51-P[129455]-T[129455]-[Debug]-AvlTreeDestroy : OK.Performance counter stats for './TestAvl':199 page-faults:u 0.001484309 seconds time elapsed0.000000000 seconds user0.001503000 seconds sys（2）有一棵子树节点
我们这边删除20节点。
| 键值 | 平衡因子 | 备注 |
| 40 | -2 | 删除的是左子树节点，平衡因子减一。 |
不平衡点40的右子树高，我们往右子树探测发现53节点，也是右子树高，这时就可以用RR旋转来进行调整。
代码测试验证：
[gbase@czg2 Exec]$ perf stat -e page-faults ./TestAvl
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeInit : OK.
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeAdd : OK, Key : 40, Root Node Key.
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeAdd : OK, Key : 20.
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeAdd : OK, Key : 53, No Rotation.
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeAdd : OK, Key : 18.
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeAdd : OK, Key : 49.
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeAdd : OK, Key : 70, No Rotation.
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeAdd : OK, Key : 80.
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreePrint :
Root : 0x2607560
TotalNodeNumsU : 7
TotalNodeNums : 7
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
18 (nil) 0 1 0x26075a0 (nil) (nil)
20 (nil) 1 1 0x2607450 0x26075a0 (nil)
40 (nil) -1 1 0x2607560 0x2607450 0x2607490
49 (nil) 0 1 0x26075e0 (nil) (nil)
53 (nil) -1 1 0x2607490 0x26075e0 0x2607620
70 (nil) -1 1 0x2607620 (nil) 0x2607660
80 (nil) 0 1 0x2607660 (nil) (nil)
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeSearch : OK.
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeRotation : OK, RR.
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeDelOne : OK, Key : 20.
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreePrint :
Root : 0x2607490
TotalNodeNumsU : 6
TotalNodeNums : 6
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
18 (nil) 0 1 0x26075a0 (nil) (nil)
40 (nil) 0 1 0x2607560 0x26075a0 0x26075e0
49 (nil) 0 1 0x26075e0 (nil) (nil)
53 (nil) 0 1 0x2607490 0x2607560 0x2607620
70 (nil) -1 1 0x2607620 (nil) 0x2607660
80 (nil) 0 1 0x2607660 (nil) (nil)
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeClear : OK.
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeClear : OK.
2024-06-12 16:01:40-P[130201]-T[130201]-[Debug]-AvlTreeDestroy : OK.Performance counter stats for './TestAvl':199 page-faults:u 0.002460665 seconds time elapsed0.000000000 seconds user0.002521000 seconds sys（3）有两棵子树节点
我们之前删除的是40，删除后如上：
| 键值 | 平衡因子 | 备注 |
| 53 | -2 | 删除的是左子树节点，平衡因子减一。 |
| 49 | 还没访问到。 |
不平衡点53的右子树高，我们往右子树探测发现70节点，也是右子树高，这时就可以用RR旋转来进行调整。
| 键值 | 平衡因子 | 备注 |
| 49 | 0 | 删除的是右子树节点，平衡因子加一。 |
代码测试验证：
[gbase@czg2 Exec]$ perf stat -e page-faults ./TestAvl
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeInit : OK.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeAdd : OK, Key : 40, Root Node Key.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeAdd : OK, Key : 20.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeAdd : OK, Key : 53, No Rotation.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeAdd : OK, Key : 18.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeAdd : OK, Key : 49.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeAdd : OK, Key : 70, No Rotation.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeAdd : OK, Key : 80.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreePrint :
Root : 0xa61560
TotalNodeNumsU : 7
TotalNodeNums : 7
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
18 (nil) 0 1 0xa615a0 (nil) (nil)
20 (nil) 1 1 0xa61450 0xa615a0 (nil)
40 (nil) -1 1 0xa61560 0xa61450 0xa61490
49 (nil) 0 1 0xa615e0 (nil) (nil)
53 (nil) -1 1 0xa61490 0xa615e0 0xa61620
70 (nil) -1 1 0xa61620 (nil) 0xa61660
80 (nil) 0 1 0xa61660 (nil) (nil)
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeSearch : OK.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeChgTail : OK.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeRotation : OK, RR.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeDelOne : OK, Key : 40.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreePrint :
Root : 0xa615e0
TotalNodeNumsU : 6
TotalNodeNums : 6
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
18 (nil) 0 1 0xa615a0 (nil) (nil)
20 (nil) 1 1 0xa61450 0xa615a0 (nil)
49 (nil) 0 1 0xa615e0 0xa61450 0xa61620
53 (nil) 0 1 0xa61490 (nil) (nil)
70 (nil) 0 1 0xa61620 0xa61490 0xa61660
80 (nil) 0 1 0xa61660 (nil) (nil)
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeClear : OK.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeClear : OK.
2024-06-12 16:12:59-P[1502]-T[1502]-[Debug]-AvlTreeDestroy : OK.Performance counter stats for './TestAvl':199 page-faults:u 0.001306663 seconds time elapsed0.000000000 seconds user0.001275000 seconds sys四、代码分享
1、AvlTreeDelOne
/*
描述：
1.删除平衡二叉树节点。参数：
1.St : 平衡二叉树节点。
2.Key : 删除的键值。返回值：
1.SUCCESS_FLAG : 成功。
2.FAIL_FLAG : 失败。注意点：
无。*/
Status AvlTreeDelOne(AvlTreeSt *St, Avl2LongT Key)
{JUDGE_NULL_PTR(St);//清理访问路径St->AccessPath.ArrayLen = 0;AvlNodeSt *DelNode = St->Root;//查找删除节点while(DelNode != NULL){if (DelNode->Data.Key == Key){break;}else if(DelNode->Data.Key > Key){AvlAccessPathPush(&(St->AccessPath), DelNode, AVL_LEFT_DIRECTION);DelNode = DelNode->LeftNode;}else{AvlAccessPathPush(&(St->AccessPath), DelNode, AVL_RIGHT_DIRECTION);DelNode = DelNode->RightNode;}}if (DelNode == NULL)//说明没有找到节点{LogFormat(Error,"AvlTreeDelOne : Fail, Key : %lld, No Data.\n",Key);return FAIL_FLAG;}St->TotalNodeNumsU--;St->TotalNodeNums = St->TotalNodeNums - DelNode->Cnt;AvlApSt *AvlApNode = NULL;AvlIntT i = St->AccessPath.ArrayLen;//先作为原始访问路径长度。//找到删除节点，且删除节点没有压入访问路径。//开始删除节点，分情况讨论。//删除的是叶子节点。if ((DelNode->LeftNode == NULL) && (DelNode->RightNode == NULL)){AvlNodeDestroy(&DelNode);//判断是不是拿到了根节点。if (St->AccessPath.ArrayLen == 0)//访问路径为0，说明删除的是根节点。{St->Root = NULL;goto SUCCESS_STAGE;}//拿到访问路径的最后一个节点。AvlApNode = &(St->AccessPath.Array[St->AccessPath.ArrayLen - 1]);//将删除节点的指针置空。(AvlApNode->Direction == AVL_LEFT_DIRECTION)?(AvlApNode->Node->LeftNode = NULL):(AvlApNode->Node->RightNode = NULL);}else if ((DelNode->LeftNode == NULL) || (DelNode->RightNode == NULL))//删除节点有一个叶子节点的情况{//拿到访问路径的最后一个节点。AvlApNode = &(St->AccessPath.Array[St->AccessPath.ArrayLen - 1]);//将父节点的手联想删除节点的叶子节点。switch (AvlApNode->Direction){case AVL_LEFT_DIRECTION:(DelNode->LeftNode == NULL)?(AvlApNode->Node->LeftNode = DelNode->RightNode):(AvlApNode->Node->LeftNode = DelNode->LeftNode);break;case AVL_RIGHT_DIRECTION:(DelNode->LeftNode == NULL)?(AvlApNode->Node->RightNode = DelNode->RightNode):(AvlApNode->Node->RightNode = DelNode->LeftNode);break; default:LogFormat(Error,"AvlTreeDelOne : Fail, Key : %lld, Error Direction.\n",Key);return FAIL_FLAG;}AvlNodeDestroy(&DelNode);}else//删除节点有左右子树。{//我们需要将AVL树扁平化，根据平衡因子来觉得找的是前驱还是后继。if(DelNode->BalanceFactor == 1 || DelNode->BalanceFactor == 0)//1、0，左子树高，找前驱。{//DelNode这边开始作为一个可复用对象。DelNode = AvlTreeChgPre(DelNode, St);}else if (DelNode->BalanceFactor == -1){//DelNode这边开始作为一个可复用对象。DelNode = AvlTreeChgTail(DelNode, St);}else//异常，给的AVL树本就不平衡。{LogFormat(Error,"AvlTreeDelOne : Fail, Key : %lld, The Avl tree is unbalanced.\n",Key);return FAIL_FLAG;}if (St->AccessPath.ArrayLen == 0)//删除的是根节点，且平衡{goto SUCCESS_STAGE;}//如果访问路径长度变化了，下面这段优化效率代码就不适用。if (i != St->AccessPath.ArrayLen){goto BALANCE_STAGE;}//如果新的删除节点也就是替换节点的平衡因子为1或-1，说明是由0变化到这两个值的。//对于新删除节点的父节点，这棵子树的高度是没有变的，所以不需要调整。switch (DelNode->BalanceFactor){case 1:goto SUCCESS_STAGE;case -1:goto SUCCESS_STAGE;default://这里也就是0的情况，说明父节点的这棵子树高度有变化，需要走平衡阶段。break;}}BALANCE_STAGE://前提条件：访问路径最后一个节点的左右子树需要是平衡的，需要注意。//平衡调整阶段。//DelNode这边开始作为一个可复用对象。for ( i = St->AccessPath.ArrayLen - 1; i >= 0; i--){AvlApNode = &(St->AccessPath.Array[i]);AVL_DEL_BALANCE_FACTOR_CHANGE(AvlApNode);switch (AvlApNode->Node->BalanceFactor){case 0:break;case 1://平衡因子是左子树高度减去右子树高度，在删除节点的情况下，是0到1的情况，0说明左右子树是平衡的，//现在右子树删除一个节点，所以变为1，对此节点的父节点，此子树的高度是不变的，所以不需要再平衡//访问路径的其他节点。goto SUCCESS_STAGE;case -1:goto SUCCESS_STAGE; default://不平衡St->AccessPath.ArrayLen = i + 1;//截断到访问路径中不平衡节点，为了后续插入数据。//根据左右子树高度，来判断如何旋转，演化成LL,RR,LR,RL。//例如不平衡点的平衡因子是2，说明左子树高，L，//到左子树后查看平衡因子是1，说明左子树高，L，加起来就是LL旋转。switch (AvlApNode->Node->BalanceFactor){case 2:AvlApNode->Direction = AVL_LEFT_DIRECTION;DelNode = AvlApNode->Node->LeftNode;break;case -2:AvlApNode->Direction = AVL_RIGHT_DIRECTION;DelNode = AvlApNode->Node->RightNode;break; default:LogFormat(Error,"AvlTreeDelOne : Fail, Key : %lld, Balance Rotation Stage 1.\n",Key);return FAIL_FLAG;}if (DelNode->BalanceFactor == 1 || DelNode->BalanceFactor == 0){AvlAccessPathPush(&(St->AccessPath), DelNode, AVL_LEFT_DIRECTION);DelNode = DelNode->LeftNode;}else if(DelNode->BalanceFactor == -1){AvlAccessPathPush(&(St->AccessPath), DelNode, AVL_RIGHT_DIRECTION);DelNode = DelNode->RightNode;}else{LogFormat(Error,"AvlTreeDelOne : Fail, Key : %lld, Balance Rotation Stage 2.\n",Key);return FAIL_FLAG;}AvlAccessPathPush(&(St->AccessPath), DelNode, AVL_RIGHT_DIRECTION);//这个方向无所谓。AvlTreeRotation(St, i);break;}}SUCCESS_STAGE:LogFormat(Debug,"AvlTreeDelOne : OK, Key : %lld.\n",Key);return SUCCESS_FLAG;
}
2、AvlTreeCheck
/*
描述：
1.平衡二叉树检查平衡因子和是否升序，使用中序遍历。参数：
1.Node : 平衡二叉树节点。
2.PreKey : 上一个键值，初始值必须是AVL_KEY_MIN_VAL。
3.CntU : 唯一节点数。初始值必须是0。
4.Cnt : 总节点数。初始值必须是0。返回值：
无。注意点：
效率不高，因为每个节点的平衡因子需要重新计算。
*/
Status AvlTreeCheck(AvlNodeSt *Node, Avl2LongT *PreKey, AvlUllT *CntU, AvlUllT *Cnt)
{if(Node == NULL){return SUCCESS_FLAG;}if(AvlTreeCheck(Node->LeftNode,PreKey,CntU,Cnt) == FAIL_FLAG){return FAIL_FLAG;}AvlIntT DepthL = AvlTreeDepth(Node->LeftNode);AvlIntT DepthR = AvlTreeDepth(Node->RightNode);AvlIntT BalanceFactor = DepthL - DepthR;//判断平衡因子计算是否正确。if (BalanceFactor != Node->BalanceFactor){LogFormat(Error,"AvlTreeCheck : Fail, Key : %lld, BalanceFactor : %d, Correct BalanceFactor : %d.\n",Node->Data.Key,Node->BalanceFactor,BalanceFactor);return FAIL_FLAG;}//判断平衡因子计算是否平衡。if (AVL_JUDGE_BALANCE_FACTOR(Node->BalanceFactor)){LogFormat(Error,"AvlTreeCheck : Fail, Key : %lld, BalanceFactor : %d.\n",Node->Data.Key,BalanceFactor);return FAIL_FLAG;}//中序遍历是否升序。if (Node->Data.Key >= (*PreKey)){*PreKey = Node->Data.Key;}else{LogFormat(Error,"AvlTreeCheck : Fail, Key : %lld, PreKey : %lld, Wrong order.\n",Node->Data.Key,*PreKey);return FAIL_FLAG; }(*CntU)++;(*Cnt) += Node->Cnt;if(AvlTreeCheck(Node->RightNode,PreKey,CntU,Cnt) == FAIL_FLAG){return FAIL_FLAG;}return SUCCESS_FLAG;
}
3、AvlTreeCheckAll
这个函数还是非常YYDS的，这样就不用去肉眼看AVL是否是正确的，解放了。
/*
描述：
1.平衡二叉树检查平衡因子和是否升序。参数：
1.St : 平衡二叉树。返回值：
无。注意点：
效率不高，因为每个节点的平衡因子需要重新计算。
*/
Status AvlTreeCheckAll(AvlTreeSt *St)
{JUDGE_NULL_PTR(St);Avl2LongT PreKey = AVL_KEY_MIN_VAL;AvlUllT CntU = 0;AvlUllT Cnt = 0;if(AvlTreeCheck(St->Root,&PreKey,&CntU,&Cnt) == FAIL_FLAG){Log("AvlTreeCheckAll : Fail.\n",Error);return FAIL_FLAG;}if(St->TotalNodeNums != Cnt){LogFormat(Error,"AvlTreeCheckAll : Fail, TotalNodeNums : %lld, Cnt : %lld.\n",St->TotalNodeNums,Cnt);return FAIL_FLAG;}if(St->TotalNodeNumsU != CntU){LogFormat(Error,"AvlTreeCheckAll : Fail, TotalNodeNumsU : %lld, CntU : %lld.\n",St->TotalNodeNumsU,CntU);return FAIL_FLAG;}Log("AvlTreeCheckAll : OK.\n",Debug);return SUCCESS_FLAG;
}五、虚机测试验证
1、编译
[gbase@czg2 Build]$ rm -rf ../Build/* && cmake ..
-- The C compiler identification is GNU 4.8.5
-- The CXX compiler identification is GNU 4.8.5
-- Check for working C compiler: /bin/cc
-- Check for working C compiler: /bin/cc -- works
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working CXX compiler: /bin/c++
-- Check for working CXX compiler: /bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Configuring done
-- Generating done
-- Build files have been written to: /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Cmake/Build
[gbase@czg2 Build]$ make clean && make
Scanning dependencies of target DataConvertion
[ 4%] Building C object Libs/CMakeFiles/DataConvertion.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/DataConvertion/Src/DataConvertion.c.o
Linking C shared library ../../Libs/libDataConvertion.so
[ 4%] Built target DataConvertion
Scanning dependencies of target FileOperate
[ 9%] Building C object Libs/CMakeFiles/FileOperate.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/FileOperate/Src/FileOperate.c.o
Linking C shared library ../../Libs/libFileOperate.so
[ 9%] Built target FileOperate
Scanning dependencies of target Gbase8aDb
[ 13%] Building C object Libs/CMakeFiles/Gbase8aDb.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Gbase8aDb/Src/Gbase8aDb.c.o
Linking C shared library ../../Libs/libGbase8aDb.so
[ 13%] Built target Gbase8aDb
Scanning dependencies of target HashTable
[ 18%] Building C object Libs/CMakeFiles/HashTable.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/HashTable/Src/MyHashTable.c.o
Linking C shared library ../../Libs/libHashTable.so
[ 18%] Built target HashTable
Scanning dependencies of target LinkList
[ 22%] Building C object Libs/CMakeFiles/LinkList.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/LinkList/Src/DuLinkList.c.o
Linking C shared library ../../Libs/libLinkList.so
[ 22%] Built target LinkList
Scanning dependencies of target Log
[ 27%] Building C object Libs/CMakeFiles/Log.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Log/Src/Log.c.o
Linking C shared library ../../Libs/libLog.so
[ 27%] Built target Log
Scanning dependencies of target MyPool
[ 31%] Building C object Libs/CMakeFiles/MyPool.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/MyPool/Src/ThreadPool.c.o
Linking C shared library ../../Libs/libMyPool.so
[ 31%] Built target MyPool
Scanning dependencies of target MyString
[ 36%] Building C object Libs/CMakeFiles/MyString.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/MyString/Src/KmpSearch.c.o
Linking C shared library ../../Libs/libMyString.so
[ 36%] Built target MyString
Scanning dependencies of target Process
[ 40%] Building C object Libs/CMakeFiles/Process.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Process/Src/MyPipe.c.o
[ 45%] Building C object Libs/CMakeFiles/Process.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Process/Src/MyXsiIpc.c.o
[ 50%] Building C object Libs/CMakeFiles/Process.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Process/Src/Process.c.o
Linking C shared library ../../Libs/libProcess.so
[ 50%] Built target Process
Scanning dependencies of target Pthread
[ 54%] Building C object Libs/CMakeFiles/Pthread.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Pthread/Src/MyThread.c.o
Linking C shared library ../../Libs/libPthread.so
[ 54%] Built target Pthread
Scanning dependencies of target Public
[ 59%] Building C object Libs/CMakeFiles/Public.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Public/Src/PublicFunction.c.o
Linking C shared library ../../Libs/libPublic.so
[ 59%] Built target Public
Scanning dependencies of target Socket
[ 63%] Building C object Libs/CMakeFiles/Socket.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Socket/Src/Socket.c.o
Linking C shared library ../../Libs/libSocket.so
[ 63%] Built target Socket
Scanning dependencies of target SqQueue
[ 68%] Building C object Libs/CMakeFiles/SqQueue.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/SqQueue/Src/SqQueue.c.o
Linking C shared library ../../Libs/libSqQueue.so
[ 68%] Built target SqQueue
Scanning dependencies of target SqStack
[ 72%] Building C object Libs/CMakeFiles/SqStack.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/SqStack/Src/SqStack.c.o
Linking C shared library ../../Libs/libSqStack.so
[ 72%] Built target SqStack
Scanning dependencies of target Tree
[ 77%] Building C object Libs/CMakeFiles/Tree.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Tree/Src/AvlTree.c.o
[ 81%] Building C object Libs/CMakeFiles/Tree.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Tree/Src/HaffmanTree.c.o
Linking C shared library ../../Libs/libTree.so
[ 81%] Built target Tree
Scanning dependencies of target G8aExecutor
[ 86%] Building C object Exec/CMakeFiles/G8aExecutor.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/HappySunshine/Src/G8aExecutor.c.o
Linking C executable /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/HappySunshine/Exec/G8aExecutor
[ 86%] Built target G8aExecutor
Scanning dependencies of target HsManager
[ 90%] Building C object Exec/CMakeFiles/HsManager.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/HappySunshine/Src/HsManager.c.o
Linking C executable /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/HappySunshine/Exec/HsManager
[ 90%] Built target HsManager
Scanning dependencies of target TestAvl
[ 95%] Building C object Exec/CMakeFiles/TestAvl.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Tree/TestSrc/TestAvl.c.o
Linking C executable /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Tree/Exec/TestAvl
[ 95%] Built target TestAvl
Scanning dependencies of target TestHfm
[100%] Building C object Exec/CMakeFiles/TestHfm.dir/opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Tree/TestSrc/TestHfm.c.o
Linking C executable /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Tree/Exec/TestHfm
[100%] Built target TestHfm2、测试代码
#include "AvlTree.h"#define AVL_TEST_ELEMENT_NUMS 10000
#define AVL_TEST_GROUP_NUMS 6//第一个是元素个数
Avl2LongT AvlData[AVL_TEST_GROUP_NUMS][AVL_TEST_ELEMENT_NUMS] = {{6,40,24,53,28,70,60},{6,40,24,53,28,70,80}, {6,40,24,70,28,53,80},{10,5,3,7,1,4,6,8,0,2,9},{10,99,40,24,53,28,70,80,100,101,1},{7,40,20,53,18,49,70,80}};Status main()
{LOG_LEVEL = Debug;AvlTreeSt *AvlTree = NULL;Avl2LongT i;Avl2LongT j;AvlDataSt Data = {0,NULL};AvlNodeSt *RetNode = NULL;AvlTreeInit(&AvlTree);for(i = 0; i < AVL_TEST_GROUP_NUMS; i++){//插入测试for ( j = 1; j <= AvlData[i][0]; j++){Data.Key = AvlData[i][j];AvlTreeAdd(AvlTree, &Data);}AvlTreePrint(AvlTree,Debug);//搜索测试AvlTreeSearch(AvlTree, AvlData[i][1], &RetNode);//删除测试//删除叶子节点测试。AvlTreeDelOne(AvlTree, AvlData[i][AvlData[i][0]]);if(AvlTreeCheckAll(AvlTree) != SUCCESS_FLAG){return FAIL_FLAG;}AvlTreePrint(AvlTree,Debug);//删除只有一个儿子节点测试。可能是可能不是。AvlTreeDelOne(AvlTree, AvlData[i][2]);if(AvlTreeCheckAll(AvlTree) != SUCCESS_FLAG){return FAIL_FLAG;}AvlTreePrint(AvlTree,Debug);AvlTreeDelOne(AvlTree, AvlData[i][3]);if(AvlTreeCheckAll(AvlTree) != SUCCESS_FLAG){return FAIL_FLAG;}AvlTreePrint(AvlTree,Debug);//删除根节点AvlTreeDelOne(AvlTree, AvlData[i][1]);if(AvlTreeCheckAll(AvlTree) != SUCCESS_FLAG){return FAIL_FLAG;}AvlTreePrint(AvlTree,Debug);AvlTreeClear(&AvlTree);}AvlTreeDestroy(&AvlTree);return SUCCESS_FLAG;
}
3、运行结果
[gbase@czg2 Exec]$ perf stat -e page-faults ./TestAvl
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeInit : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 40, Root Node Key.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 24.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 53, No Rotation.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 28.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 70.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeRotation : OK, RL.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 60.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352560
TotalNodeNumsU : 6
TotalNodeNums : 6
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
24 (nil) -1 1 0x2352450 (nil) 0x23525a0
28 (nil) 0 1 0x23525a0 (nil) (nil)
40 (nil) 0 1 0x2352560 0x2352450 0x2352620
53 (nil) 0 1 0x2352490 (nil) (nil)
60 (nil) 0 1 0x2352620 0x2352490 0x23525e0
70 (nil) 0 1 0x23525e0 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeSearch : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeChgPre : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 60.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352560
TotalNodeNumsU : 5
TotalNodeNums : 5
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
24 (nil) -1 1 0x2352450 (nil) 0x23525a0
28 (nil) 0 1 0x23525a0 (nil) (nil)
40 (nil) 0 1 0x2352560 0x2352450 0x2352490
53 (nil) -1 1 0x2352490 (nil) 0x23525e0
70 (nil) 0 1 0x23525e0 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 24.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352560
TotalNodeNumsU : 4
TotalNodeNums : 4
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
28 (nil) 0 1 0x23525a0 (nil) (nil)
40 (nil) -1 1 0x2352560 0x23525a0 0x2352490
53 (nil) -1 1 0x2352490 (nil) 0x23525e0
70 (nil) 0 1 0x23525e0 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 53.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352560
TotalNodeNumsU : 3
TotalNodeNums : 3
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
28 (nil) 0 1 0x23525a0 (nil) (nil)
40 (nil) 0 1 0x2352560 0x23525a0 0x23525e0
70 (nil) 0 1 0x23525e0 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeChgPre : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 40.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x23525a0
TotalNodeNumsU : 2
TotalNodeNums : 2
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
28 (nil) -1 1 0x23525a0 (nil) 0x23525e0
70 (nil) 0 1 0x23525e0 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeClear : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 40, Root Node Key.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 24.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 53, No Rotation.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 28.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 70.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeRotation : OK, RR.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 80.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x23525a0
TotalNodeNumsU : 6
TotalNodeNums : 6
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
24 (nil) -1 1 0x2352560 (nil) 0x2352490
28 (nil) 0 1 0x2352490 (nil) (nil)
40 (nil) 0 1 0x23525a0 0x2352560 0x23525e0
53 (nil) 0 1 0x2352450 (nil) (nil)
70 (nil) 0 1 0x23525e0 0x2352450 0x2352620
80 (nil) 0 1 0x2352620 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeSearch : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 80.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x23525a0
TotalNodeNumsU : 5
TotalNodeNums : 5
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
24 (nil) -1 1 0x2352560 (nil) 0x2352490
28 (nil) 0 1 0x2352490 (nil) (nil)
40 (nil) 0 1 0x23525a0 0x2352560 0x23525e0
53 (nil) 0 1 0x2352450 (nil) (nil)
70 (nil) 1 1 0x23525e0 0x2352450 (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 24.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x23525a0
TotalNodeNumsU : 4
TotalNodeNums : 4
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
28 (nil) 0 1 0x2352490 (nil) (nil)
40 (nil) -1 1 0x23525a0 0x2352490 0x23525e0
53 (nil) 0 1 0x2352450 (nil) (nil)
70 (nil) 1 1 0x23525e0 0x2352450 (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 53.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x23525a0
TotalNodeNumsU : 3
TotalNodeNums : 3
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
28 (nil) 0 1 0x2352490 (nil) (nil)
40 (nil) 0 1 0x23525a0 0x2352490 0x23525e0
70 (nil) 0 1 0x23525e0 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeChgPre : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 40.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352490
TotalNodeNumsU : 2
TotalNodeNums : 2
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
28 (nil) -1 1 0x2352490 (nil) 0x23525e0
70 (nil) 0 1 0x23525e0 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeClear : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 40, Root Node Key.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 24.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 70, No Rotation.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 28.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 53.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 80, No Rotation.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x23525e0
TotalNodeNumsU : 6
TotalNodeNums : 6
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
24 (nil) -1 1 0x2352560 (nil) 0x2352450
28 (nil) 0 1 0x2352450 (nil) (nil)
40 (nil) 0 1 0x23525e0 0x2352560 0x23525a0
53 (nil) 0 1 0x2352490 (nil) (nil)
70 (nil) 0 1 0x23525a0 0x2352490 0x2352620
80 (nil) 0 1 0x2352620 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeSearch : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 80.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x23525e0
TotalNodeNumsU : 5
TotalNodeNums : 5
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
24 (nil) -1 1 0x2352560 (nil) 0x2352450
28 (nil) 0 1 0x2352450 (nil) (nil)
40 (nil) 0 1 0x23525e0 0x2352560 0x23525a0
53 (nil) 0 1 0x2352490 (nil) (nil)
70 (nil) 1 1 0x23525a0 0x2352490 (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 24.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x23525e0
TotalNodeNumsU : 4
TotalNodeNums : 4
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
28 (nil) 0 1 0x2352450 (nil) (nil)
40 (nil) -1 1 0x23525e0 0x2352450 0x23525a0
53 (nil) 0 1 0x2352490 (nil) (nil)
70 (nil) 1 1 0x23525a0 0x2352490 (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 70.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x23525e0
TotalNodeNumsU : 3
TotalNodeNums : 3
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
28 (nil) 0 1 0x2352450 (nil) (nil)
40 (nil) 0 1 0x23525e0 0x2352450 0x2352490
53 (nil) 0 1 0x2352490 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeChgPre : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 40.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352450
TotalNodeNumsU : 2
TotalNodeNums : 2
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
28 (nil) -1 1 0x2352450 (nil) 0x2352490
53 (nil) 0 1 0x2352490 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeClear : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 5, Root Node Key.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 3.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 7, No Rotation.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 1.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 4, No Rotation.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 6.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 8, No Rotation.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 0.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 2, No Rotation.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 9.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352450
TotalNodeNumsU : 10
TotalNodeNums : 10
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
0 (nil) 0 1 0x23526a0 (nil) (nil)
1 (nil) 0 1 0x23525a0 0x23526a0 0x2352700
2 (nil) 0 1 0x2352700 (nil) (nil)
3 (nil) 1 1 0x2352490 0x23525a0 0x23525e0
4 (nil) 0 1 0x23525e0 (nil) (nil)
5 (nil) 0 1 0x2352450 0x2352490 0x2352560
6 (nil) 0 1 0x2352620 (nil) (nil)
7 (nil) -1 1 0x2352560 0x2352620 0x2352660
8 (nil) -1 1 0x2352660 (nil) 0x23528a0
9 (nil) 0 1 0x23528a0 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeSearch : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 9.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352450
TotalNodeNumsU : 9
TotalNodeNums : 9
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
0 (nil) 0 1 0x23526a0 (nil) (nil)
1 (nil) 0 1 0x23525a0 0x23526a0 0x2352700
2 (nil) 0 1 0x2352700 (nil) (nil)
3 (nil) 1 1 0x2352490 0x23525a0 0x23525e0
4 (nil) 0 1 0x23525e0 (nil) (nil)
5 (nil) 1 1 0x2352450 0x2352490 0x2352560
6 (nil) 0 1 0x2352620 (nil) (nil)
7 (nil) 0 1 0x2352560 0x2352620 0x2352660
8 (nil) 0 1 0x2352660 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeChgPre : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 3.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352450
TotalNodeNumsU : 8
TotalNodeNums : 8
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
0 (nil) 0 1 0x23526a0 (nil) (nil)
1 (nil) 1 1 0x23525a0 0x23526a0 (nil)
2 (nil) 1 1 0x2352700 0x23525a0 0x23525e0
4 (nil) 0 1 0x23525e0 (nil) (nil)
5 (nil) 1 1 0x2352450 0x2352700 0x2352560
6 (nil) 0 1 0x2352620 (nil) (nil)
7 (nil) 0 1 0x2352560 0x2352620 0x2352660
8 (nil) 0 1 0x2352660 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeChgPre : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 7.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352450
TotalNodeNumsU : 7
TotalNodeNums : 7
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
0 (nil) 0 1 0x23526a0 (nil) (nil)
1 (nil) 1 1 0x23525a0 0x23526a0 (nil)
2 (nil) 1 1 0x2352700 0x23525a0 0x23525e0
4 (nil) 0 1 0x23525e0 (nil) (nil)
5 (nil) 1 1 0x2352450 0x2352700 0x2352620
6 (nil) -1 1 0x2352620 (nil) 0x2352660
8 (nil) 0 1 0x2352660 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeChgPre : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeRotation : OK, LL.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 5.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x23525e0
TotalNodeNumsU : 6
TotalNodeNums : 6
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
0 (nil) 0 1 0x23526a0 (nil) (nil)
1 (nil) 0 1 0x23525a0 0x23526a0 0x2352700
2 (nil) 0 1 0x2352700 (nil) (nil)
4 (nil) 0 1 0x23525e0 0x23525a0 0x2352620
6 (nil) -1 1 0x2352620 (nil) 0x2352660
8 (nil) 0 1 0x2352660 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeClear : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 99, Root Node Key.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 40.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeRotation : OK, LL.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 24.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 53.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 28.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeRotation : OK, LR.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 70.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 80.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 100, No Rotation.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeRotation : OK, RR.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 101.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 1, No Rotation.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352560
TotalNodeNumsU : 10
TotalNodeNums : 10
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
1 (nil) 0 1 0x23528a0 (nil) (nil)
24 (nil) 0 1 0x23525a0 0x23528a0 0x2352490
28 (nil) 0 1 0x2352490 (nil) (nil)
40 (nil) -1 1 0x2352560 0x23525a0 0x23525e0
53 (nil) 0 1 0x2352450 (nil) (nil)
70 (nil) 0 1 0x2352620 0x2352450 0x2352660
80 (nil) 0 1 0x2352660 (nil) (nil)
99 (nil) 0 1 0x23525e0 0x2352620 0x23526a0
100 (nil) -1 1 0x23526a0 (nil) 0x2352700
101 (nil) 0 1 0x2352700 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeSearch : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 1.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352560
TotalNodeNumsU : 9
TotalNodeNums : 9
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
24 (nil) -1 1 0x23525a0 (nil) 0x2352490
28 (nil) 0 1 0x2352490 (nil) (nil)
40 (nil) -1 1 0x2352560 0x23525a0 0x23525e0
53 (nil) 0 1 0x2352450 (nil) (nil)
70 (nil) 0 1 0x2352620 0x2352450 0x2352660
80 (nil) 0 1 0x2352660 (nil) (nil)
99 (nil) 0 1 0x23525e0 0x2352620 0x23526a0
100 (nil) -1 1 0x23526a0 (nil) 0x2352700
101 (nil) 0 1 0x2352700 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeChgTail : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 40.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352450
TotalNodeNumsU : 8
TotalNodeNums : 8
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
24 (nil) -1 1 0x23525a0 (nil) 0x2352490
28 (nil) 0 1 0x2352490 (nil) (nil)
53 (nil) -1 1 0x2352450 0x23525a0 0x23525e0
70 (nil) -1 1 0x2352620 (nil) 0x2352660
80 (nil) 0 1 0x2352660 (nil) (nil)
99 (nil) 0 1 0x23525e0 0x2352620 0x23526a0
100 (nil) -1 1 0x23526a0 (nil) 0x2352700
101 (nil) 0 1 0x2352700 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeRotation : OK, RL.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 24.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352620
TotalNodeNumsU : 7
TotalNodeNums : 7
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
28 (nil) 0 1 0x2352490 (nil) (nil)
53 (nil) 1 1 0x2352450 0x2352490 (nil)
70 (nil) -1 1 0x2352620 0x2352450 0x23525e0
80 (nil) 0 1 0x2352660 (nil) (nil)
99 (nil) -1 1 0x23525e0 0x2352660 0x23526a0
100 (nil) -1 1 0x23526a0 (nil) 0x2352700
101 (nil) 0 1 0x2352700 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeChgTail : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 99.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352620
TotalNodeNumsU : 6
TotalNodeNums : 6
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
28 (nil) 0 1 0x2352490 (nil) (nil)
53 (nil) 1 1 0x2352450 0x2352490 (nil)
70 (nil) 0 1 0x2352620 0x2352450 0x23526a0
80 (nil) 0 1 0x2352660 (nil) (nil)
100 (nil) 0 1 0x23526a0 0x2352660 0x2352700
101 (nil) 0 1 0x2352700 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeClear : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 40, Root Node Key.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 20.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 53, No Rotation.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 18.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 49.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 70, No Rotation.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeAdd : OK, Key : 80.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352620
TotalNodeNumsU : 7
TotalNodeNums : 7
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
18 (nil) 0 1 0x2352560 (nil) (nil)
20 (nil) 1 1 0x2352450 0x2352560 (nil)
40 (nil) -1 1 0x2352620 0x2352450 0x2352490
49 (nil) 0 1 0x23525a0 (nil) (nil)
53 (nil) -1 1 0x2352490 0x23525a0 0x23525e0
70 (nil) -1 1 0x23525e0 (nil) 0x2352660
80 (nil) 0 1 0x2352660 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeSearch : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 80.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352620
TotalNodeNumsU : 6
TotalNodeNums : 6
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
18 (nil) 0 1 0x2352560 (nil) (nil)
20 (nil) 1 1 0x2352450 0x2352560 (nil)
40 (nil) 0 1 0x2352620 0x2352450 0x2352490
49 (nil) 0 1 0x23525a0 (nil) (nil)
53 (nil) 0 1 0x2352490 0x23525a0 0x23525e0
70 (nil) 0 1 0x23525e0 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 20.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352620
TotalNodeNumsU : 5
TotalNodeNums : 5
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
18 (nil) 0 1 0x2352560 (nil) (nil)
40 (nil) -1 1 0x2352620 0x2352560 0x2352490
49 (nil) 0 1 0x23525a0 (nil) (nil)
53 (nil) 0 1 0x2352490 0x23525a0 0x23525e0
70 (nil) 0 1 0x23525e0 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeChgPre : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 53.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x2352620
TotalNodeNumsU : 4
TotalNodeNums : 4
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
18 (nil) 0 1 0x2352560 (nil) (nil)
40 (nil) -1 1 0x2352620 0x2352560 0x23525a0
49 (nil) -1 1 0x23525a0 (nil) 0x23525e0
70 (nil) 0 1 0x23525e0 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeChgTail : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDelOne : OK, Key : 40.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeCheckAll : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreePrint :
Root : 0x23525a0
TotalNodeNumsU : 3
TotalNodeNums : 3
Key Ptr BalanceFactor Cnt CurNode LeftNode RightNode
18 (nil) 0 1 0x2352560 (nil) (nil)
49 (nil) 0 1 0x23525a0 0x2352560 0x23525e0
70 (nil) 0 1 0x23525e0 (nil) (nil)
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeClear : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeClear : OK.
2024-06-12 16:31:59-P[4471]-T[4471]-[Debug]-AvlTreeDestroy : OK.Performance counter stats for './TestAvl':204 page-faults:u 0.008749709 seconds time elapsed0.001660000 seconds user0.001660000 seconds sys