---

---

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

--
Shaken, Not Stirred.
--
※ 作者: TL 時間: 2013-01-27 18:40:26