局部重建

形式陈述 ​

范式与三项证明义务 ​

设动态结构的每个区域 $C$ 有规模 $s(C)$ 和坏度量 $b(C)$。局部重建在 $b(C)$ 越过阈值时，用 $R(s)=\mathrm{\Theta }(s)$ 时间从 $C$ 的活动元素重新构造一个满足强不变量的版本，而不扫描结构其余部分。

一个完整分析必须给出三项内容：触发阈值是什么；重建后恢复到离阈值多远；从上次恢复到本次触发之间，至少发生了多少次能向该区域收费的更新。若只说“偶尔平衡一下”，就没有摊还证明。

在搜索树实例中，可用搜索树增强理路搜索树增强定理与方法Search-tree augmentation区分可逐层重算的子树摘要与旋转后只需局部修复的中序聚合，并据此维护增强搜索树。维护子树大小等摘要；桶密度或墓碑数则按相应区域的表示维护。重建会替换一整片内部表示，父节点指向新根后仍须自底向上修复祖先摘要。

Scapegoat Tree 主例子 ​

固定 $\alpha \in (1/2,1)$。Scapegoat tree 不在每次插入后旋转，而要求搜索路径深度不超过约

这里明确维护当前键数 $n$ 和规模上界 $q$：插入后令 $q\leftarrow max(q,n)$；删除使 $n<q/2$ 时重建整树并令 $q=n$，空树直接复位。于是非空时 $n\le q\le 2n$，深度关于 $q$ 的界也就是关于当前 $n$ 的对数界。本例另维护每个节点的子树大小，便于沿搜索路径检查阈值。若新叶过深，沿祖先向上找第一个满足

的 scapegoat 节点 $w$，把 $w$ 的全部键按中序收集，再建成近乎完全平衡的子树。

重建后，$w$ 的两个孩子大小至多约 $size(w)/2$。要再次使某个孩子超过 $\alpha size(w)$，该区域必须经历线性数量的插入或删除；收费按实际更新次数，不按可能互相抵消的净变化数。以重建时大小 $s$ 为基准，经过 $u$ 次更新，某个孩子至多有 $s/2+u$ 项，总大小至少为 $s-u$。越过阈值要求 $s/2+u>\alpha (s-u)$，故 $u>(\alpha -1/2)s/(1+\alpha )=\mathrm{\Omega }(s)$，其中 $\alpha$ 固定。这些更新各存常数信用，即可支付 $\mathrm{\Theta }(size(w))$ 的重建。

祖先收费为何只有对数层 ​

一次更新可能给搜索路径上多个候选区域增加坏度量。若平衡不变量保证树高 $O(\log n)$，把常数信用放到每个祖先，总收费为 $O(\log n)$。当某个子树重建时，只消费属于该子树、且在上次重建后积累的信用，不能同时拿同一笔更新替两个重叠区域付款。

例如一个含 $15$ 个键的子树，两侧各有 $7$ 个键。取 $\alpha =2/3$，若只向左侧插入，条件是 $(7+u)/(15+u)>2/3$，至少需要 $u=10$ 次；九次时恰为 $2/3$，还未越界。若只删右侧，条件是 $7/(15-u)>2/3$，至少需要五次。每次更新同时改变分子或分母，不能把原来的总大小15冻结后计算触发点。