作者nonagoner (哈)
看板Grad-ProbAsk
標題[理工] [資結]-leftist tree
時間Thu Feb 11 13:56:46 2010
請問下圖的leftist tree附上shostest(x)，依定義左子沒有小於右子是不是不用SWAP?
2(12)
/ \
1(18) (24)1
/
1(33)
可是解答上寫要SWAP成下圖
2(12)
/ \
1(24) (18)1
/
1(33)
請問到底要不要SWAP呢?謝謝~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.142.91
1F：推 gorocky:不用吧!我剛剛看了定義 左邊shortest大於等於右邊的即可 02/11 14:26
2F：→ nonagoner:謝謝~那看來是解答有問題 02/11 14:57
3F：→ xrodneylee:要SWAP因為當X=12的時候左子樹比右子樹高度來的低!! 02/12 00:25
4F：→ nonagoner:不是依shortest值決定要不要SWAP嗎 它也跟AVL一樣看高嗎 02/13 15:34
5F：推 koehie:shortest(leftChild(x)) >= shortest(rightChild(x)) 01/03 03:36
6F：→ koehie:所以不用 swap 01/03 03:36