資結 AVL tree 問題 mloop PTT批踢踢實業坊

作者: mloop (mloop) 2016-08-01 15:57:08

http://i.imgur.com/7r7RuqD.jpg
我想請問一下C選項答案是給說正確
但是在AVL樹應該的確是存在有高度差超過1的Leaves
例如這棵
http://i.imgur.com/q2v1Y4o.jpg
想請問是我想法哪裡有誤

作者: ken52011219 (呱) 2016-08-01 17:23:00

第二張圖還沒平衡過不算AVL TREE正確AVL TREE的balanceFcator∈{-1,0,1} 題目無誤

作者: gary19941208 2016-08-01 17:07:00

針對每個節點，左右子樹高度差小於等於1，你去檢視那顆樹的每個節點就會發現其實他高度差沒有超過1哦哦！沒看清楚...那我也覺得可以...

作者: ken52011219 (呱) 2016-08-01 17:50:00

你說的有理QQ 那我覺得問題應該是any pair of leaves題目在玩文字遊戲了

作者: mloop (mloop) 2016-08-01 17:43:00

http://i.imgur.com/pizadRh.jpg這樣子看起來應該是不需要調整吧http://i.imgur.com/x9e3REm.jpg然後根據高度5最小棵的AVL樹畫出來是長這樣所以應該樹是正確的

作者: mloop (mloop) 2016-08-01 17:03:00

我是想問選項C 因為選項的意思看起來是任兩個Leaves的高度不超過1 但應該是可以

作者: gary19941208 2016-08-01 16:36:00

AVL tree不會有高度差超過1，是指左子樹和右子樹的高度差

繼續閱讀