推 kiwidoit:作法2 01/05 16:25
→ a613204:請問那搜尋的節點不在樹中,那會調整哪個節點呢? 01/05 18:37
→ a613204:是沿著搜尋路徑下來的最後一個節點嗎? 01/05 18:38
推 kiwidoit:沒錯 01/07 17:48
想請問一下Splay tree的刪除
不太懂刪除的時候是要從哪個節點開始調起
書上面寫從實質刪除節點的父節點開始
依照二元搜尋樹刪除的規則 , 若要刪除的節點有兩個子樹的話 , 則用左子數最大的鍵值
, 或是右子樹最小的鍵值來取代 , 然後退化成刪除樹葉節點或者是只有一個子樹的情況
30
/
10
/ \
6 18
/ \ / \
4 8 13 25
/ \
3 5
假設要刪除6
作法1 : 先用二元搜尋樹刪除的規則將6刪除 ,
從6的父節點10開始調(就直接找該刪除點的父節點)
作法2 : 先用二元搜尋樹刪除的規則將6刪除 , 若採用左子樹最大鍵值來取代
則用5來取代6 , 將原本5的位置刪除 , 因為5的父節點是4 , 所以從4開始調
想請問哪個做法才是對的??
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.0.42.10