[理工] AVL Tree T/F
您好，問題如下:
Which statement(s) is correct for an AVL Tree?
(1) The absolute value of the level difference of any two leaves is at most
one.
(2) The absolute value of the height difference of any two subtrees on the
same level is at most one.
(3) A deletion needs at most two rotation operations to preserve an AVL Tree
to be a height-balanced tree.
(4) After a new node is inserted, the tree height will not increase if
rotation operations are performed.
Ans: (D)
(1)反例 https://imgur.com/e5AyByL
--> 6和30的高度差2
Q: 為什麼(2)的敘述是錯誤的?
在"相同的Level"的"任意2個子樹"的高度差最多差1。
不知道有沒有反例可以舉出來。
更新:謝謝提醒，我發現(1)的反例也是(2)的反例。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.126.33.178 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1577959620.A.E08.html
→
01/02 18:10,
6年前
, 1F
01/02 18:10, 1F
→
01/02 18:10,
6年前
, 2F
01/02 18:10, 2F
※ 編輯: x411066 (120.126.33.178 臺灣), 01/02/2020 19:28:27