[理工] 資料結構 ΑVL tree

看板Grad-ProbAsk作者 (18號)時間8年前 (2017/10/03 18:56), 8年前編輯推噓6(6推 0噓 12→)
留言18則, 4人參與, 8年前最新討論串1/1
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
推
10/03 20:48, 8年前 , 1F
定義是左右子樹高度差
10/03 20:48, 1F
→
10/03 20:48, 8年前 , 2F
左子樹高度=5 右子樹高度=4
10/03 20:48, 2F
→
10/03 20:48, 8年前 , 3F
所以沒問題吧
10/03 20:48, 3F
→
10/03 21:52, 8年前 , 4F
沒問題的是答案還是我畫的XD
10/03 21:52, 4F
推
10/03 22:11, 8年前 , 5F
答案沒問題 你畫的也沒問題
10/03 22:11, 5F
→
10/03 22:11, 8年前 , 6F
AVL tree的定義是|左右子樹高度差|<=1 且左右子樹也是AV
10/03 22:11, 6F
→
10/03 22:11, 8年前 , 7F
L tree
10/03 22:11, 7F
→
10/03 22:11, 8年前 , 8F
左子樹高度是5 右子樹高度是4
10/03 22:11, 8F
→
10/03 22:11, 8年前 , 9F
相差=1 分別看也都符合AVL tree
10/03 22:11, 9F
→
10/03 22:43, 8年前 , 10F
可是我找到選項的反例為何還是true?
10/03 22:43, 10F
推
10/03 23:02, 8年前 , 11F
你畫的不是反例
10/03 23:02, 11F
推
10/03 23:31, 8年前 , 12F
difference of “any pair” of leaves
10/03 23:31, 12F
→
10/03 23:31, 8年前 , 13F
感覺是答案的問題
10/03 23:31, 13F
→
10/03 23:47, 8年前 , 14F
s10 大 為何不是反例呢?
10/03 23:47, 14F
→
10/03 23:47, 8年前 , 15F
兩個藍色點都是leaf
10/03 23:47, 15F
推
10/04 00:16, 8年前 , 16F
真的欸 對不起我誤會你的意思了QQ
10/04 00:16, 16F
推
10/04 13:01, 8年前 , 17F
他的意思可能是一對子葉對一對子葉高度差一。 你畫
10/04 13:01, 17F
→
10/04 13:01, 8年前 , 18F
的是一顆節點對節點
10/04 13:01, 18F
‣ 更多 can18 的文章
文章代碼(AID): #1PqspSoh (Grad-ProbAsk)