數(shù)據(jù)結(jié)構(gòu)a第07章搜索樹-資料下載頁
2025-08-04 10:10本頁面
【正文】 有兩個孩子； （ 2） 除根結(jié)點和失敗結(jié)點外的所有結(jié)點至少有?m/2?個孩子； （ 3） 所有失敗結(jié)點均在同一層上 。 南京郵電大學(xué)計算機學(xué)院 陳慧南 2022年 9月 南京郵電大學(xué)計算機學(xué)院 陳慧南 2022年 9月 B樹的高度 性質(zhì) 設(shè) B樹失敗結(jié)點的總數(shù)是 s， 那么 ， 一棵 B樹的元素總數(shù) N是 B樹的失敗結(jié)點的總數(shù)減 ，即 N=s1。 設(shè) n是非失敗結(jié)點數(shù) ， t 是指針總數(shù) t =N+n＝ s+n1 定理 有 N個元素的 m階 B樹的高度是 因： N+1?2*（ ?m/2?） h1 ? ? )21N(l o g1hm / 2???南京郵電大學(xué)計算機學(xué)院 陳慧南 2022年 9月 B樹的搜索 磁盤訪問的次數(shù)最多是 1＋ log?m/2? ((N+1)/2) 南京郵電大學(xué)計算機學(xué)院 陳慧南 2022年 9月 B樹的插入 B樹插入新元素的方法 （ 1） 在 B－樹中搜索給定關(guān)鍵字值的元素 ， 如果搜索成功 ， 表示有重復(fù)元素 ， 插入運算失敗終止 ，否則將新元素和一個空指針插入搜索失敗處的葉結(jié)點中 。 （ 2） 若插入新元素 （ 和一個指針 ） 后 ， 結(jié)點 *q未溢出 ， 即結(jié)點中包含的元素個數(shù)未超過 m1（ 指針數(shù)未超過 m） ， 則插入運算成功終止 。 南京郵電大學(xué)計算機學(xué)院 陳慧南 2022年 9月 （ 3） 若插入新元素 （ 和一個指針后 ） ， 結(jié)點 *q已溢出 ， 則必須進(jìn)行結(jié)點的分裂操作 ， 將結(jié)點一分為三 。分裂發(fā)生在位置 ?m/2?處 。 關(guān)鍵字值 K?m/2?之前的元素保留在原來的結(jié)點中 ， 在它之后的元素存放在新創(chuàng)建的結(jié)點 （ 設(shè)地址為 q’） 中 ， 而關(guān)鍵字值為 K?m/2?的元素和地址 q’ 將插入結(jié)點 *q的雙親結(jié)點中 。 這意味著在該雙親結(jié)點中新增了一個元素和一個指針 ， 因此 ， 必須檢查此雙親結(jié)點的溢出問題 。 這同樣可按 （ 2） 和 （ 3）的原則 ， 繼續(xù)檢查和處理該雙親結(jié)點 。 （ 4） 如果按照 （ 3） 的原則 ， 根結(jié)點 *q產(chǎn)生分裂 ， 根結(jié)點沒有雙親 ， 那么分裂產(chǎn)生的兩個結(jié)點的指針 q和 q’以及關(guān)鍵字為 K?m/2? 的元素應(yīng)組成一個新的根結(jié)點 ， B樹增高一 。 只要從根結(jié)點到新元素插入結(jié)點的路徑上至少有一個結(jié)點未滿 ， B樹不會長高 。 南京郵電大學(xué)計算機學(xué)院 陳慧南 2022年 9月 插入 59 南京郵電大學(xué)計算機學(xué)院 陳慧南 2022年 9月 插入 53 南京郵電大學(xué)計算機學(xué)院 陳慧南 2022年 9月 B樹的刪除 從 B樹刪除元素的方法 （ 1） 首先搜索被刪除的元素 ， 如果不存在被刪除的元素 ， 則刪除運算失敗終止 。 如果搜索成功 ， 且被刪除的元素在葉子結(jié)點中 ， 則從該葉子結(jié)點中刪除該元素；如果被刪除的元素不在葉子結(jié)點中 ，那么由它的右側(cè)子樹上的最小元素取代之 （ 必定在葉結(jié)點中 ） ， 然后從葉子結(jié)點中刪除該替代元素 。 （ 2） 如果刪除元素后 ， 當(dāng)前結(jié)點中包含至少 ?m/2?1個元素 ， 刪除運算成功結(jié)束 。 南京郵電大學(xué)計算機學(xué)院 陳慧南 2022年 9月 （ 3） 如果刪除元素后 ， 當(dāng)前結(jié)點中包含不足 ?m/2?1個元素 ， 則稱發(fā)生下溢 。 處理的方法首先是借元素：如果其左側(cè)兄弟包含多余 ?m/2?1個元素 ， 則可以向其左兄弟 “ 借 ” 一個元素；否則如果其右側(cè)兄弟有多余元素 ， 則向其右側(cè)兄弟借 。 南京郵電大學(xué)計算機學(xué)院 陳慧南 2022年 9月 （ 4） 如果刪除元素后 ， 當(dāng)前結(jié)點產(chǎn)生下溢 ， 且左 、右兩側(cè)兄弟結(jié)點都只有 ?m/2?1個元素 ， 則只能進(jìn)行“ 連接 ” 。 若當(dāng)前結(jié)點有左側(cè)兄弟 ， 則將該結(jié)點與其左側(cè)兄弟連成一個結(jié)點 ， 否則與右側(cè)兄弟連接 。連接是將兩個結(jié)點中的元素 ， 連同它們的雙親結(jié)點中用來分割它們的元素組合成一個結(jié)點 ， 另一個結(jié)點將撤消 。 這意味著從其雙親結(jié)點中刪除分割元素和一個指向被撤銷的結(jié)點的指針 ， 這可能導(dǎo)致雙親結(jié)點的下溢 ， 所以需繼續(xù)檢查其雙親結(jié)點 。 應(yīng)按“ （ 2） ， （ 3） ， （ 4） ” 所述方法處理從雙親結(jié)點中刪除元素的問題 。 南京郵電大學(xué)計算機學(xué)院 陳慧南 2022年 9月 （ 5） 如果由于連接操作 ， 導(dǎo)致根結(jié)點中的一個元素被刪除 ， 并且該根結(jié)點只包含一個元素 ， 則其中的元素被刪除后 ， 根結(jié)點成為不含任何元素的空結(jié)點 ，那么兩結(jié)點連接后被保留的那個結(jié)點將成為 B樹新的根結(jié)點 ， 這時 ， B樹變矮 。 如果 B樹本來是只有一個根結(jié)點 ， 且該根結(jié)點只包含一個元素 ， 那么當(dāng)這惟一的元素被刪除后 B樹便成為空樹 。 南京郵電大學(xué)計算機學(xué)院 陳慧南 2022年 9月 刪除 35 南京郵電大學(xué)計算機學(xué)院 陳慧南 2022年 9月 南京郵電大學(xué)計算機學(xué)院 陳慧南 2022年 9月 刪除 27
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1