[理工] 資料結構 ΑVL tree can18 PTT批踢踢實業坊

[理工] 資料結構 ΑVL tree

作者: can18 (18號) 2017-10-03 18:56:26

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
請問是答案錯誤還是我畫錯了呢

作者: s1020824 (HowardW) 2017-10-03 20:48:00

定義是左右子樹高度差左子樹高度=5 右子樹高度=4所以沒問題吧

作者: can18 (18號) 2017-10-03 21:52:00

沒問題的是答案還是我畫的XD

作者: s1020824 (HowardW) 2017-10-03 22:11:00

答案沒問題你畫的也沒問題AVL tree的定義是|左右子樹高度差|<=1 且左右子樹也是AVL tree左子樹高度是5 右子樹高度是4相差=1 分別看也都符合AVL tree

作者: can18 (18號) 2017-10-03 22:43:00

可是我找到選項的反例為何還是true?

作者: s1020824 (HowardW) 2017-10-03 23:02:00

你畫的不是反例

作者: sarsman (DeNT15T♠) 2017-10-03 23:31:00

difference of “any pair” of leaves感覺是答案的問題

作者: can18 (18號) 2017-10-03 23:47:00

s10 大為何不是反例呢?兩個藍色點都是leaf

作者: s1020824 (HowardW) 2017-10-04 00:16:00

真的欸對不起我誤會你的意思了QQ

作者: kobebset105 (小小小妹) 2017-10-04 13:01:00

他的意思可能是一對子葉對一對子葉高度差一。你畫的是一顆節點對節點

繼續閱讀

Re: [理工] 拉氏逆轉換Honor1984 [理工] 拉氏逆轉換ab4010800 [理工] 張凡計組p.513 multiple issueclonsey1314 [理工] [線代] 黃子嘉2-51範例4s90210jackle [理工] 計組第四章練習題bobsonlin [理工] 資料結構Quick sortlovepipi [理工] 離散子群證明問題s1020824 [計組]96政大資科-virtual address cacheking8313 [理工] 計組程序呼叫概念ahahahahah [理工] 線代 eigenvalue 個數jerry900287