m階b樹是什麼意思

2021-06-13 06:40:13 字數 3638 閱讀 1651

1樓:匿名使用者

一棵m階b樹(balanced tree of order m)是一棵平衡的m路搜尋樹。它或者是空樹,或者是滿足下列性質的樹:

1、根結點至少有兩個子女;

2、每個非根節點所包含的關鍵字個數 j 滿足:┌m/2┐-1≤ j≤ m-1;

3、除根結點以外的所有結點(不包括葉子結點)的度數正好是關鍵字總數加1,故內部子樹個數k 滿足:┌m/2┐≤k≤m ;

4、所有的葉子結點都位於同一層。

擴充套件資料

在b樹中查詢給定關鍵字的方法是,首先把根結點取來,在根結點所包含的關鍵字k1,…,kn查詢給定的關鍵字(可用順序查詢或二分查詢法),若找到等於給定值的關鍵字,則查詢成功。

否則,一定可以確定要查詢的關鍵字在ki與ki+1之間,pi為指向子樹根節點的指標,此時取指標pi所指的結點繼續查詢,直至找到,或指標pi為空時查詢失敗。

b+樹為b樹的一種變形,比b樹具有更廣泛的應用,m階b+樹有如下特徵:

1、每個結點的關鍵字個數與孩子個數相等,所有非最下層的內層結點的關鍵字是對應子樹上的最大關鍵字,最下層內部結點包含了全部關鍵字。

2、除根結點以外,每個內部結點有m/2到m個孩子。

3、所有葉結點在樹結構的同一層,並且不含任何資訊(可看成是外部結點或查詢失敗的結點),因此,樹結構總是樹高平衡的。

2樓:匿名使用者

m階為一節點至多有m棵子樹 ,也就是說b樹上的結點最多只能有m棵子樹。。。

3樓:

一棵m階的b 樹 (m叉樹)的要求滿足如下:

樹中每個結點最多含有m個孩子(m>=2);

除根結點和葉子結點外,其它每個結點至少有[ceil(m / 2)]個孩子(其中ceil(x)是一個取上限的函式);

若根結點不是葉子結點,則至少有2個孩子(特殊情況:沒有孩子的根結點,即根結點為葉子結點,整棵樹只有一個根節點);

所有葉子結點都出現在同一層,葉子結點不包含任何關鍵字資訊(可以看做是外部接點或查詢失敗的接點,實際上這些結點不存在,指向這些結點的指標都為null);(讀者反饋@冷嶽:這裡有錯,葉子節點只是沒有孩子和指向孩子的指標,這些節點也存在,也有元素。@july:

其實,關鍵是把什麼當做葉子結點,因為如紅黑樹中,每一個null指標即當做葉子結點,只是沒畫出來而已)。

每個非終端結點中包含有n個關鍵字資訊: (n,p0,k1,p1,k2,p2,......,kn,pn)。其中:

a) ki (i=1...n)為關鍵字,且關鍵字按順序升序排序k(i-1)< ki。

b) pi為指向子樹根的接點,且指標p(i-1)指向子樹種所有結點的關鍵字均小於ki,但都大於k(i-1)。

c) 關鍵字的個數n必須滿足: [ceil(m / 2)-1]<= n <= m-1。

4樓:蓴灬叔

b-樹的定義

一棵m(m≥3)階的b-樹是滿足如下性質的m叉樹:

(1)每個結點至少包含下列資料域:

(j,p 0 ,k l ,p 1 ,k 2 ,…,k i ,p i )

其中:j為關鍵字總數

k i (1≤i≤j)是關鍵字,關鍵字序列遞增有序:k 1

5樓:

m階b樹的意思就是:一個根節點最多有m個子節點,n(ceil(m/2)<=n<=m-1)個key值。

其中:m>=2(必須)。

b樹生成規則:以m=4為例。

先生成葉子節點。即插入3個數字(key值(即n)數量飽和)。當插入第4個數字時拆分出一個根節點(取中間值元素0006,0010取0006),2個葉子節點。

依次規律迴圈類推。

新生成的根節點,最多掛4個葉子節點(即根節點0006),即m階.

b樹刪除規則:已m=5為例

如果我們刪除h值,key值(即n)應該ceil(m/2)<=n<=m-1,即2<=n<=4。即滿足key數量範圍要求,只需要把k值移動到h值位置,l值移動到k位置,即操作完成。結果如下:

如果我們刪除t值,

因為t沒有在葉子結點中,而是在中間結點中找到,咱們發現他的繼承者w(字母升序的下個元素),將w上移到t的位置,然後將原包含w的孩子結點中的w進行刪除,這裡恰好刪除w後,該孩子結點中元素個數大於2,無需進行合併操作。結果如下:

