看板 [ Prob_Solve ]
討論串[問題] 請問一個演算法的問題
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 請問一個演算法的問題
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者DJWS (...)時間15年前 (2009/10/31 19:45), 編輯資訊
1
0
0
內容預覽:
我有一個演算法的問題。. 有一棵可以動態增減節點的多元樹，一開始是空的。. 有兩個針對此多元樹的操作，如下所述：. 操作A: 增加節點. 給定一個多元樹的節點x，以及給定一個要新增的節點y，讓y成為x的小孩。. 這項操作會是O(1)。. 操作B: 刪除節點. 給定樹上兩個相異的葉子x和y，令x與y的
(還有180個字)
#2
Re: [問題] 請問一個演算法的問題
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者FRAXIS (喔喔)時間15年前 (2009/10/31 23:58), 編輯資訊
1
0
0
內容預覽:
操作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可
(還有185個字)
#3
Re: [問題] 請問一個演算法的問題
推噓0(0推 0噓 1→)留言1則，0人參與, 最新作者DJWS (...)時間15年前 (2009/11/01 10:03), 編輯資訊
0
0
0
內容預覽:
「x和y利用parent pointer先找到z，在O(h1+h2)的時間之內完成。」. 這件事情要怎麼實作呢?. 這也是我最大的問題 XD. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 220.137.80.26.
首頁
上一頁
1
下一頁
尾頁