資結 AVL tree 問題

看板Grad-ProbAsk作者 (mloop)時間9年前 (2016/08/01 15:57), 編輯推噓0(0推 0噓 17→)
留言17則, 3人參與, 最新討論串1/1
http://i.imgur.com/7r7RuqD.jpg
我想請問一下C選項 答案是給說正確 但是在AVL樹 應該的確是存在有高度差超過1的Leaves 例如這棵 http://i.imgur.com/q2v1Y4o.jpg
想請問是我想法哪裡有誤 ----- Sent from JPTT on my HTC_D816x. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.89.128 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1470038230.A.CCC.html
→
08/01 16:36, , 1F
AVL tree不會有高度差超過1，是指左子樹和右子樹的
08/01 16:36, 1F
→
08/01 16:36, , 2F
高度差
08/01 16:36, 2F
→
08/01 17:03, , 3F
我是想問選項C 因為選項的意思看起來是 任兩個Leaves的高
08/01 17:03, 3F
→
08/01 17:03, , 4F
度不超過1 但應該是可以
08/01 17:03, 4F
→
08/01 17:07, , 5F
針對每個節點，左右子樹高度差小於等於1，你去檢視
08/01 17:07, 5F
→
08/01 17:07, , 6F
那顆樹的每個節點就會發現其實他高度差沒有超過1
08/01 17:07, 6F
→
08/01 17:08, , 7F
哦哦！沒看清楚...
08/01 17:08, 7F
→
08/01 17:10, , 8F
那我也覺得可以...
08/01 17:10, 8F
→
08/01 17:23, , 9F
第二張圖還沒平衡過 不算AVL TREE
08/01 17:23, 9F
→
08/01 17:26, , 10F
正確AVL TREE的balanceFcator∈{-1,0,1} 題目無誤
08/01 17:26, 10F
→
08/01 17:43, , 11F
08/01 17:43, 11F
→
08/01 17:43, , 12F
這樣子看起來應該是不需要調整吧
08/01 17:43, 12F
→
08/01 17:47, , 13F
08/01 17:47, 13F
→
08/01 17:47, , 14F
然後根據高度5最小棵的AVL樹 畫出來是長這樣 所以應該樹是
08/01 17:47, 14F
→
08/01 17:47, , 15F
正確的
08/01 17:47, 15F
→
08/01 17:50, , 16F
你說的有理QQ 那我覺得問題應該是any pair of leaves
08/01 17:50, 16F
→
08/01 17:50, , 17F
題目在玩文字遊戲了
08/01 17:50, 17F
‣ 更多 mloop 的文章
文章代碼(AID): #1Ndm3MpC (Grad-ProbAsk)