局部重建

范式与三项证明义务 ​

设动态结构的每个区域 $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 不在每次插入后旋转，而要求搜索路径深度不超过约

$${\log }_{1/\alpha }q,$$

其中 $q$ 是自最近一次全局清理以来的规模上界。若新叶过深，沿祖先向上找第一个满足

$$size(child)>\alpha size(parent)$$

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

重建后，$w$ 的两个孩子大小至多约 $size(w)/2$。要再次使某个孩子超过 $\alpha size(w)$，该区域必须经历 $\mathrm{\Omega }((\alpha -1/2)size(w))$ 次净插入或删除；这些更新各存常数信用，即可支付 $\mathrm{\Theta }(size(w))$ 的重建。

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

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

例如一个含 $15$ 个键的子树重建成两侧各约 $7$ 个键。取 $\alpha =2/3$，某一侧需增长到超过 $10$ 才再次失衡，至少要有四次影响该侧的更新；常数因子按重建实现调整，但“离阈值有线性距离”是必要事实。

Subtree、Bucket 与增量重建 ​

Subtree rebuild 替换一棵失衡子树；bucket rebuild 只整理某个叶桶、哈希桶或块内数组；二者的收费对象分别是经过祖先的更新和落入该桶的更新。触发事件与被收费操作必须匹配，不能让另一区域的更新虚构信用。

增量重建把 $\mathrm{\Theta }(s)$ 工作拆到后续操作中，并在迁移期间同时维护旧、新版本或更新日志。它进一步进入去摊还化公理库去摊还化Deamortization把偶发的大工作拆成有预算的增量步骤，使逐操作延迟获得最坏界。：除总工作足够外，还要证明每次固定预算能在下一次触发前完成，查询也能在双版本状态中保持正确。

与全局重建的区分 ​

全局重建公理库全局重建Global rebuilding在坏度量越界时从活动元素重建结构，并把线性成本收费给足够多次更新。用一次扫描恢复整个容器，收费通常来自全局规模或负载的几何变化。局部重建只触及坏区域，能避免无关数据停顿，却引入祖先重叠和局部阈值的证明负担。

旋转是常数规模的持续修复；局部重建是线性于区域大小的间歇修复。Weight-balanced tree、scapegoat tree 与分桶索引可能在两者之间取舍，但不能把它们的最坏或摊还界混写。

失败边界 ​

若重建后仍贴着触发阈值，下一次更新就可能再次花 $\mathrm{\Theta }(s)$。若寻找 scapegoat 本身要扫描整个结构，或收集活动元素还遍历无界历史日志，局部收费也无法支付额外工作。

删除还可能让许多嵌套区域同时稀疏。必须规定选择最小、最高还是第一个坏祖先，并证明未选区域的坏度量不会失控。持久化结构中的旧版本不能贡献给新版本可重复消费的同一信用。

参考资料

• Igal Galperin and Ronald L. Rivest, “Scapegoat Trees,” SODA, 1993.
• Mark H. Overmars, The Design of Dynamic Data Structures, Springer, 1983.
• Arne Andersson, “Balanced Search Trees Made Simple,” WADS, 1993.