※ 引述《DJWS (...)》之铭言： : 我有一个演算法的问题。 : 有一棵可以动态增减节点的多元树，一开始是空的。 : 有两个针对此多元树的操作，如下所述： : 操作A: 增加节点 : 给定一个多元树的节点x，以及给定一个要新增的节点y，让y成为x的小孩。 : 这项操作会是O(1)。 : 操作B: 删除节点 : 给定树上两个相异的叶子x和y，令x与y的least common ancestor为z， : 此操作会删除x至z、删除y至z路径上的所有节点（会删除到x与y，但不删除z）。 : 然後x至z、y至z路径上剩余下来的子树，统统接到z上。 : 问题是...请实作操作B， : 让这棵多元树经过多次操作後， : 总共的时间复杂度为O(n)，n为增加节点的次数。 : 先谢谢大家。 :) : - : PS: 这是我最近在研究Edmonds' blossom shrinking algorithm遇到的问题。 操作A，操作O(n)次之後的时间复杂度是O(n) 操作B，假设x~z和y~z的距离分别是h1和h2，那麽至少会删除O(h1+h2)个节点。 如果可以在O(h1+h2)的时间之内完成操作B，就可以了。 每一个Tree Node需要有以下的资料结构： parent pointer：这样从x和y可以在O(h1+h2)的时间内找到z。 children list：以doubly linked list串起来，list node再指向子树。 parent child pointer：指向parent的children list中的属於自己的list node。 x和y利用parent pointer先找到z。 假设p是x的parent，用x的parent child pointer找出p的children list中指向 x的node，把此node删除，接着把此list串到z的children list中。 这样就可以把p除了x之外的子树都接到z上去。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.119.162.50