引線二元樹.ppt

* 第二次節點分裂的結果 * 6.7.3 B樹 (B Tree) 刪除一筆鍵值資料K ，首先我們必須透過搜尋的處理找出該筆鍵值所在的節點位置，接著再將該筆資料刪除。由於鍵值資料所在的節點可能是樹葉節點或是非終端節點，其刪除的動作並不相同。 詳細的資料刪除程序如下所列： 步驟(1)：令 NK = ?m/2?-1，且NO(i)表示節點 i之鍵值個數。 步驟(2)：找出欲刪除的鍵值 K 所在之節點 N 。 步驟(3)：若 N 為樹葉節點，且刪除K之後，No(N)≧NK，則直接刪除之。 * 6.7.3 B樹 (B Tree) 步驟(4)：若 N 為樹葉節點，且刪除K之後，NO(N)＜NK，則分為以下三種情況處理： a.找出 N 節點的右邊兄弟節點 NR，如果 NO(NR) NK，則取出 NR 節點中最小的鍵值 KR 將之置於父親節點，並且將父親節點中第一個大於 K 之鍵值移到節點 N。 b.若右邊兄弟節點無法調整，則找左邊最靠近之兄弟節點 NL，如果NO(NL) NK。那麼就將 NL 中最大的鍵值移到父親節點，並將父親節點中第一個小於 K 之鍵值移到節點 N。 * 6.7.3 B樹 (B Tree) c.當左邊和右邊兄弟節點均無法調整時，那麼就應調整父親節點 NP。在NP 節點中尋找鏈結指標 Pi+1,i+2 其中 Ki≦K＜Ki+1。順著Pi+1,i+2 找到 NP 的子節點NC 。若 NC = N就沿鏈結指標 Pi,i+1 找到 NP 的子節點 NC。將 NP 中第一個大於 K 的鍵值 Ki+1 以及 N 節點中剩餘之鍵值全部移到節點 NC。 步驟(5)：處理非終端節點。令 Ki = K。沿著 Pi,i+1 鏈結往下找到一個節點 NR，NR 當中的第一個鍵值 K1是 B 樹中所有大於鍵值 K中的最小者，然後將 K1 移到 N 節點的 Ki 位置，若因而導致 No(NR) Nk 則繼續處理節點 NR（即跳回步驟3）。 * * * * 6.7.3 B樹 (B Tree) 圖6.37 原本的 3 階 B 樹 (接下來刪除20) * 6.7.3 B樹 (B Tree) 圖6.38 從圖6.37中刪除20後之 B 樹 (接下來刪除40) * 6.7.3 B樹 (B Tree) 圖6.39 從圖6.38中刪除40後之 B 樹 (接下來刪除90) * 6.7.3 B樹 (B Tree) 圖6.40 從圖6.39刪除90後之 B 樹 (接下來刪除80) * 6.7.3 B樹 (B Tree) 圖6.41 從圖6.40刪除80後之 B 樹 * 6.8 樹狀結構的應用 使用二元樹來組織資料具有下優點：可以方便資料的插入和刪除，並且能夠提昇搜尋資料的速度，也可用來進行資料排序等等。本節將陸續介紹兩種常見的樹狀結構的應用。 * 6.8.1集合(Set)的表示法和應用 樹林(Forest)是由兩棵或兩棵以上的樹所構成。 互斥集合(Pairwise Disjoint Set)就是兩兩沒有交集的集合。 【範例】圖6.42描述了一組互斥集合S1={A,B,C,D}，S2={E,F,G}，S3={H,I,J,K}，我們發現任意兩個集合之交集皆為空集合。 圖6. 42 用樹林來表示互斥集合 * 6.8.1集合(Set)的表示法和應用 「聯集」是一個互斥集合常見的運算。將兩個分別以X與Y為樹根的集合進行聯集處理是將兩個集合的所有元素合併在一個集合中。我們通常利用UNION(X,Y)來表示以X與Y為樹根進行聯集的運算。 【範例】將圖6.42中兩個集合S1 與S2進行聯集的處理。 圖6.43 S1 U S2的兩種結果 * 6.8.2霍夫曼樹與資料壓縮 霍夫曼編碼法（Huffman’s Encode）是一種無失真壓縮技術，其基本概念是將利用較短的編碼字來表示出現頻率高的字元；反之出現頻率較低的字元其編碼字的長度會較長。 建構一棵霍夫曼樹的處理過程列於下： 步驟(1)：替每一個出現頻率不為零的字元產生一個樹葉節點，並將其出現頻率存於該樹葉節點的資料欄位。 步驟(2)：令L是所有樹葉節點之集合。 * 6.8.2霍夫曼樹與資料壓縮 步驟(3)：當│L│樹葉節點的個數不等於1時，重複地執行下列子步驟 : a.產生一個新節點 N。 b.設定節點N為 N1 和 N2 的父親節點，N1 和 N2 是 L 中出現頻率最低的兩個節點。 c.設定節點N的出現頻率等於N1 和 N2 的出現頻率總 和。 d.從L中刪除N1 和N2，並將N