作者DJWS (...)
站内Prob_Solve
标题[问题] 请问一个演算法
时间Sat Oct 31 19:45:34 2009
我有一个演算法的问题。
有一棵可以动态增减节点的多元树，一开始是空的。
有两个针对此多元树的操作，如下所述：
操作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遇到的问题。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.137.73.157
※ 编辑: DJWS 来自: 220.137.73.157 (10/31 21:23)