[理工] 資料結構 ΑVL tree

[can18 (18號)]

https://i.imgur.com/SdBExgu.jpg

第三題的 C 選項

the level difference of any pair of leaves is at most one

答案給true

可是我找到的反例(AVL tree)
https://i.imgur.com/bABAbbJ.jpg
藍點 level 差了2

請問是答案錯誤還是我畫錯了呢

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.119.121.6
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1507028188.A.CAB.html
※ 編輯: can18 (140.119.121.6), 10/03/2017 19:00:54
推 s1020824: 定義是左右子樹高度差
→ s1020824: 左子樹高度=5  右子樹高度=4
→ s1020824: 所以沒問題吧
→ can18: 沒問題的是答案還是我畫的XD
推 s1020824: 答案沒問題 你畫的也沒問題
→ s1020824: AVL tree的定義是|左右子樹高度差|<=1 且左右子樹也是AV
→ s1020824: L tree
→ s1020824: 左子樹高度是5 右子樹高度是4
→ s1020824: 相差=1 分別看也都符合AVL tree
→ can18: 可是我找到選項的反例為何還是true?
推 s1020824: 你畫的不是反例
推 sarsman: difference of “any pair” of leaves
→ sarsman: 感覺是答案的問題
→ can18: s10 大 為何不是反例呢?
→ can18: 兩個藍色點都是leaf
推 s1020824: 真的欸 對不起我誤會你的意思了QQ
推 kobebset105: 他的意思可能是一對子葉對一對子葉高度差一。  你畫
→ kobebset105: 的是一顆節點對節點