數(shù)據(jù)結(jié)構(gòu)與算法系列(B樹)

B樹

B樹即平衡查找樹竖慧,一般理解為平衡多路查找樹季研,也稱為B-樹鸽疾、B_樹熊尉。是一種自平衡樹狀數(shù)據(jù)結(jié)構(gòu)焚挠,能對存儲的數(shù)據(jù)進(jìn)行O(log n)的時(shí)間復(fù)雜度進(jìn)行查找、插入和刪除碳胳。B樹一般較多用在存儲系統(tǒng)上递沪,比如數(shù)據(jù)庫或文件系統(tǒng)豺鼻。

B樹特點(diǎn)

1.B樹可以定義一個(gè)m值作為預(yù)定范圍,即m路(階)B樹款慨。
1.每個(gè)節(jié)點(diǎn)最多有m個(gè)孩子儒飒。
2.每個(gè)節(jié)點(diǎn)至少有ceil(m/2)個(gè)孩子,除了根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外檩奠。
3.對于根節(jié)點(diǎn)桩了,子樹個(gè)數(shù)范圍為[2,m]附帽,節(jié)點(diǎn)內(nèi)值的個(gè)數(shù)范圍為[1,m-1]。
4.對于非根節(jié)點(diǎn)井誉,節(jié)點(diǎn)內(nèi)的值個(gè)數(shù)范圍為[ceil(m/2)-1,m-1]蕉扮。
5.根節(jié)點(diǎn)(非葉子節(jié)點(diǎn))至少有兩個(gè)孩子。
6.一個(gè)有k個(gè)孩子的非葉子節(jié)點(diǎn)包含k-1個(gè)值颗圣。
7.所有葉子節(jié)點(diǎn)在同一層喳钟。
8.節(jié)點(diǎn)內(nèi)的值按照從小到大排列。
9.父節(jié)點(diǎn)的若干值作為分離值分成多個(gè)子樹在岂,左子樹小于對應(yīng)分離值奔则,對應(yīng)分離值小于右子樹。

以下是一個(gè)四階B樹蔽午,

image

插入
假設(shè)現(xiàn)在構(gòu)建一棵四階B樹易茬,開始插入“A”,直接作為根節(jié)點(diǎn)及老,

image

插入“B”疾呻,大于“A”,放右邊写半,

image

插入“C”,按順序排到最后尉咕,


image

繼續(xù)插入“D”叠蝇,直接添加的結(jié)果如下圖,此時(shí)超過了節(jié)點(diǎn)可以存放容量年缎,對于四階B樹每個(gè)節(jié)點(diǎn)最多存放3個(gè)值悔捶,此時(shí)需要執(zhí)行分裂操作,


image

分裂操作為单芜,先選取待分裂節(jié)點(diǎn)的中值蜕该,這里為“B”,然后將中值“B”放到父節(jié)點(diǎn)中洲鸠,因?yàn)檫@里還沒有父節(jié)點(diǎn)堂淡,那么直接創(chuàng)建一個(gè)新的父節(jié)點(diǎn)存放“B”,而原來小于“B”的那些值作為左子樹扒腕,原來大于“B”的那些值作為右子樹绢淀。

image

繼續(xù)插入“E”,”E”大于“B”瘾腰,往右子節(jié)點(diǎn)皆的,


分別于“C”和“D”比較,大于它們蹋盆,放到最右邊费薄,

image

插入“F”硝全,“F”大于“B”,往右子樹楞抡,


image

“F”分別與“C””D”“E”比較伟众,大于它們,放到最右邊拌倍,此時(shí)觸發(fā)分裂操作赂鲤,


image

選取待分裂節(jié)點(diǎn)的中值“D”,然后將中值“D”放到父節(jié)點(diǎn)中柱恤,父節(jié)點(diǎn)中的“B”小于“D”数初,于是放到“B”右邊,而原來小于“D”的那些值作為左子樹梗顺,原來大于“D”的那些值作為右子樹泡孩。

image

繼續(xù)插入“M”,結(jié)果為寺谤,

image

插入“L’仑鸥,大于“B”“D”,往右子樹变屁,

image

“L”大于“E”“F”小于“M”眼俊,于是放到第三個(gè)位置,此時(shí)觸發(fā)分裂操作粟关,


image

選取待分裂節(jié)點(diǎn)的中值“F”疮胖,然后將中值“F”放到父節(jié)點(diǎn)中,父節(jié)點(diǎn)中的“B”“D”都小于“F”闷板,于是放到最右邊澎灸,而原來小于“F”的那些值作為左子樹,原來大于“F”的那些值作為右子樹遮晚。

image

插入“K”性昭,結(jié)果為,

image

插入“J”县遣,大于“B”“D”“F”糜颠,往右子樹,


