目录
一、知识点回顾
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 elapsed
0.000000000 seconds user
0.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 elapsed
0.000000000 seconds user
0.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 elapsed
0.000000000 seconds user
0.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 elapsed
0.001660000 seconds user
0.001660000 seconds sys
![[终端安全]-7 后量子密码算法](https://i-blog.csdnimg.cn/direct/dbbe4ec736f04469bb82618067756506.png)
