→ tobyboy21242:去 grad-proask 04/21 20:48
→ itsnotme2:要由插入的結點當作[起始結點]由下往上檢查BF值,非0,-1 04/21 23:20
→ itsnotme2:+2時就調整,調整完就可以了,只有DELETION要一直檢查調整 04/21 23:21
→ itsnotme2:所以只要14那邊調整就可以了 04/21 23:25
題目:請在下面的二元搜尋樹插入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