Please enable JavaScript.

Coggle requires JavaScript to display documents.

高等樹 - Coggle Diagram

- - - - DS版本
        LL、LR、RL、RR算四種
      - ALGO版本
        LL、RR算一種 ; LR、RL算一種
  - - - 求最小高度
        
        2^n -1：二元樹基本定理之一
      - 求最大高度
        
        費氏數F_n+2 -1：上述定理
- - - - 令Root階級=0，高度為0的Binomial Tree為B0，只有Root一個點
      - 高度為k的Binomial Tree，記作Bk，由兩棵Bk-1組成
        任意挑某一棵當成另一棵的子樹
    - - Bk中第I level的節點數是C k取i
      - Bk的節點數是2^k
- - - - Def
        
        1）樹根不存值
        2）左兄弟值<=右兄弟值
        3）若某節點x有祖父，則祖父的左子點需要<= x
        4）祖父的右子點需要>= x
        5）:explode:以節點編號 i 為樹根之子樹中，其子孫最小值為左子節點，其子孫最大值為右子節點（也就是左子樹是min-heap 右子樹是max-heap） :explode:
      - insert x in SMMH
        
        1）x先暫時放在最後一個節點的下一個位置
        2）先確認Def 2是否成立，違反則兩兄弟互換
        3）確認Def 3-4 是否滿足，若違反其中之一，就要做調整(SWAP)
      - Delete MAX in SMMH
        
        1）移走樹根的右子樹的樹根「值」
        2）刪掉最後一個節點，並令其值為x
        3）x暫時放在右子樹的樹根，並令其節點位置為E
        4）重複check Def 1&3 是否滿足，不滿足則調整
      - 刪除最小
        
        1）移走樹根左小孩的樹根「值」
        2）刪掉最後一個節點，並令其值為 x
        3）x 暫存在左子樹的樹根，並令其節點位置為E
        4）重複check Def 1&3 是否滿足，不滿足則調整
    - - insert
        
        先把x放在最後一個節點的下一個位置，再看x爸爸是在min(max) level，比較x和爸爸的關係，若x 小於(大於)他爸，則兩人交換。最後x站在原地向上挑戰min(max) level
      - delete min
        
        移走root 資料，刪掉最後一個節點x，並將其視作要插入進一個root 為空的min-Max Heap 中
        
        如果樹根的子孫中最小值就是樹根的左右兒子其中之一，令作k。則x和k比較一下（亦即 k位在max-level 但又是目前樹裡面資料的最小值）
        
        如果樹根的孫子其中之一是最小值（是min-levle），令作k，k的爸爸是p。如果x>k，k直接放到root然後確定x和k老爸p的關係。如果x>p，則兩值互換，此時視作x要插入原本k在的地方（所以go to step3）
        
        如果樹根以下沒子點，就直接把x放到樹根，接著Exit
      - Def
        
        1）資料最小值在樹根
        2）最大值是樹根的左右兒子其中之ㄧ
        3）若x在min(max) level 中，表示以x為樹根的子樹中，x是min(max值)
      - delete max
        
        移走樹根的左右兒子的max的其中之一，刪掉最後一個節點x並將其視作一個要插入進樹根為空的MAX-min Heap
        
        此時這邊的樹根是指剛剛被移走空下來的那一個節點位置
        
        如果root沒有小孩了，x直接放進去樹根
        
        如果樹根的左右小孩之一是整棵sub子樹中的最小值
        
        如果
    - - Def
        
        1）樹根不存值
        2）樹根左子樹是min heap
        3）樹根右子樹是max heap
        4）Deap [i]<= Deap [j]（很重要）
      - Insert x
        
        x先暫時放在最後一個節點的下一個位置
        
        x 在左子樹
        
        比較x所在位置在右子樹的對應點值，亦即如果x > Deap[ j ]，則把 j 位置中的值放到 x 所在位置，然後當成x要去j的位置做insert Max Heap ，否則就是插入min-Heap-insert
        
        x 在右子樹
        
        對稱
      - Delete min in Deap
        
        1）移走左子樹的樹根值
        2）將最後一個節點刪掉，並令其值為x
        3）左子樹樹根的空缺由他的左右子點min往上遞補，直到在左子樹的某個leaf（令做 i）形成一個空缺
        4）視作insert x 在leaf I 的位置，也就是insert x in Deap
- - - - E=I+2N（N是內部節點數量）
        
        加權外部路徑長
        WEPL
        
        求min WEPL
        
        用Huffman演算法
        
        令w 為外部節點的加權集合，從w中每次都挑兩個最小的加權值，建立延伸二元樹，然後這兩個加權值的和再繼續放到w裡，重複做直到w中只剩一個加權值
        
        sigma （樹根到每個外部節點j的總路徑長*加權值）
- - - - 1）樹根至少有>=2個子點
        2）除了樹根和外部節點以外，其他節點分支度只能為：m/2取上限<=Degree<=m
        3）所有的外部節點都要位在同一個level
      - 是一種Balance的m-way search tree
    - - Insert x
        
        1）先找有沒有 x ，若到了某個「外部節點」就代表沒有 x ，則將 x 放在此外部節點的「爸爸節點裡」
        2）檢查爸爸節點裡的資料是否有overflow
        3）若沒有就離開，有的話就split ，且處理完還要對爸爸的爸爸去重新檢查2）
      - delete x
        
        1）先找是否有 x
        2）找到看 x 在哪裏，leaf 還是non-leaf
        3）是 leaf 就刪掉 x 並看有沒有underflow，有的話就先看是否可以Rotation（key值重新分配），可以的話就做，不行的話就merge
        4）若是 non-leaf 就找x左子樹最大值或是右子樹最小值，令做y，且y必定在leaf裡，然後拿y去代替x，最後針對這個leaf去check 3）
- - - - 1)先search for x，找出適當的插入位置，但還不要插入
        2）在找的過程中，如果有某節點的兩個小孩都是紅色，則做color change，接著檢查有無連續的紅色節點，有的話做Rotaiton
        3）第2步做完後將x放到新node，且標紅色
        4）檢查是否有連續的紅色節點，有的話就做Rotation調整
        5）Root一律改黑色
      - 做完就不要回頭，第2、4步驟的Rotation最多只會做一個，不可能兩個都發生
      - Rotation：中間鍵往上拉放黑色，兩子點放紅色
- - - - splay點永遠當Root
      - 但要維持BST特性