作者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