B-樹的刪除過(guò)程介紹
上文http://www.fzitv.net/article/154157.htm我們介紹了B-樹的插入過(guò)程，本文我們來(lái)介紹B-樹的刪除過(guò)程。
在B-樹中刪除節(jié)點(diǎn)時(shí)，可能會(huì)發(fā)生向兄弟節(jié)點(diǎn)借元素，和孩子節(jié)點(diǎn)交換元素，甚至節(jié)點(diǎn)合并的過(guò)程。
我們以下面的樹為基礎(chǔ)，進(jìn)行刪除操作。
首先明確一下這個(gè)樹的定義。它是一個(gè)5階樹。所以，每個(gè)節(jié)點(diǎn)內(nèi)元素個(gè)數(shù)為2~4個(gè)。
我們依次刪除8、16、15、4這4個(gè)元素。
首先刪除8，因?yàn)閯h除8后，不破壞樹的性質(zhì)，所以直接刪除即可。得到如下
然后刪除16，這導(dǎo)致該節(jié)點(diǎn)只剩下一個(gè)13節(jié)點(diǎn)，不滿足節(jié)點(diǎn)內(nèi)元素個(gè)數(shù)為2~4個(gè)的要求了。所以需要調(diào)整。這里可以向孩子借節(jié)點(diǎn)，把17提升上來(lái)即可，得到下圖。這里不能和兄弟節(jié)點(diǎn)借節(jié)點(diǎn)，因?yàn)閺?，6節(jié)點(diǎn)中把6借走后，剩下的3也不滿要求了。另外，也不能把孩子中的15提升上來(lái)，那樣會(huì)導(dǎo)致剩下的14不滿足要求。
然后刪除15，刪除15后同樣需要調(diào)整。調(diào)整的方式是，18上升，17下降到原來(lái)15的位置，得到下圖。
然后刪除元素4，刪除4后該節(jié)點(diǎn)只剩下5，需要調(diào)整?？墒撬男值芄?jié)點(diǎn)也都沒有多余的節(jié)點(diǎn)可借，所以需要進(jìn)行節(jié)點(diǎn)合并。節(jié)點(diǎn)合并時(shí)，方式會(huì)有多種，我們選擇其中的一種即可。這里，我們選擇父節(jié)點(diǎn)中的3下沉，和1，2，以及5進(jìn)行合并，如下圖。
但這次調(diào)整，導(dǎo)致6不符合要求了。另外，6非根節(jié)點(diǎn)，但只有2個(gè)孩子，也不符合要求。需要繼續(xù)調(diào)整。調(diào)整的方式是，將10下沉，和6，以及13，18合并為根節(jié)點(diǎn)，如下圖。
結(jié)束。
總結(jié)
以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請(qǐng)查看下面相關(guān)鏈接
相關(guān)文章
MySQL數(shù)據(jù)表基本操作實(shí)例詳解
這篇文章主要介紹了MySQL數(shù)據(jù)表基本操作,結(jié)合實(shí)例形式較為詳細(xì)的分析了MySQL針對(duì)數(shù)據(jù)表的基本創(chuàng)建、表結(jié)構(gòu)查看、修改、刪除等相關(guān)操作技巧,需要的朋友可以參考下2018-06-06
這篇文章主要介紹了MySQL數(shù)據(jù)庫(kù)node使用,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-06-06
SQL實(shí)現(xiàn)數(shù)據(jù)過(guò)濾流程詳解
這篇文章主要介紹了SQL實(shí)現(xiàn)數(shù)據(jù)過(guò)濾流程，當(dāng)我們?cè)赟QL中查詢數(shù)據(jù)時(shí)，肯定是有一些數(shù)據(jù)是我們不需要的，所以我們此時(shí)就要對(duì)數(shù)據(jù)進(jìn)行過(guò)濾，以篩選出我們僅需要的數(shù)據(jù)2023-01-01
查詢數(shù)據(jù)庫(kù)空間(mysql和oracle)
本文通過(guò)代碼示例詳細(xì)介紹了如何查詢MySQL數(shù)據(jù)空間和Oracle數(shù)據(jù)空間，具有一定的參考價(jià)值，感興趣的小伙伴可以參考閱讀2023-04-04
windows 64位下mysql 8.0.13 安裝配置方法圖文教程
這篇文章主要為大家詳細(xì)介紹了windows 64位下mysql 8.0.13 安裝配置方法圖文教程，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-11-11
這篇文章主要介紹了Mysql中的Btree與Hash索引比較,本文起講解了B-Tree 索引特征、Hash 索引特征等內(nèi)容,需要的朋友可以參考下2015-03-03
Range分區(qū)是最常用的一種分區(qū)類型,它是根據(jù)某個(gè)列的值劃分為幾個(gè)連續(xù)的區(qū),行數(shù)據(jù)根據(jù)該列的值分別放入到不同的分區(qū),這篇文章主要給大家介紹了關(guān)于MySQL分區(qū)之RANGE分區(qū)的相關(guān)資料,需要的朋友可以參考下2022-04-04
這篇文章主要給大家介紹了關(guān)于MySQL如何為字段添加默認(rèn)時(shí)間的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者使用MySQL具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-10-10
這篇文章主要為大家詳細(xì)介紹了Centos7.3下mysql5.7安裝配置教程，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-09-09
這篇文章主要介紹了MySQL load語(yǔ)句詳細(xì)介紹,本文講解了load的基本語(yǔ)法、文件的路徑、配置選項(xiàng)、STARTING LINES選項(xiàng)、TERMINATED LINES選項(xiàng)等內(nèi)容,需要的朋友可以參考下2014-12-12