← 返回起始笔记位置

知识卡片

普通读书笔记卡 · 3636

动态树维护可修改的树森林

理解等级:中级

动态树维护带边成本的多棵互不相交有根树,支持根与父节点查询、路径最小边成本查询、切边、连树和路径成本更新。

原文给出一种实现每项操作O(lg n)摊还界,复杂实现则有O(lg n)最坏界。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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.

    参考来源

    - 位置:《算法导论(第4版)》第五部分引言《高级数据结构》(OEBPS/part005.xhtml,文本字符[0,5000))。 - 结论依据:原文列出动态树的查询和结构更新,并区分简单实现的摊还界与复杂实现的最坏界。 - 原始内容: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.