[問題]資料結構--關於AVL樹有二個BF值大於1的平衡調整?
題目:請在下面的二元搜尋樹插入15，並維持AVL的平衡
--------------------------8------------------------
---------4---------------------------------------14--------------
---2--------------5-------------------11---------------------17----
---------------------------------------------------------16------18----------
我的想法:
加入15後圖形變成:
--------------------------8-----------------------------
---------4----------------------------------------14--------------
---2--------------5-------------------11---------------------17----
---------------------------------------------------------16------18----------
-----------------------------------------------------15---------------
8節點的平衡因子(BF)為-2,14節點的平衡因子(BF)為2
之前做的題目都是只有一個BF絕對值大於1的節點,現在這題是兩個
我的想法是先針對8的右子樹去做平衡的動作:
如果以14為Root這棵樹屬於RL型,平衡後圖形如下:
--------------------------16--------------
---------14---------------------------------------17----
---11------------15------------------------------------------18
合併原本8的左子樹圖形如下:
--------------------------8-----------------------------
---------4----------------------------------------16--------------
---2--------------5-------------------14---------------------17----
---------------------------------11---------15--------------------18
所有的BF皆小於等於1
請問我這樣解可以?有沒有錯誤?
謝謝.^_^
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.235.199.169
→
04/21 20:48, , 1F
04/21 20:48, 1F
→
04/21 23:20, , 2F
04/21 23:20, 2F
→
04/21 23:21, , 3F
04/21 23:21, 3F
→
04/21 23:25, , 4F
04/21 23:25, 4F