image

“J”小于“K”“L”“M”萧求,于是放到第一個(gè)位置括蝠,此時(shí)觸發(fā)分裂操作,

image

選取待分裂節(jié)點(diǎn)的中值“K”饭聚,然后將中值“K”放到父節(jié)點(diǎn)中忌警,父節(jié)點(diǎn)中的“B”“D”“F”都小于“K”,于是放到最右邊,而原來小于“K”的那些值作為左子樹法绵,原來大于“K”的那些值作為右子樹箕速。此時(shí)父節(jié)點(diǎn)也觸發(fā)分裂操作,

image

選取待分裂節(jié)點(diǎn)的中值“D”朋譬,然后將中值“D”放到父節(jié)點(diǎn)中盐茎,由于還沒有父節(jié)點(diǎn),那么直接創(chuàng)建一個(gè)新的父節(jié)點(diǎn)存放“D”徙赢,而原來小于“D”的那些值作為左子樹字柠,原來大于“D”的那些值作為右子樹。

image

插入“I”狡赐,大于“D”窑业,往右子樹,

image

右子樹不是葉子節(jié)點(diǎn)枕屉,繼續(xù)往下常柄,這時(shí)“I”大于“F”而小于“K”,所以往第二個(gè)分支搀擂,


image

“I”小于“J”西潘,于是放到左邊,

image

類似地哨颂,插入“H”喷市,結(jié)果如下,

image

插入“G”威恼,往左子樹品姓,


image

往中間分支,


image

觸發(fā)分裂操作沃测,

image

選取待分裂節(jié)點(diǎn)的中值“H”,然后將中值“H”放到父節(jié)點(diǎn)中食茎,”H”大于父節(jié)點(diǎn)中的“F”而小于“K”蒂破,于是放到中間,而原來小于“H”的那些值作為左子樹别渔,原來大于“H”的那些值作為右子樹附迷。

image

綜上所述,插入操作的核心是分裂操作哎媚。無需分裂的情況比較簡單喇伯,直接插入即可;如果插入后超過節(jié)點(diǎn)容量拨与,這個(gè)容量可預(yù)先自定義稻据,則需要進(jìn)行分裂操作,需要注意的是分裂可能引起父節(jié)點(diǎn)需要繼續(xù)分裂买喧。

查找
對B樹進(jìn)行查找就比較簡單捻悯,查找過程有點(diǎn)類似二叉搜索樹匆赃,從根節(jié)點(diǎn)開始查找,根據(jù)比較數(shù)值找到對應(yīng)的分支今缚,繼續(xù)往子樹上查找算柳。

比如查找“I”,”I”大于“D”姓言,往右子樹瞬项,

image

“I”分別與節(jié)點(diǎn)內(nèi)值比較,大于“F”“H”而小于“K”何荚,往第三個(gè)分支囱淋,

image

逐一比較節(jié)點(diǎn)內(nèi)的值,找到“I”兽泣。


image

轉(zhuǎn)自:https://blog.csdn.net/wangyangzhizhou/article/details/82215430

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末绎橘,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子唠倦,更是在濱河造成了極大的恐慌称鳞,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件稠鼻,死亡現(xiàn)場離奇詭異冈止,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)候齿,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進(jìn)店門熙暴,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人慌盯,你說我怎么就攤上這事周霉。” “怎么了亚皂?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵俱箱,是天一觀的道長。 經(jīng)常有香客問我灭必,道長狞谱,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任禁漓,我火速辦了婚禮跟衅,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘播歼。我一直安慰自己伶跷,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著撩穿,像睡著了一般磷支。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上食寡,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天雾狈,我揣著相機(jī)與錄音,去河邊找鬼抵皱。 笑死善榛,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的呻畸。 我是一名探鬼主播移盆,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼伤为!你這毒婦竟也來了咒循?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤绞愚,失蹤者是張志新(化名)和其女友劉穎叙甸,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體位衩,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡裆蒸,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了糖驴。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片僚祷。...
    茶點(diǎn)故事閱讀 40,872評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖贮缕,靈堂內(nèi)的尸體忽然破棺而出辙谜,到底是詐尸還是另有隱情,我是刑警寧澤感昼,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布装哆,位于F島的核電站,受9級特大地震影響抑诸,放射性物質(zhì)發(fā)生泄漏烂琴。R本人自食惡果不足惜爹殊,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一蜕乡、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧梗夸,春花似錦层玲、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽畔派。三九已至,卻和暖如春润绵,著一層夾襖步出監(jiān)牢的瞬間线椰,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工尘盼, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留憨愉,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓卿捎,卻偏偏與公主長得像配紫,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子午阵,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評論 2 361

推薦閱讀更多精彩內(nèi)容