[問題] 請問一個演算法的問題
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間15年前 (2009/10/31 19:45)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/3 (看更多)
我有一個演算法的問題。
有一棵可以動態增減節點的多元樹，一開始是空的。
有兩個針對此多元樹的操作，如下所述：
操作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)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