如果上結果圖中,我們繼續刪除r值:

r在葉子結點中,但是該結點中元素數目為2,刪除導致只有1個元素,已經小於最小元素數目ceil(5/2)-1=2,而由前面我們已經知道:如果其某個相鄰兄弟結點中比較豐滿(元素個數大於ceil(5/2)-1=2),則可以向父結點借一個元素,然後將最豐滿的相鄰兄弟結點中上移最後或最前一個元素到父節點中,在這個例項中,右相鄰兄弟結點中比較豐滿(3個元素大於2),所以先向父節點借一個元素w下移到該葉子結點中,代替原來s的位置,s前移;然後x在相鄰右兄弟結點中上移到父結點中,最後在相鄰右兄弟結點中刪除x,後面元素前移。結果如下:

如果上圖中,我們繼續刪除e:

刪除後會導致很多問題,因為e所在的結點數目剛好達標,剛好滿足最小元素個數(ceil(5/2)-1=2),而相鄰的兄弟結點也是同樣的情況,刪除一個元素都不能滿足條件,所以需要該節點與某相鄰兄弟結點進行合併操作;首先移動父結點中的元素(該元素在兩個需要合併的兩個結點元素之間)下移到其子結點中,然後將這兩個結點進行合併成一個結點。所以在該例項中,咱們首先將父節點中的元素d下移到已經刪除e而只有f的結點中,然後將含有d和f的結點和含有a,c的相鄰兄弟結點進行合併成一個結點。結果如下(第一步)

也許你認為這樣刪除操作已經結束了,其實不然,在看看上圖,對於這種特殊情況,你立即會發現父節點只包含一個元素g,沒達標(因為非根節點包括葉子結點的關鍵字數n必須滿足於2=

網頁連結

網頁連結

網頁連結

詳細參見上面三個部落格,寫的更加詳細。

在資料結構中m階b樹是什麼意思呀?

6樓:匿名使用者

b-樹的定義

一棵m(m≥3)階的b-樹是滿足如下性質的m叉樹:

(1)每個結點至少包含下列資料域:

(j,p 0 ,k l ,p 1 ,k 2 ,…,k i ,p i )

其中:j為關鍵字總數

k i (1≤i≤j)是關鍵字,關鍵字序列遞增有序:k 1

p i (0≤i≤j)是孩子指標。對於葉結點,每個p i 為空指標。

注意:①實用中為節省空間,葉結點中可省去指標域p i ,但必須在每個結點中增加一個標誌域leaf,其值為真時表示葉結點,否則為

內部結點。

②在每個內部結點中,假設用keys(pi)來表示子樹pi中的所有關鍵字,則有:

keys(p 0 )

即關鍵字是分界點,任一關鍵字ki左邊子樹中的所有關鍵字均小於k i ,右邊子樹中的所有關鍵字均大於k i 。

(2)所有葉子是在同一層上,葉子的層數為樹的高度h。

(3)每個非根結點中所包含的關鍵字個數j滿足:

(4)若樹非空,則根至少有1個關鍵字,故若根不是葉子,則它至少有2棵子樹。根至多有m-1個關鍵字,故至多有m棵子樹。

M是什麼意思,S M是什麼意思?

s 性格比較強勢,喜歡控制和欺負別人。m 和s剛好相反。屬於被人欺負的還很開心的型別。簡單的說,s和m分別就是虐待狂和受虐狂的意思。自動擋p r n d s l m表示什麼意思 在物理中 s m t s 是什麼意思 s m代表位移,t s代表時間。物理速度關係影象通常有 s t影象 v t影象 橫座...

說女生m是什麼意思,說女生M什麼意思

抖m,意思是指有受nue傾向的一種人,與抖s nue待傾向 正好相反,亦指一種人物性格和心理傾向。有個圈子是字母圈s和m,s是主動放,m是被動方。說她m,就是她是被動方,而且喜歡那種被動。抖m,說好聽點有受虐傾向的那種。女生是說他來大姨媽的意思,大姨媽知道是什麼嗎,就是月經,來這個月經的時候,身體是...

足球裡b2b是什麼意思,B2B是什麼意思啊

b2b 即 box to box 的縮寫,直譯過來就是 從禁區到禁區 在足球領域特指那些奔跑能力強,覆蓋面積大且攻守俱佳的全能型中場。大意就是進攻你能去到對方的禁區,防守時你能回到己方的的這樣的球員一般擁有超強的耐力以及貫穿全場的持續爆發力,當然類似超強控球能力,擺脫能力以及組織能力也是不可缺少的。...