Re: 請問AVL Tree的實作

看板C_and_CPP (C/C++)作者iamomygod (不詳)時間19年前 (2006/01/31 21:09)推噓4(4推 0噓 4→)

留言8則, 4人參與討論串1/1

第一次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