[理工] [資結]-leftist tree

看板Grad-ProbAsk作者 (哈)時間16年前 (2010/02/11 13:56), 編輯推噓2(2推 0噓 4→)
留言6則, 4人參與, 最新討論串1/1
請問下圖的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
推
02/11 14:26, , 1F
不用吧!我剛剛看了定義 左邊shortest大於等於右邊的即可
02/11 14:26, 1F
→
02/11 14:57, , 2F
謝謝~那看來是解答有問題
02/11 14:57, 2F
→
02/12 00:25, , 3F
要SWAP因為當X=12的時候左子樹比右子樹高度來的低!!
02/12 00:25, 3F
→
02/13 15:34, , 4F
不是依shortest值決定要不要SWAP嗎 它也跟AVL一樣看高嗎
02/13 15:34, 4F
推
01/03 03:36, , 5F
shortest(leftChild(x)) >= shortest(rightChild(x))
01/03 03:36, 5F
→
01/03 03:36, , 6F
所以不用 swap
01/03 03:36, 6F
‣ 更多 nonagoner 的文章
文章代碼(AID): #1BSvmWpZ (Grad-ProbAsk)