Tree可以是空集合.ppt

Chapter102 3tree與2 3 4tree 10 12 3tree10 22 3 4Tree 資料結構 使用C語言2 10 12 3tree 一棵2 3Tree可以是空集合 若不是空集合 則必須符合下列幾項定義 2 3Tree中的節點可以存放一筆或兩筆資料 若節點中存放了一筆資料Ldata 其必須存在兩個子點節 左子節點與中子節點 而且左子節點所存放的資料必須小於Ldata 中子節點存放的資料必須大於Ldata 資料結構 使用C語言3 10 12 3tree 若節點中存放了兩筆資料Ldata與Rdata 則會存在三個子節點 左子節點 中子節點與右子節點 而且Ldata Rdata 左子節點所存放的資料必須小於Ldata 中子節點所存放的資料必須大於Ldata 小於Rdata 右子節點所存放的資料必須大於Rdata 樹中的所有樹葉節點必須為同一階度 Level 資料結構 使用C語言4 10 12 3tree 10 1 12 3Tree的加入從2 3Tree的開始搜尋 假使加入的資料其鍵值在2 3Tree中找不到 則加入2 3Tree中 假設加入的節點該節點只有一筆資料 則直接加入 該節點已存在兩筆資料 加入後不符合2 3tree的定義 因此必須將此節點一分為二 並將中間的鍵值 往上提到父節點 資料結構 使用C語言5 10 12 3tree 資料結構 使用C語言6 10 12 3tree 加入60於圖10 1 依搜尋結果將60加入於f節點中 由於f節點的鍵值數只有一個 則直接加入即可 資料結構 使用C語言7 10 12 3tree 承 1 加入90 由於g節點已有兩個鍵值80與85 因此必須將g節點劃分為g h兩個節點 然後將85加入其父節點c中 因為85介於80和90之間 資料結構 使用C語言8 10 12 3tree 承 2 加入55 以同樣的方法將f劃分為f i並將55加入c節點 由於c節點已有兩個鍵值 若再加入一鍵值勢必也要劃分c節點為二 其為c j 並將70加入其父節點a 資料結構 使用C語言9 10 12 3tree 承 3 加入15 資料結構 使用C語言10 10 12 3tree 承 4 加入25 資料結構 使用C語言11 10 12 3tree 承 5 加再加入17以同樣方法 其結果如下所示 資料結構 使用C語言12 10 12 3tree 10 1 22 3Tree的刪除2 3Tree的刪除分成兩部份 刪除的鍵值是在樹葉節點上 leafnode 刪除的鍵值是在非樹葉節點 non leafnode 資料結構 使用C語言13 10 12 3tree 資料結構 使用C語言14 10 12 3tree 若刪除的鍵值是在樹葉節點上今欲刪除圖10 2中節點d的鍵值10 則可直接刪除之 因為刪除後還有一個 故還符合2 3Tree的定義 資料結構 使用C語言15 10 12 3tree 假設我們要刪除的是圖10 2中節點g的鍵值85 此時不可直接刪除之 我們必需向左或右兄弟節點借一個鍵值 一般而言我都先向右邊的節點借 若右邊節點沒有 再向左邊節點借 這不是絕對的順序 ok 若我們向右邊的節點h借 則需借一個最小的鍵值95 為什麼 然後以g節點之父節點c中的鍵值90 挑介於85和95之間的鍵值 取代刪除的85 並將95往上提到c節點上 資料結構 使用C語言16 10 12 3tree 最後結果如下圖所示 資料結構 使用C語言17 10 12 3tree 承上圖若繼續刪除90 則右兄弟節點沒有多餘的鍵值 而左兄弟節點有一個以上的鍵值 因此向左兄弟節點借一個最大值75 往上提至父節點 並將父節點的80 因為它介於75和90之間 取代90 資料結構 使用C語言18 10 12 3tree 最後結果如下圖所示 資料結構 使用C語言19 10 12 3tree 承上圖 繼續刪除80的話 則因為它的左右兄弟節點皆無一個以上的鍵值 此時必需挑左或右兄弟與其父節點的某一鍵值合併 如挑右兄弟節點和父節點合併結果如下圖所示 資料結構 使用C語言20 10 12 3tree 若挑左兄弟節點和父節點合併 則結果如下 資料結構 使用C語言21 10 12 3tree 刪除的鍵值在非樹葉節點上若此時欲刪除的圖10 2中a節點的鍵值60 則可以找此節點之右子樹中最小的鍵值來取代 或找左子樹中最大的鍵值來取代之 若以右子樹中最小的鍵值來取代的話 則f節點的70將取代60 資料結構 使用C語言22 10 12 3tree 如下圖所示 資料結構 使用C語言23 10 12 3tree 就好比您是刪除70一樣 由於f節點有一個以上的鍵值 故可直接刪除之 承上圖 再刪除70鍵值 資料結構 使用C語言24 10 12 3tree 承上圖 再刪除90 資料結構 使用C語言25 10 12 3tree 承上圖 再刪除95 資料結構 使用C語言26 10 12 3tree 承上圖 若再刪除75 1 若以右子樹中的80取代的話後 情形如下圖所示 資料結構 使用C語言27 10 12 3tree 則此不符合2 3tree的定義 因為有一節點沒有鍵值故需再調整之 最後如下圖所示 資料結構 使用C語言28 10 12 3tree 2 若以左子樹中的50取代的話 則結果如下圖所示 資料結構 使用C語言29 10 12 3tree 這好比在刪除50的樹葉節點一般 其實我們可以在刪除非樹葉節點的鍵值時 隨機的挑選以右子樹的最小值或左子樹的最大值交換的應用 資料結構 使用C語言30 10 22 3 4Tree 一棵2 3 4Tree必須符合下列定義 2 3 4Tree中的節點可以存放一筆 兩筆或三筆資料 若節點中存放了一筆資料Ldata 其必須存在兩個子節點 左子節點與左中子節點 而且左子節點所存放的資料必須小於Ldata 左中子節點存放的資料必須大於Ldata 資料結構 使用C語言31 10 22 3 4Tree 若節點中存放了兩筆資料Ldata與Mdata 則會存在三個子節點 左子節點 左中子節點與右中子節點 Ldata Mdata 左子節點所存放的資料必須小於Ldata 左中子節點所存放的資料必須大於Ldata 小於Mdata 右中子節點所存放的資料必須大於Mdata 資料結構 使用C語言32 10 22 3 4Tree 若節點中存放了三筆資料Ldata Mdata與Rdata 則會存在四個子節點 左子節點 左中子節點 右中子節點與右子節點 Ldata Mdata Rdata 左子節點所存放的資料必須小於Ldata 左中子節點所存放的資料必須大於Ldata 小於Mdata 右中子節點所存放的資料必須大於Mdata 小於Rdata 右子節點所存放的資料必須大於Rdata 資料結構 使用C語言33 10 22 3 4Tree 樹中的所有樹葉節點必須為同一階度 Level 資料結構 使用C語言34 10 22 3 4Tree 10 2 12 3 4Tree的加入2 3 4Tree的加入與2 3Tree十分類似 假設存在一2 3 4Tree 如下圖所示 資料結構 使用C語言35 10 22 3 4Tree 若欲加入60承上圖 再加入70於d節點 資料結構 使用C語言36 10 22 3 4Tree 承上圖 再加入95最後再加入75 資料結構 使用C語言37 10 22 3 4Tree 由於e節點不符合2 3 4Tree的定義 故需加以調整之 將80提至父節點a中 並將e分為二 如下所示 資料結構 使用C語言38 10 22 3 4Tree 但此時a亦是不符合2 3 4Tree的定義 故繼續調整之 最