Please enable JavaScript.

Coggle requires JavaScript to display documents.

CH10 (比較圖(Insert/Delete Worst Case與Expected) (Hash Table : O(n)、O(1), BST …

- - - - (1)中間鍵值往上拉，小放左、大放右
      - (2)孤兒(子點或子樹)依照BST性質，及可置入正確位置
    - - Single rotation
        
        LL (順時針)
        
        RR (逆時針)
      - Double rotations
        
        LR = RR+LL
        
        RL = LL+RR
- - - - (1)樹根最少有2個子點
      - (2)除了樹根、外部節點以外的node，至少都要有⎾m/2⏋個子點
      - (3)所有的外部節點需再同一level (平衡之意)
      - (4)每個內部節點最多可以有(m-1)個key value，以及m個指標(指向子點)
  - - - (1)先search for x，找到x之置入node，且置入x
      - (2)檢查node是否overflow
        
        若有，必須做split處理。然後再對父點進行overflow判斷，持續向上。
    - - 將第⎾m/2⏋個key往上拉到父點，把其他key分裂成兩個新子點