题目描述Gaston\texttt{Gaston}Gaston是一家漫画杂志的员工他最不喜欢的工作是归档邮件。他设计了一个用棍子和线构成的二叉搜索树系统来存放信件每根棍子中间挂一封信左端线下的所有信件编号小于棍子上的信右端线下的所有信件编号大于棍子上的信。该系统形成一棵二叉搜索树便于检索。然而该系统存在平衡问题。Gaston\texttt{Gaston}Gaston规定一根棍子平衡当且仅当其左侧信件数量等于右侧数量或者左侧恰好比右侧多一封即左子树大小等于右子树大小或左子树大小等于右子树大小加一。若右侧比左侧多则视为不平衡。新增信件时从根开始根据编号大小决定向左或向右直至找到空线然后挂上新棍子。随后从根开始自上而下检查所有棍子的平衡情况一旦发现不平衡的棍子就执行一次“平衡步骤”然后重新从根开始检查直至整棵树完全平衡。一次平衡步骤的定义为对于不平衡的棍子sss若右侧较重则从右子树中取出最小信件lnewl_{\text{new}}lnew替换sss上的旧信loldl_{\text{old}}lold并将loldl_{\text{old}}lold插入到左子树的最大位置若左侧过重即左子树大小大于右子树大小加一则从左子树中取出最大信件lnewl_{\text{new}}lnew替换sss上的旧信loldl_{\text{old}}lold并将loldl_{\text{old}}lold插入到右子树的最小位置。每次平衡步骤可能导致其他子树失衡故需反复检查整个树。题目要求给定一棵初始已平衡的二叉搜索树以及一系列待插入的新信件编号计算在整个插入过程中总共需要执行多少次平衡步骤。输入格式第一行一个整数nnn表示测试问题个数。接下来nnn组数据每组包含一行或跨多行描述一棵二叉搜索树的先序表示其中每个节点用一个正整数表示信件编号空子树用000表示。数字之间至少一个空格分隔。下一行一个整数bbb表示将要插入的信件数量。接下来bbb个整数可能跨多行表示依次插入的信件编号1≤l≤10001 \le l \le 10001≤l≤1000。保证初始树是平衡的即满足平衡条件且所有信件编号互不相同。输出格式对于每组测试数据输出一行一个整数表示从开始插入第一封信到插入最后一封信为止总共执行的平衡步骤数。样例输入1 96 0 99 97 0 0 100 0 0 6 43 78 88 86 11 59输出11题目分析本题是一道动态维护平衡二叉搜索树的模拟题。核心操作包括在二叉搜索树中插入一个新节点按照编号大小递归找到空位。判断任意节点的平衡状态左子树大小与右子树大小是否满足sizeleft≥sizerightsize_{\text{left}} \ge size_{\text{right}}sizeleft≥sizeright且sizeleft≤sizeright1size_{\text{left}} \le size_{\text{right}} 1sizeleft≤sizeright1否则视为不平衡。对不平衡节点执行平衡步骤规则固定。每次插入后需要反复扫描整棵树直到所有节点均平衡每次扫描按“根 → 左子树 → 右子树”的顺序检查一旦执行一次平衡步骤立即停止本次扫描重新从根开始下一次扫描。题目给出的初始树已经平衡因此无需在插入前做任何调整。我们需要模拟整个插入过程并累计平衡步骤数。由于编号上限为100010001000总节点数不超过100010001000每次插入后最多可能触发O(O(O(节点数)))次平衡步骤而平衡步骤本身涉及子树遍历查找最值、删除、插入因此总复杂度约为O(b⋅N⋅N)O(b \cdot N \cdot N)O(b⋅N⋅N)其中NNN为最终节点数在100010001000量级下完全可行。解题思路数据结构设计每个节点记录信件编号val。左儿子指针left右儿子指针right。不维护子树大小字段而是在需要判断平衡时通过递归函数getSize实时计算子树大小。虽然这增加了常数开销但避免了因平衡操作后更新size产生遗漏的风险且节点数小性能无碍。核心操作实现插入按照二叉搜索树规则递归插入新节点。计算子树大小递归统计节点个数。平衡判断对某个节点计算左右子树大小若L R或L R 1则执行平衡步骤。平衡步骤若右子树较重L R从右子树中取出最小节点中序后继将其值赋给当前节点删除该最小节点将当前节点的旧值插入到左子树的最大位置即作为左子树的最右节点。若左子树过重L R 1从左子树中取出最大节点中序前驱将其值赋给当前节点删除该最大节点将当前节点的旧值插入到右子树的最小位置即作为右子树的最左节点。每次操作后无需更新任何size字段因为我们实时计算。全局平衡检查定义一个函数balanceCheck从根开始按“根 → 左 → 右”的顺序遍历一旦发现某个节点不平衡立即调用balanceNode执行一次平衡步骤并返回true若整棵树都平衡返回false。主循环对于每组数据读入初始树已平衡然后依次读入每个待插入编号执行insertBST随后循环执行balanceCheck并累加次数直到balanceCheck返回false。正确性说明平衡步骤严格按照题目描述实现保证了二叉搜索树的有序性不被破坏。每次插入后反复扫描整棵树直到全局平衡符合题目要求。实时计算子树大小避免了维护size可能产生的错误确保了平衡判断的准确性。复杂度分析设最终节点数为NNNN≤1000N \le 1000N≤1000每次插入后平衡步骤次数最多为O(N)O(N)O(N)因为每次平衡至少减少一个“逆序”对或类似势能而每次平衡步骤涉及getSizeO(N)O(N)O(N)、查找最值O(N)O(N)O(N)、删除O(N)O(N)O(N)和插入O(N)O(N)O(N)因此单次平衡步骤复杂度为O(N)O(N)O(N)。总复杂度为O(b⋅N⋅N)O(b \cdot N \cdot N)O(b⋅N⋅N)在N≤1000N \le 1000N≤1000时足够快。代码实现// Gaston// UVa ID: 564// Verdict: Accepted// Submission Date: 2026-06-27// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structNode{intval;Node*left,*right;Node(intv):val(v),left(nullptr),right(nullptr){}};// 递归计算子树大小不依赖存储字段实时计算intgetSize(Node*p){if(!p)return0;return1getSize(p-left)getSize(p-right);}// BST 插入不更新 sizevoidinsertBST(Node*p,intv){if(!p){pnewNode(v);return;}if(vp-val)insertBST(p-left,v);elseinsertBST(p-right,v);}// 寻找子树中的最小节点Node*findMin(Node*p){while(pp-left)pp-left;returnp;}// 寻找子树中的最大节点Node*findMax(Node*p){while(pp-right)pp-right;returnp;}// 删除子树中的最小节点并释放内存voiddeleteMin(Node*p){if(!p)return;if(!p-left){Node*tmpp;pp-right;deletetmp;}else{deleteMin(p-left);}}// 删除子树中的最大节点voiddeleteMax(Node*p){if(!p)return;if(!p-right){Node*tmpp;pp-left;deletetmp;}else{deleteMax(p-right);}}// 将值 v 插入到子树 p 中的最大位置作为最右节点voidinsertMax(Node*p,intv){if(!p){pnewNode(v);return;}if(!p-right)p-rightnewNode(v);elseinsertMax(p-right,v);}// 将值 v 插入到子树 p 中的最小位置作为最左节点voidinsertMin(Node*p,intv){if(!p){pnewNode(v);return;}if(!p-left)p-leftnewNode(v);elseinsertMin(p-left,v);}// 对单个节点执行一次平衡步骤返回是否执行了操作boolbalanceNode(Node*p){if(!p)returnfalse;intLgetSize(p-left);intRgetSize(p-right);// 右侧过重左 右if(LR){Node*minNodefindMin(p-right);intoldValp-val;intnewValminNode-val;deleteMin(p-right);// 移除重侧的最小节点p-valnewVal;// 将其值赋给当前节点insertMax(p-left,oldVal);// 旧值插入轻侧最大位置returntrue;}// 左侧过重左 右 1elseif(LR1){Node*maxNodefindMax(p-left);intoldValp-val;intnewValmaxNode-val;deleteMax(p-left);// 移除重侧的最大节点p-valnewVal;// 将其值赋给当前节点insertMin(p-right,oldVal);// 旧值插入轻侧最小位置returntrue;}returnfalse;}// 从当前节点开始按根、左、右顺序检查并执行一次平衡返回是否执行boolbalanceCheck(Node*p){if(!p)returnfalse;if(balanceNode(p))returntrue;if(balanceCheck(p-left))returntrue;if(balanceCheck(p-right))returntrue;returnfalse;}// 读取树的先序表示0 表示空voidreadTree(Node*p){intx;cinx;if(x0){pnullptr;return;}pnewNode(x);readTree(p-left);readTree(p-right);}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;cinn;while(n--){Node*rootnullptr;readTree(root);intsteps0;intb;cinb;for(inti0;ib;i){intval;cinval;insertBST(root,val);// 插入后反复平衡直至整棵树满足条件while(balanceCheck(root))steps;}coutsteps\n;// 此处可递归释放内存但非必须}return0;}总结模拟题的关键是严格按照题目描述的流程实现每一步特别是平衡步骤中“从重侧取最值”以及“旧值插入轻侧最值位置”的细节必须保证二叉搜索树的有序性不被破坏。平衡判断采用实时递归计算子树大小简化了维护逻辑虽然牺牲了一点性能但在数据规模较小N≤1000N \le 1000N≤1000时完全可行且降低了编码出错概率。全局扫描采用“根 → 左 → 右”的顺序每次只执行一次平衡步骤后立即重新扫描符合题目“重复从顶部检查直到全部平衡”的要求。初始树平衡题目保证初始树已平衡因此不需要在插入前进行平衡否则会导致步骤计数错误实际评测数据也证实了这一点。内存管理本程序未显式释放节点但程序运行完即结束对于竞赛题目可接受。若需严谨可编写递归释放函数。本题训练了对二叉树操作的熟练掌握以及模拟复杂流程的能力。
