????????普通樹(shù)一個(gè)結(jié)點(diǎn)可以有多個(gè)孩子，但它本身只能存儲(chǔ)一個(gè)元素，而二叉樹(shù)結(jié)點(diǎn)最多只能有兩個(gè)，這對(duì)于元素非常多的時(shí)候，會(huì)使得樹(shù)的度或者是高度會(huì)非常大。這就使得內(nèi)存存取外存的次數(shù)會(huì)增多，一旦涉及到外部存儲(chǔ)設(shè)備，時(shí)間復(fù)雜度的計(jì)算就會(huì)受到影響，所以為了降低對(duì)外存設(shè)備的訪問(wèn)次數(shù)，就引入了一個(gè)叫多路查找樹(shù)(mutil-way search tree)的數(shù)據(jù)結(jié)構(gòu)。

????????多路查找樹(shù)，其每一個(gè)結(jié)點(diǎn)的孩子數(shù)可以多于兩個(gè)，且每一個(gè)結(jié)點(diǎn)可以存儲(chǔ)多個(gè)元素。多路查找樹(shù)有查找的性質(zhì)，所以，所有元素之間又存在著特定的排序關(guān)系。多路查找樹(shù)的4種特殊形式：2-3樹(shù)、2-3-4樹(shù)、B樹(shù)和B+樹(shù)

? ? ? ? 最開(kāi)始說(shuō)說(shuō)最簡(jiǎn)單的B樹(shù)，2-3樹(shù)

????????1.1 概念

????????2-3樹(shù)其中的每個(gè)非葉子結(jié)點(diǎn)都具有兩個(gè)孩子(2結(jié)點(diǎn))或三個(gè)孩子(3結(jié)點(diǎn))。高度為h的2-3樹(shù)結(jié)點(diǎn)數(shù)至少有2^h - 1個(gè)。

????????2結(jié)點(diǎn)包含一個(gè)元素S和兩個(gè)孩子(或沒(méi)有孩子)。元素S大于左子樹(shù)包含的元素，小于右子樹(shù)包含的元素。

????????3結(jié)點(diǎn)包含兩個(gè)元素S和L以及三個(gè)孩子(或沒(méi)有孩子)。元素S大于左子樹(shù)包含的元素且小于中間子樹(shù)包含的元素，元素L大于中間子樹(shù)包含的元素小于右子樹(shù)包含的元素。

????????且所有葉子結(jié)點(diǎn)都在同一層次。

????????1.2 操作2-3樹(shù)

????????1.2.1 查找元素

????????2-3樹(shù)的查找方式與二叉樹(shù)類似，根據(jù)元素與結(jié)點(diǎn)的大小比對(duì)決定后續(xù)路線。如上圖，我需要找個(gè)10，首先2結(jié)點(diǎn)10 > 8，往右子樹(shù)找；下一結(jié)點(diǎn)包含兩個(gè)元素，為3結(jié)點(diǎn)，10 < 12，往左子樹(shù)找；左子樹(shù)中比較查找得到10。

????????1.2.2 插入

????????2-3樹(shù)的插入操作與二叉樹(shù)相同，插入操作一定是發(fā)生在葉子節(jié)點(diǎn)上。

????????1)對(duì)于一個(gè)空樹(shù)來(lái)說(shuō)，插入一個(gè)2結(jié)點(diǎn)即可

??????? 2)插入結(jié)點(diǎn)到一個(gè)2結(jié)點(diǎn)的葉子上，由于其本身就一個(gè)元素，所以只需要將其變成3結(jié)點(diǎn)即可。

????????如上圖，我希望插入一個(gè)元素3，根據(jù)遍歷，3 < 8，3 < 4，于是考慮插入到葉子結(jié)點(diǎn)1所在位置，3 > 1，于是3在1的右邊兒。

??????? 3)往3結(jié)點(diǎn)插入一個(gè)新元素，就需要將其拆分，且將樹(shù)中兩元素或插入元素的三者中選擇其一向上移動(dòng)一層。

????????來(lái)看看第一種情況，插入的元素是5，被插入的結(jié)點(diǎn)是(6,7)，是一個(gè)3結(jié)點(diǎn)，當(dāng)父節(jié)點(diǎn)是2節(jié)點(diǎn)，這時(shí)候考慮將567其中一人升一級(jí)，4 < 5 < 6， 5 < 6 < 7，將6提上一層，讓父節(jié)點(diǎn)變?yōu)?節(jié)點(diǎn)，5插入變成中間子樹(shù)，剩下一個(gè)7為右子樹(shù)

