第一次PO板，可能寫的不盡詳細or不完整.... 假設兩兒子的高度差為 正數 or 0 找出旋轉點：先從剛插入的節點往root的方向，依序往上找， 直到找到節點的兩個兒子高度差為2 則此節點的爸爸以上，高度差皆 >= 2 此節點的兒子以下，高度差皆 <= 1 再判斷此節點與剛剛節點插入的方向（就是LL LR那四種的某一種） 依插入的方向，可以找出三個節點， 依二元樹特性，可以找出這三節點的大小關係， 而這三個節點，會連接四個節點，依小到大，我用紅黃綠藍四色代表。 找好之後，開始作旋轉。 旋轉：將需要作旋轉的三個節點，依二元樹的特性，列出大中小三個值 而中間的值往上搬成為父點，小的值與大的值變成中間值的兩個兒子 接下來比較難的就是旋轉前三個節點的四個兒子（紅黃綠藍四個節點） 此四個節點（紅 < 黃 < 綠 < 藍）依圖例， 紅色接到最小值的左兒子（因為紅色是最小的）， 黃色接到最小值的右兒子（次小） 綠色接到最大值的左兒子（次大） 藍色接到最大值的右兒子（因為最大） 按照這種規則就可以實作出來了， 我會利用從插入的節點往回找高度差的原因是因為， 這樣子就不用每插入一次，就要整棵樹parse一次， 再者，旋轉只會與那三個需要旋轉的點有關， 旋轉完之後，並不需要再計算整棵樹每個節點的高度差， 因為旋轉一次，整棵樹就會平衡了。（horowitz課本後面好像有証明的樣子） │ │ ╭─╮ 　　　　　　 │大│ ← 以此點的"左右兒子高度差"為２ 　　　　　　 ╰─╯ （他兒孫的高度差皆為１或０， 　　　　　　 ／ ＼ 他爸爸、爺爺往上，皆大於等於２） ／ Ｌ ＼ 　 ╭─╮　　　 　 　 ╭─╮ 　│小│ 　　　 　│ │ 　╰─╯ 　 　 　　╰─╯ ／　＼ Ｒ 　 　 ／　＼ ／　　　＼ ／　　　＼ ╭─╮　　　╭─╮ ╭─╮　　　╭─╮ │ │ 　│中│ │ │ 　　│ │ ╰─╯ 　╰─╯ ╰─╯ 　　╰─╯ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ○ ○ ○ ○○ ○ ○ ○ ： ： ： ： ： ： ● ← 假設插入的節點在這邊， 由此節點往上開始比較爸爸的左右兩兒子高度差 if ( 爸爸的左右兒子高度差 >= 1 ) then 記錄此點， 並判斷 此點 與 插入節點 的關係， 即 LL or LR or RL or RR， 開始做旋轉!! else 繼續找爸爸的爸爸， 直到找到第一個高度差為２的節點， 或是找到root都沒有高度差為２，則結束! 　　　　　　　　　 父　 父 │ │ │ │ ╭─╮ 經ＬＲ旋轉後 　 　 ╭─╮ 　　　　 │大│ ＝＝＝＝＝＝＞　 　│中│ 　　　　 ╰─╯ 　　╰─╯ 　　　 ／ ＼ 　 ／　＼ ／ Ｌ ＼ ／　　　＼ 　 ╭─╮　　　 　 　 ╭─╮ ╭─╮　　　╭─╮ 　│小│ 　　　 　│Ｄ│ │小│ 　　│大│ 　╰─╯ 　 　 　　╰─╯ ╰─╯ 　　╰─╯ ／　＼ Ｒ 　 　 ／　＼ ／ ＼ ／ ＼ ／　　　＼ ／　　　＼ Ａ Ｂ Ｃ Ｄ ╭─╮　　　╭─╮ ╭─╮　　　╭─╮ ： ： ： ： │Ａ│ 　│中│ │ │ 　　│ │ ： ： ： ： ╰─╯ 　╰─╯ ╰─╯ 　　╰─╯ ● ／ ＼ ／ ＼ ／ ＼ ／ ＼ ○ ○ Ｂ Ｃ○ ○ ○ ○ ： ： ： ： ： ： ● 剩下LL RL （RR我就沒有畫了，因為差不多） 爺 │ 父 │ ╭─╮ 　　　　 │大│ 　　　　 ╰─╯ 　　　　 ／ ＼ ／ Ｌ ＼ 　 ╭─╮　　　 　 　 ╭─╮ 　│中│ 　　　 　│ │ 　╰─╯ 　 　 　　╰─╯ ／　＼ 　 　 　 ／　＼ ／Ｌ　　＼ ／　　　＼ ╭─╮　　　╭─╮ ╭─╮　　　╭─╮ │小│ 　│　│ │ │ 　　│ │ ╰─╯ 　╰─╯ ╰─╯ 　　╰─╯ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ○ ○ ○ ○○ ○ ○ ○ ： ： ： ： ： ： ● ● ↖ ↑ ↖↑ 不管插在哪一邊，皆都是LL型 !! 爺 │ 父 │ ╭─╮ 　　　　 │小│ 　　　　 ╰─╯ 　　　　 ／ ＼ ／ 　 Ｒ ＼ 　 ╭─╮　　　 　 　 ╭─╮ 　│　│ 　　　 　│大│ 　╰─╯ 　 　 　　╰─╯ ／　＼ 　 　 Ｌ ／　＼ ／　　　＼ ／　　　＼ ╭─╮　　　╭─╮ ╭─╮　　　╭─╮ │　│ 　│　│ │中│ 　　│ │ ╰─╯ 　╰─╯ ╰─╯ 　　╰─╯ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ○ ○ ○ ○○ ○ ○ ○ ： ： ： ： ： ： ● ● ↖ ↑ ↖↑ 不管插在哪一邊，皆都是RL型 !! ※ 引述《drkkimo (Dr.K)》之銘言： : 我想這算是蠻常被提到的一種東西吧 不過老實說 我對它的資料插入和刪除後 要作的 : 調整真的搞不太懂 看到二、三本書吧 都分成LL、LR、RR、LR型調整之類的 但還是不很 : 了解 … : 請問有沒有人知道那裡有比較完整的實作 或是比較清楚的解說呢 因為我最近想把它弄懂　 : 可否指點一下呢 thx:) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.229.230.7 ※ 編輯: iamomygod 來自: 61.229.230.7 (01/31 21:31)