[理工] [資結]-leftist tree

[nonagoner (哈)]

請問下圖的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
推 gorocky:不用吧!我剛剛看了定義 左邊shortest大於等於右邊的即可
→ nonagoner:謝謝~那看來是解答有問題
→ xrodneylee:要SWAP因為當X=12的時候左子樹比右子樹高度來的低!!
→ nonagoner:不是依shortest值決定要不要SWAP嗎 它也跟AVL一樣看高嗎
推 koehie:shortest(leftChild(x)) >= shortest(rightChild(x))
→ koehie:所以不用 swap