知识卡片
动态树维护可修改的树森林
动态树维护带边成本的多棵互不相交有根树,支持根与父节点查询、路径最小边成本查询、切边、连树和路径成本更新。
原文给出一种实现每项操作O(lg n)摊还界,复杂实现则有O(lg n)最坏界。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第五部分 高级数据结构 · 查看原书依据
Dynamic trees [415, 429] maintain a forest of disjoint rooted trees. Each edge in each tree has a real-valued cost. Dynamic trees support queries to find parents, roots, edge costs, and the minimum edge cost on a simple path from a node up to a root. Trees may be manipulated by cutting edges, updating all edge costs on a simple path from a node up to a root, linking a root into another tree, and making a node the root of the tree it appears in. One implementation of dynamic trees gives an O(lg n) amortized time bound for each operation, while a more complicated implementation yields O(lg n) worst-case time bounds.