Data Structure - Ch2 Advanced Tree

Chapter 2   Advanced Tree

2.1   Optimal Binary Search Tree 

• Extended Binary Tree
• 外部節點數 = 內部節點數 + 1，感覺：2n–(n-1) = n+1 
• Internal path Length：I = 「Root 到內部節點 i 的路徑長度」的所有總和
• Extended path Length：E = 「Root 到外部節點 j 的路徑長度」的所有總和
• E = I + 2n (n為內部節點個數) 
• 愈平衡的Extended BT，其E値與I値愈小，若外部Node有加權値時則不一定

• Weighted External Path Length：分別給予毎一個外部節點一個加權値
  ∑ (Root 到外部節點 j的路徑長度 * 外部節點 j的加權值 )
• Minimum Weighted External Path Length：給予(n+1)個外部節點加權値， C_n²ⁿ/(n+1)顆樹中具有最小的Weighted External Path Length稱之。 
• 應用：Huffman Algorithm(Greedy、Dynamic programming) 

• Optimal Binary Search Tree證明與題目操作

2.2    AVL Tree (高度平衡樹)

• 動機
• 在靜態的環境下，一般Binary Search Tree的建構方法可以有較充裕的時間將欲搜尋的所有資料建構成較平衡的Binary Search Tree。 
• 然而，若是在動態的環境下，資料可以隨時Insert / Delete。此時，一般Binary Search Tree的建構方法會産生Skewed Binary Tree。 因此需要AVL Tree面對動態資料使Tree的高度均維持在高度平衡的情況。 
• 定義：AVL (Adelson-Velskii and Landis) tree為Height Balance Binary Search Tree 
• |L - R| ≤ 1，其中L與R為左、右子樹的高度  
• 左右子樹亦是AVL Tree 
• Balance Factor：BT(T)  =  hL - hR  =  -1, 0, 1 
• 從不符合Balance factor向下找(L or R)來判斷是哪種旋轉，找該調整node的方式是用bottom-up
  (因為它上面的也會違反)
• LL、RR調整2個pointer
• LR、RL調整4個pointer (Double-rotation的概念)
• 形成高度h的AVL Tree所須要的最少節點個數為
  F_h+2 - 1   (F:費式數)  

 2.3   m-way Search Tree

• m-way Search Tree
• 動機：External Search，資料量大無法一次全置於Memory中，compare次數較不重要，I/O次數較重要，也就是search tree高度，而最有效方法為加大tree Degree。
• 定義：m-way Search Tree是一個所有節點的分支度≤m的樹。
• 節點結構為 : 鍵值個數n, 指標A0, (鍵值k1, 指標A1), ..., (鍵值kn, 指標An) 
• 指標指向存放大小介於 ki 與 ki+1 之間的資料之節點
• m-way Search Tree雖利用增大Tree的Degree來降低 Search Tree的高度以減少Disk I/O 的次數，但若此Tree 不平衡也可能會變相地增加Disk I/O的次數。 因此發展出B-tree of order m。
• B Tree
• 定義：是一個Balanced m-way search tree。
• Root至少有2個Childs
• 除了Root及Failure Node之外，其餘Node的分支度介於⎡m/2⎤及m之間
• 所有葉子節點位於同一Level
• when m = 3, nodes of B-Tree have degree 2, and 3, a 2-3 tree. 
• when m = 4, nodes of R-Tree have degree 2, 3, and 4, a 2-3-4 tree 
• Operation
• Insert
• 無Overflow (key數≤m-1), simple
• 有Overflow (key數≥ m), split 
• Delete
• 沒有Underflow (即:鍵値數目 ≥ ⎡m/2⎤ -1) ,simple
• 有Underflow (即:鍵値數目 < ⎡m/2⎤ -1)
• Rotation
• Combination,  Combination做完, 針對父點, goto 2

• [補記 : x位於Non-leaf Node]
• 要選擇右子樹最小 or 左子樹最大的鍵値來取代被刪除的資料,以最方便的為優先!! 

• B+ Tree
• 定義：
• B Tree之變形，也是用於External Search/Sort上。 
• 可以支援ISAM (Index Sequential Access Method)，常用於DBMS內層製作。
• Index Sequential Access： 透過Index找到對應的起始Data Block之後，即可循序讀取其它資料。Ex: 找出大於等於7~小於20的資料。 
• B+ tree分為兩個Layer
• Index Layer：採B tree結構。僅用來存放索引，以幫助User正確地找到所需之Data Block。 
• Data Blocks Layer：Data Block存放資料時，通常不會受到B tree的Order限制。用以存放Data且Blocks之間以Link List串連。 

2.4   Red-Black Tree

• 定義：Red-Black Tree 是一種 balanced tree。它基本上是一棵 binary search tree且

1. 每個 node 還漆上了顏色 — 可以是紅色或黑色。
2. root 和 leaves (NIL’s) 必為黑色。
3. 紅色的 node 不可連續兩代。
4. 從一個 node x 往下走，每一條通往 leaf 的路徑上遇到的黑色 nodes 都一樣多，這個固定的數目叫做 x 的 black-height。

• 直覺解釋：
         希望定義出一棵 (黑色的) full 或 complete binary tree (每個 leaf 所在的深度最多只差 1); 但這個條件顯然太嚴格，所以允許有紅色的 nodes 穿插其間。 把紅色的 nodes 想像成是雜質，希望雜質不要太多，以免破壞樹的平衡。 
• 2-3-4 tree和red-black tree對應 
  (非one-to-one)

• 操作
• search : 因為它是一棵 BST，所以查詢資料很簡單
• insert : 先當做一般的 BST, 一路往下找到新資料 x 的落點, 並把 x 塗上紅色。 這樣的變化, 不會破壞 "black height 原則", 但可能破壞 "不可連紅原則", 所以可能需要一路往上整修樹
• x 的父親是黑色：完全不需要整修！
• x 的父親既是紅色，x 的祖父一定是黑色的，有以下三種狀況要考慮
• 叔叔也是紅色：讓祖/父兩輩「紅黑變色」. 現在 x 是沒有問題了, 但祖父可能變成紅色, 因而產生問題。 所以讓祖父扮演 x 的角色, 繼續往上整修。
• 叔叔是黑色
• x 到祖父的路上沒有轉彎：以祖父為 pivot父親為 rotator 旋轉，並調整顏色。 結束。
• x 到祖父的路上有轉彎：先以父親為 pivot, x 為 rotator 旋轉, 變成上個狀況, 再依上個狀況處理。
• 不論是insert, delete, search, modify, 所需時間皆為 O( log n )
• 例題