※ 引述《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