[理工] [DS] 高等樹Rotation問題

看板Grad-ProbAsk作者時間12年前 (2012/02/09 00:06), 編輯推噓3(3推 0噓 3→)
留言6則, 3人參與, 最新討論串1/1
After inserting a new node to an AVL tree, at most two rotations are needed to re-blanced the tree. 答案給這個敘述是 錯的 但不管是RR.RL.LR.LL哪種case最多都是兩次rotation不是嗎? 還是我誤會題目的意思了 另外若將AVL tree改成Red-Black tree 也是錯的嗎? 以上兩題請教各位 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.33.188.58
推
02/09 00:27, , 1F
做一次就好了吧
02/09 00:27, 1F
→
02/09 00:29, , 2F
Algo版的紅黑樹應該才是rotation兩次
02/09 00:29, 2F
推
02/09 00:38, , 3F
AVL應該是最多兩次沒錯吧＠＠ 紅黑樹要看旋轉完是否符合
02/09 00:38, 3F
→
02/09 00:39, , 4F
特性，繼續往上檢查，所以不會最多兩次
02/09 00:39, 4F
推
02/09 00:43, , 5F
我這邊是把RL LR視為兩次旋轉啦 不然AVL當然一次而已
02/09 00:43, 5F
→
02/09 01:11, , 6F
了解!! 謝謝兩位強者
02/09 01:11, 6F
‣ 更多 shooo 的文章
文章代碼(AID): #1FCfsRKC (Grad-ProbAsk)