欢迎来到天天文库
浏览记录
ID：43922570
大小：1.07 MB
页数：41页
时间：2019-10-16
《Tree可以是空集合》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、Chapter10 2-3tree與2-3-4tree10.12-3tree10.22-3-4Tree10.12-3tree一棵2-3Tree可以是空集合，若不是空集合，則必須符合下列幾項定義：2-3Tree中的節點可以存放一筆或兩筆資料。若節點中存放了一筆資料Ldata，其必須存在兩個子點節－左子節點與中子節點。而且左子節點所存放的資料 必須小於Ldata；中子節點存放的資料 必須大於Ldata。210.12-3tree若節點中存放了兩筆資料Ldata與Rdata，則會存在三個子節點－左子節點、中子節點與右子節點。 而且Ldata2、料必須小於Ldata；中子節點所存放的資料必須大於Ldata，小於Rdata；右子節點所存放的資料 必須大於Rdata。樹中的所有樹葉節點 必須為同一階度（Level）。310.12-3tree10.1.12-3Tree的加入從2-3Tree的開始搜尋，假使加入的資料其鍵值在2-3Tree中找不到，則加入2-3Tree中，假設加入的節點該節點只有一筆資料，則直接加入；該節點已存在兩筆資料，加入後不符合2-3tree的定義，因此必須將此節點一分為二，並將中間的鍵值，往上提到父節點。410.12-3tree510.12-3tree加入60於圖10-1，依搜尋結果將603、加入於f節點中，由於f節點的鍵值數只有一個，則直接加入即可。610.12-3tree承(1)加入90，由於g節點已有兩個鍵值80與85，因此必須將g節點劃分為g,h兩個節點，然後將85加入其父節點c中，因為85介於80和90之間。710.12-3tree承(2)加入55，以同樣的方法將f劃分為f,i並將55加入c節點，由於c節點已有兩個鍵值，若再加入一鍵值勢必也要劃分c節點為二，其為c,j，並將70加入其父節點a。810.12-3tree承(3)加入15910.12-3tree承(4)加入251010.12-3tree承(5)加再加入17以同樣方法，其結果如下所示4、：1110.12-3tree10.1.22-3Tree的刪除2-3Tree的刪除分成兩部份：刪除的鍵值是在樹葉節點上（leafnode），刪除的鍵值是在非樹葉節點（non-leafnode）。1210.12-3tree1310.12-3tree若刪除的鍵值是在樹葉節點上今欲刪除圖10-2中節點d的鍵值10，則可直接刪除之，因為刪除後還有一個，故還符合2-3Tree的定義。1410.12-3tree假設我們要刪除的是圖10-2中節點g的鍵值85，此時不可直接刪除之，我們必需向左或右兄弟節點借一個鍵值，一般而言我都先向右邊的節點借，若右邊節點沒有，再向左邊節點借，這不5、是絕對的順序。ok，若我們向右邊的節點h借，則需借一個最小的鍵值95（為什麼?），然後以g節點之父節點c中的鍵值90（挑介於85和95之間的鍵值）取代刪除的85，並將95往上提到c節點上。1510.12-3tree最後結果如下圖所示：1610.12-3tree承上圖若繼續刪除90，則右兄弟節點沒有多餘的鍵值，而左兄弟節點有一個以上的鍵值，因此向左兄弟節點借一個最大值75，往上提至父節點，並將父節點的80（因為它介於75和90之間）取代90。1710.12-3tree最後結果如下圖所示：1810.12-3tree承上圖，繼續刪除80的話，則因為它的左右兄弟節點皆無一6、個以上的鍵值，此時必需挑左或右兄弟與其父節點的某一鍵值合併，如挑右兄弟節點和父節點合併結果如下圖所示：1910.12-3tree若挑左兄弟節點和父節點合併，則結果如下：2010.12-3tree刪除的鍵值在非樹葉節點上 若此時欲刪除的圖10-2中a節點的鍵值60．則可以找此節點之右子樹中最小的鍵值來取代，或找左子樹中最大的鍵值來取代之，若以右子樹中最小的鍵值來取代的話，則f節點的70將取代60。2110.12-3tree如下圖所示：2210.12-3tree就好比您是刪除70一樣，由於f節點有一個以上的鍵值，故可直接刪除之。承上圖，再刪除70鍵值。2310.12-7、3tree承上圖，再刪除90。2410.12-3tree承上圖，再刪除952510.12-3tree承上圖，若再刪除75，(1)若以右子樹中的80取代的話後，情形如下圖所示：2610.12-3tree則此不符合2-3tree的定義，因為有一節點沒有鍵值故需再調整之，最後如下圖所示：2710.12-3tree(2)若以左子樹中的50取代的話，則結果如下圖所示：2810.12-3tree這好比在刪除50的樹葉節點一般，其實我們可以在刪除非樹葉節點的鍵值時，隨機的挑選以右子樹的最小值或左子樹的最大值交換的應用。2910.22-3-4Tree一棵2-3-4Tree必須符合8、下列定義：
2、料必須小於Ldata；中子節點所存放的資料必須大於Ldata，小於Rdata；右子節點所存放的資料 必須大於Rdata。樹中的所有樹葉節點 必須為同一階度（Level）。310.12-3tree10.1.12-3Tree的加入從2-3Tree的開始搜尋，假使加入的資料其鍵值在2-3Tree中找不到，則加入2-3Tree中，假設加入的節點該節點只有一筆資料，則直接加入；該節點已存在兩筆資料，加入後不符合2-3tree的定義，因此必須將此節點一分為二，並將中間的鍵值，往上提到父節點。410.12-3tree510.12-3tree加入60於圖10-1，依搜尋結果將60
3、加入於f節點中，由於f節點的鍵值數只有一個，則直接加入即可。610.12-3tree承(1)加入90，由於g節點已有兩個鍵值80與85，因此必須將g節點劃分為g,h兩個節點，然後將85加入其父節點c中，因為85介於80和90之間。710.12-3tree承(2)加入55，以同樣的方法將f劃分為f,i並將55加入c節點，由於c節點已有兩個鍵值，若再加入一鍵值勢必也要劃分c節點為二，其為c,j，並將70加入其父節點a。810.12-3tree承(3)加入15910.12-3tree承(4)加入251010.12-3tree承(5)加再加入17以同樣方法，其結果如下所示
4、：1110.12-3tree10.1.22-3Tree的刪除2-3Tree的刪除分成兩部份：刪除的鍵值是在樹葉節點上（leafnode），刪除的鍵值是在非樹葉節點（non-leafnode）。1210.12-3tree1310.12-3tree若刪除的鍵值是在樹葉節點上今欲刪除圖10-2中節點d的鍵值10，則可直接刪除之，因為刪除後還有一個，故還符合2-3Tree的定義。1410.12-3tree假設我們要刪除的是圖10-2中節點g的鍵值85，此時不可直接刪除之，我們必需向左或右兄弟節點借一個鍵值，一般而言我都先向右邊的節點借，若右邊節點沒有，再向左邊節點借，這不
5、是絕對的順序。ok，若我們向右邊的節點h借，則需借一個最小的鍵值95（為什麼?），然後以g節點之父節點c中的鍵值90（挑介於85和95之間的鍵值）取代刪除的85，並將95往上提到c節點上。1510.12-3tree最後結果如下圖所示：1610.12-3tree承上圖若繼續刪除90，則右兄弟節點沒有多餘的鍵值，而左兄弟節點有一個以上的鍵值，因此向左兄弟節點借一個最大值75，往上提至父節點，並將父節點的80（因為它介於75和90之間）取代90。1710.12-3tree最後結果如下圖所示：1810.12-3tree承上圖，繼續刪除80的話，則因為它的左右兄弟節點皆無一
6、個以上的鍵值，此時必需挑左或右兄弟與其父節點的某一鍵值合併，如挑右兄弟節點和父節點合併結果如下圖所示：1910.12-3tree若挑左兄弟節點和父節點合併，則結果如下：2010.12-3tree刪除的鍵值在非樹葉節點上 若此時欲刪除的圖10-2中a節點的鍵值60．則可以找此節點之右子樹中最小的鍵值來取代，或找左子樹中最大的鍵值來取代之，若以右子樹中最小的鍵值來取代的話，則f節點的70將取代60。2110.12-3tree如下圖所示：2210.12-3tree就好比您是刪除70一樣，由於f節點有一個以上的鍵值，故可直接刪除之。承上圖，再刪除70鍵值。2310.12-
7、3tree承上圖，再刪除90。2410.12-3tree承上圖，再刪除952510.12-3tree承上圖，若再刪除75，(1)若以右子樹中的80取代的話後，情形如下圖所示：2610.12-3tree則此不符合2-3tree的定義，因為有一節點沒有鍵值故需再調整之，最後如下圖所示：2710.12-3tree(2)若以左子樹中的50取代的話，則結果如下圖所示：2810.12-3tree這好比在刪除50的樹葉節點一般，其實我們可以在刪除非樹葉節點的鍵值時，隨機的挑選以右子樹的最小值或左子樹的最大值交換的應用。2910.22-3-4Tree一棵2-3-4Tree必須符合
8、下列定義：
此文档下载收益归作者所有
