資料結構--關於AVL樹有二個BF值大於1的平衡調整? - 學習

By Mia
at 2011-04-21T09:48

Table of Contents

題目:請在下面的二元搜尋樹插入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
請問我這樣解可以?有沒有錯誤?
謝謝.^_^

--

All Comments

By Zanna
at 2011-04-25T20:59

去 grad-proask

By Isla
at 2011-04-29T12:31

要由插入的結點當作[起始結點]由下往上檢查BF值,非0,-1

By Isabella
at 2011-04-30T12:38

+2時就調整,調整完就可以了,只有DELETION要一直檢查調整

By Sandy
at 2011-05-02T12:26

所以只要14那邊調整就可以了

Related Posts

腦袋無法控制該怎麼辦

By Zenobia
at 2011-04-21T05:42

※ 引述《daijon (Daijon)》之銘言： : 唉我這個人只要在很重要的時期腦袋就會無法控制… : 像是只要在準備大考的那一年我就會焦躁到發瘋怎麼念都念不進去最後就變成坐在 : 書桌前一直哭連在圖書館也是… : 明明以前念很順的東西怎麼突然全看不懂了或是那種念進去的感覺跟以前不 ...

念書的態度

By Callum
at 2011-04-20T19:42

其實讀書念到現在中間有怠惰過也有奮發過(真的嗎?!) 自己習慣的念書環境不斷在變國中的時候會希望念書的環境越安靜越好反而到了高中覺得吵一點的環境可以專心XD 大學... 其實都是和室友挑夜燈比較多不過念到現在真的可以體驗禮記所寫「獨學而無友，則孤陋寡聞」自己一個人孤軍 ...

自己孤軍奮戰的情況

By Jessica
at 2011-04-20T18:56

各位晚安,今天我大學學妹問我一個問題就是考研究所的時候到底自己唸就可以還是跟別人組讀書會比較好? 因為她聽別人考上的經驗,大多都有和別人一起組讀書會 (包括我,但是我有跟她說我之前是全職的考生,所以才找人組讀書會) 但因為她現在是OL,打算做到七月底再辭職專心準備明年的考試現在她是一邊補習一邊 ...

如何學會寫"英文論文"

By Joe
at 2011-04-20T18:28

考上碩班了但是指導教授說論文要用英文寫糟了連英文作文簡單文章都不太會寫該怎麼寫英文論文這讓我好焦慮... - ...

大同大學跨海催生多國第一所研究型大學

By Hamiltion
at 2011-04-20T16:20

今年三月跨海替多明尼加規劃完成研究型大學方案，以產學合作為主要方向，這一所研究型大學，預計2013年開始招生，第一年將招收120名學生。多明尼加共和國位於加勒比海，國內有10多所大學，以教學為主，沒有研究所，大同大學教務長林永仁指出，多明尼加和台灣十年前狀況相似，必須創新研究，才能提升國內經 ...