????????另一種情況，插入的元素是11，11 < 12，顯然，11應(yīng)該插入到3節(jié)點(diǎn)(9,10)中，但(9,10)節(jié)點(diǎn)不能再插入元素了，于是考慮將11插入到(12,14)節(jié)點(diǎn)中，這時(shí)候8 < 11 < 12,所以，將12向上提一層，這時(shí)候，原來(lái)的擁有8元素的2結(jié)點(diǎn)變?yōu)榱?結(jié)點(diǎn)，剩下的11,9,10需要考慮將他們變?yōu)橹凶訕?shù)

????????1.2.3 刪除

??????? 1)所刪除的元素位于3結(jié)點(diǎn)的葉子結(jié)點(diǎn)上直接刪除即可。因?yàn)?結(jié)點(diǎn)中肯定是包含兩個(gè)元素的，直接刪除也不會(huì)影響到2-3樹(shù)的結(jié)構(gòu)變化。如圖，我想要把元素9刪除，那么我直接剔除元素9即可

??????? 2)刪除的元素位于2結(jié)點(diǎn)上，即刪除的是只有一個(gè)元素的結(jié)點(diǎn)，相當(dāng)于對(duì)結(jié)點(diǎn)進(jìn)行刪除操作。這個(gè)時(shí)候如果直接把結(jié)點(diǎn)刪除，便會(huì)不符合2-3樹(shù)的定義(無(wú)子結(jié)點(diǎn)或必須擁有N個(gè)子節(jié)點(diǎn))。如，我想要?jiǎng)h除元素1，結(jié)點(diǎn)4本來(lái)是擁有子結(jié)點(diǎn)1與子結(jié)點(diǎn)6,7的，此時(shí)少了結(jié)點(diǎn)1，便不符合2-3樹(shù)的定義了。

????????于是，對(duì)于刪除的元素處于2結(jié)點(diǎn)的位置時(shí)候，需要分四種情況考慮：

????????第一種，結(jié)點(diǎn)雙親也是2結(jié)點(diǎn)，且擁有一個(gè)3結(jié)點(diǎn)的孩子，正如上圖，那么這時(shí)候只需要左旋，將6元素提上一層即可

????????第二種，結(jié)點(diǎn)的雙親是2結(jié)點(diǎn)，右孩子也是2結(jié)點(diǎn)。這個(gè)時(shí)候就不能像上一種情況那樣直接左旋，這樣會(huì)造成新的樹(shù)形沒(méi)有右孩子，因此需要對(duì)整棵樹(shù)進(jìn)行變形，來(lái)讓擁有7元素的這個(gè)結(jié)點(diǎn)變?yōu)?結(jié)點(diǎn)。比如，我刪除了一個(gè)元素4的結(jié)點(diǎn)。這個(gè)時(shí)候需要讓8加入到元素7的結(jié)點(diǎn)中，然后讓右子樹(shù)最小的一位元素9到頂層最后左旋即可。

????????情形三，此節(jié)點(diǎn)的雙親是一個(gè)3結(jié)點(diǎn)。比如說(shuō)我刪除一個(gè)元素10，這個(gè)時(shí)候只需要將3結(jié)點(diǎn)的小元素降下來(lái)，然后與中子樹(shù)的合為一個(gè)3結(jié)點(diǎn)即可。

????????情形四，當(dāng)前的2-3樹(shù)為一個(gè)滿二叉樹(shù)，這個(gè)時(shí)候，刪除任何一個(gè)葉子都需要讓整棵樹(shù)變形。我從下圖中刪除一個(gè)8元素的結(jié)點(diǎn)，這個(gè)時(shí)候9肯定不能單獨(dú)作為一個(gè)2結(jié)點(diǎn)存在了，考慮到2-3樹(shù)的性質(zhì)，6與7合為一個(gè)3結(jié)點(diǎn)，放左子樹(shù)，14提上一層，13當(dāng)做一個(gè)中子樹(shù)，15作為一個(gè)右子樹(shù)

總結(jié)

以上是生活随笔為你收集整理的用table展示树形结构数据_复习一下数据结构（二）——2.2 树形索引（23树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。