企业官网建设流程全解析

题目描述

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≤sizeright+1size_{\text{left}} \le size_{\text{right}} + 1sizeleft​≤sizeright​+1，否则视为不平衡。
• 对不平衡节点执行平衡步骤（规则固定）。
• 每次插入后，需要反复扫描整棵树，直到所有节点均平衡，每次扫描按“根 → 左子树 → 右子树”的顺序检查，一旦执行一次平衡步骤，立即停止本次扫描，重新从根开始下一次扫描。

题目给出的初始树已经平衡，因此无需在插入前做任何调整。我们需要模拟整个插入过程，并累计平衡步骤数。

由于编号上限为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产生遗漏的风险，且节点数小，性能无碍。

核心操作实现

1. 插入：按照二叉搜索树规则递归插入新节点。
2. 计算子树大小：递归统计节点个数。
3. 平衡判断：对某个节点，计算左右子树大小，若L < R或L > R + 1，则执行平衡步骤。
4. 平衡步骤：
   • 若右子树较重（L < R）：从右子树中取出最小节点（中序后继），将其值赋给当前节点；删除该最小节点；将当前节点的旧值插入到左子树的最大位置（即作为左子树的最右节点）。
   • 若左子树过重（L > R + 1）：从左子树中取出最大节点（中序前驱），将其值赋给当前节点；删除该最大节点；将当前节点的旧值插入到右子树的最小位置（即作为右子树的最左节点）。
   • 每次操作后，无需更新任何size字段（因为我们实时计算）。
5. 全局平衡检查：定义一个函数balanceCheck，从根开始按“根 → 左 → 右”的顺序遍历，一旦发现某个节点不平衡，立即调用balanceNode执行一次平衡步骤，并返回true；若整棵树都平衡，返回false。
6. 主循环：对于每组数据，读入初始树（已平衡），然后依次读入每个待插入编号，执行insertBST，随后循环执行balanceCheck并累加次数，直到balanceCheck返回false。

正确性说明

• 平衡步骤严格按照题目描述实现，保证了二叉搜索树的有序性不被破坏。
• 每次插入后反复扫描整棵树，直到全局平衡，符合题目要求。
• 实时计算子树大小，避免了维护size可能产生的错误，确保了平衡判断的准确性。

复杂度分析

设最终节点数为NNN（N≤1000N \le 1000N≤1000），每次插入后，平衡步骤次数最多为O(N)O(N)O(N)（因为每次平衡至少减少一个“逆序”对或类似势能），而每次平衡步骤涉及getSize（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(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//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structNode{intval;Node*left,*right;Node(intv):val(v),left(nullptr),right(nullptr){}};// 递归计算子树大小（不依赖存储字段，实时计算）intgetSize(Node*p){if(!p)return0;return1+getSize(p->left)+getSize(p->right);}// BST 插入（不更新 size）voidinsertBST(Node*&p,intv){if(!p){p=newNode(v);return;}if(v<p->val)insertBST(p->left,v);elseinsertBST(p->right,v);}// 寻找子树中的最小节点Node*findMin(Node*p){while(p&&p->left)p=p->left;returnp;}// 寻找子树中的最大节点Node*findMax(Node*p){while(p&&p->right)p=p->right;returnp;}// 删除子树中的最小节点（并释放内存）voiddeleteMin(Node*&p){if(!p)return;if(!p->left){Node*tmp=p;p=p->right;deletetmp;}else{deleteMin(p->left);}}// 删除子树中的最大节点voiddeleteMax(Node*&p){if(!p)return;if(!p->right){Node*tmp=p;p=p->left;deletetmp;}else{deleteMax(p->right);}}// 将值 v 插入到子树 p 中的最大位置（作为最右节点）voidinsertMax(Node*&p,intv){if(!p){p=newNode(v);return;}if(!p->right)p->right=newNode(v);elseinsertMax(p->right,v);}// 将值 v 插入到子树 p 中的最小位置（作为最左节点）voidinsertMin(Node*&p,intv){if(!p){p=newNode(v);return;}if(!p->left)p->left=newNode(v);elseinsertMin(p->left,v);}// 对单个节点执行一次平衡步骤，返回是否执行了操作boolbalanceNode(Node*&p){if(!p)returnfalse;intL=getSize(p->left);intR=getSize(p->right);// 右侧过重（左 < 右）if(L<R){Node*minNode=findMin(p->right);intoldVal=p->val;intnewVal=minNode->val;deleteMin(p->right);// 移除重侧的最小节点p->val=newVal;// 将其值赋给当前节点insertMax(p->left,oldVal);// 旧值插入轻侧（最大位置）returntrue;}// 左侧过重（左 > 右 + 1）elseif(L>R+1){Node*maxNode=findMax(p->left);intoldVal=p->val;intnewVal=maxNode->val;deleteMax(p->left);// 移除重侧的最大节点p->val=newVal;// 将其值赋给当前节点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;cin>>x;if(x==0){p=nullptr;return;}p=newNode(x);readTree(p->left);readTree(p->right);}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;cin>>n;while(n--){Node*root=nullptr;readTree(root);intsteps=0;intb;cin>>b;for(inti=0;i<b;++i){intval;cin>>val;insertBST(root,val);// 插入后反复平衡直至整棵树满足条件while(balanceCheck(root))++steps;}cout<<steps<<'\n';// 此处可递归释放内存，但非必须}return0;}

总结

• 模拟题的关键是严格按照题目描述的流程实现每一步，特别是平衡步骤中“从重侧取最值”以及“旧值插入轻侧最值位置”的细节，必须保证二叉搜索树的有序性不被破坏。
• 平衡判断采用实时递归计算子树大小，简化了维护逻辑，虽然牺牲了一点性能，但在数据规模较小（N≤1000N \le 1000N≤1000）时完全可行，且降低了编码出错概率。
• 全局扫描采用“根 → 左 → 右”的顺序，每次只执行一次平衡步骤后立即重新扫描，符合题目“重复从顶部检查直到全部平衡”的要求。
• 初始树平衡：题目保证初始树已平衡，因此不需要在插入前进行平衡，否则会导致步骤计数错误（实际评测数据也证实了这一点）。
• 内存管理：本程序未显式释放节点，但程序运行完即结束，对于竞赛题目可接受。若需严谨，可编写递归释放函数。

本题训练了对二叉树操作的熟练掌握，以及模拟复杂流程的能力。