PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 請問一個演算法的問題

看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間15年前 (2009/10/31 23:58)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/3 (看更多)

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