1、2-3-4樹

在二叉樹中，每個(gè)節(jié)點(diǎn)有一個(gè)數(shù)據(jù)項(xiàng)，最多有兩個(gè)子節(jié)點(diǎn)。如果允許每個(gè)節(jié)點(diǎn)可以有更多的數(shù)據(jù)項(xiàng)和更多的子節(jié)點(diǎn)，就是多叉樹（multiway tree）。

2-3-4樹就是一種階為4的多叉樹，它像紅黑樹一樣是平衡樹，可以保證在O(lgn)的時(shí)間內(nèi)完成查找、插入和刪除操作，容易實(shí)現(xiàn)，但是效率比紅黑樹稍差。

下圖展示了一顆2-3-4樹：

1.png

它有如下特點(diǎn)：

• 每個(gè)節(jié)點(diǎn)可以保存一個(gè)、兩個(gè)或者三個(gè)數(shù)據(jù)項(xiàng)。
• 底層的六個(gè)節(jié)點(diǎn)都是葉節(jié)點(diǎn)，所有的葉節(jié)點(diǎn)都是在一層上的
• 非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)總數(shù)總是比它含有的數(shù)據(jù)項(xiàng)大1

2-3-4樹中的2、3、4的含義指的是一個(gè)節(jié)點(diǎn)可能含有的子節(jié)點(diǎn)數(shù)。對(duì)非子葉節(jié)點(diǎn)有三種可能的情況：

• 有一個(gè)數(shù)據(jù)項(xiàng)的節(jié)點(diǎn)總是有兩個(gè)子節(jié)點(diǎn)
• 有兩個(gè)數(shù)據(jù)項(xiàng)的節(jié)點(diǎn)總是有三個(gè)子節(jié)點(diǎn)
• 有三個(gè)數(shù)據(jù)項(xiàng)的節(jié)點(diǎn)重是有四個(gè)子節(jié)點(diǎn)

上述的重要的關(guān)系決定了2-3-4樹的結(jié)構(gòu)，比較而言，葉節(jié)點(diǎn)沒有子節(jié)點(diǎn)，然而它可能還有一個(gè)、兩個(gè)、三個(gè)數(shù)據(jù)項(xiàng)，而空節(jié)點(diǎn)是不會(huì)存在的。在2-3-4樹中不允許只有一個(gè)鏈接。有一個(gè)數(shù)據(jù)項(xiàng)的節(jié)點(diǎn)必須總是保持兩個(gè)連接，除非它是葉節(jié)點(diǎn)，在那種情況下沒有連接。

如下圖所示，有兩個(gè)鏈接的節(jié)點(diǎn)被稱為2-節(jié)點(diǎn)，有三個(gè)鏈接的節(jié)點(diǎn)被稱為3-節(jié)點(diǎn)，有四個(gè)鏈接的節(jié)點(diǎn)被稱為4-節(jié)點(diǎn)。

2.png

樹結(jié)構(gòu)中很重要的一點(diǎn)就是它的鏈接與自己數(shù)據(jù)項(xiàng)的關(guān)鍵字之間的關(guān)系。二叉樹中，所有關(guān)鍵字比某個(gè)節(jié)點(diǎn)值小的節(jié)點(diǎn)都在左子樹中，所有關(guān)鍵字比某個(gè)值大的節(jié)點(diǎn)都在右子樹，2-3-4樹的規(guī)則與之類似：

3.png

1.1 插入

• 如果2-3-4樹中已存在當(dāng)前插入的key，則插入失敗，否則最終一定是在葉子節(jié)點(diǎn)中進(jìn)行插入操作
• 如果待插入的節(jié)點(diǎn)不是4-節(jié)點(diǎn)，那么直接在該節(jié)點(diǎn)插入
• 如果待插入的節(jié)點(diǎn)是個(gè)4-節(jié)點(diǎn)，那么應(yīng)該先分裂該節(jié)點(diǎn)然后再插入。一個(gè)4-節(jié)點(diǎn)可以分裂成一個(gè)根節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)（這三個(gè)節(jié)點(diǎn)各含一個(gè)key）然后在子節(jié)點(diǎn)中插入，我們把分裂形成的根節(jié)點(diǎn)中的key看成向上層插入的key，然后重復(fù)第2步和第3步。

如果是在4-節(jié)點(diǎn)中進(jìn)行插入，每次插入會(huì)多出一個(gè)分支，如果插入操作導(dǎo)致根節(jié)點(diǎn)分裂，則2-3-4樹會(huì)生長(zhǎng)一層。

4.png

5.png

6.png

7.png

8.png

1.2 帶預(yù)分裂的插入

上面的插入操作在某些情況需要不斷回溯來(lái)調(diào)整樹的結(jié)構(gòu)以達(dá)到平衡。為了消除回溯過(guò)程，在插入操作過(guò)程中我們可以采取預(yù)分裂的操作，即我們?cè)诓迦氲乃阉髀窂街校龅?-節(jié)點(diǎn)就分裂（分裂后形成的根節(jié)點(diǎn)的key要上移，與父節(jié)點(diǎn)中的key合并）這樣可以保證找到需要插入節(jié)點(diǎn)時(shí)可以直接插入（即該節(jié)點(diǎn)一定不是4節(jié)點(diǎn)）。

9.png

10.png

11.png

12.png

13.png

1.3 刪除

• 如果2-3-4樹中不存在當(dāng)前需要?jiǎng)h除的key，則刪除失敗。
• 如果當(dāng)前需要?jiǎng)h除的key不位于葉子節(jié)點(diǎn)上，則用后繼key覆蓋，然后在它后繼key所在的子支中刪除該后繼key。
• 如果當(dāng)前需要?jiǎng)h除的key位于葉子節(jié)點(diǎn)上:
  • 該節(jié)點(diǎn)不是2-節(jié)點(diǎn)，刪除key，結(jié)束
  • 該節(jié)點(diǎn)是2-節(jié)點(diǎn)，刪除該節(jié)點(diǎn)：
    • 如果兄弟節(jié)點(diǎn)不是2-節(jié)點(diǎn)，則父節(jié)點(diǎn)中的key下移到該節(jié)點(diǎn)，兄弟節(jié)點(diǎn)中的一個(gè)key上移
    • 如果兄弟節(jié)點(diǎn)是2-節(jié)點(diǎn)，父節(jié)點(diǎn)是個(gè)3-節(jié)點(diǎn)或4-節(jié)點(diǎn)，父節(jié)點(diǎn)中的key與兄弟節(jié)點(diǎn)合并
    • 如果兄弟節(jié)點(diǎn)是2-節(jié)點(diǎn)，父節(jié)點(diǎn)是個(gè)2-節(jié)點(diǎn)，父節(jié)點(diǎn)中的key與兄弟節(jié)點(diǎn)中的key合并，形成一個(gè)3-節(jié)點(diǎn)，把此節(jié)點(diǎn)看成當(dāng)前節(jié)點(diǎn)（此節(jié)點(diǎn)實(shí)際上是下一層的節(jié)點(diǎn)），重復(fù)步驟3.2.1到3.2.3

如果是在2節(jié)點(diǎn)（葉子節(jié)點(diǎn)）中進(jìn)行刪除，每次刪除會(huì)減少一個(gè)分支，如果刪除操作導(dǎo)致根節(jié)點(diǎn)參與合并，則2-3-4樹會(huì)降低一層。

14.png

15.png

16.png

17.png

18.png

1.4 帶有預(yù)合并的刪除

在刪除過(guò)程中，我們同樣可以采取預(yù)合并的操作，即我們?cè)趧h除的搜索路徑中（除根節(jié)點(diǎn)，因?yàn)楦?jié)點(diǎn)沒有兄弟節(jié)點(diǎn)和父節(jié)點(diǎn)），遇到當(dāng)前節(jié)點(diǎn)是2節(jié)點(diǎn)，如果兄弟節(jié)點(diǎn)也是2節(jié)點(diǎn)就合并（該節(jié)點(diǎn)的父節(jié)點(diǎn)中的key下移，與自身和兄弟節(jié)點(diǎn)合并）；如果兄弟節(jié)點(diǎn)不是2節(jié)點(diǎn)，則父節(jié)點(diǎn)的key下移，兄弟節(jié)點(diǎn)中的key上移。這樣可以保證，找到需要?jiǎng)h除的key所在的節(jié)點(diǎn)時(shí)可以直接刪除（即要?jiǎng)h除的key所在的節(jié)點(diǎn)一定不是2節(jié)點(diǎn)）。

19.png

20.png

21.png

22.png

23.png

2、2-3樹

2-3樹也是一種多叉樹，與2-3-4樹類似，現(xiàn)在在很多應(yīng)用程序中還在應(yīng)用，一些用于2-3樹的技術(shù)會(huì)在B-樹中應(yīng)用。

2-3樹比2-3-4樹少一個(gè)數(shù)據(jù)項(xiàng)和一個(gè)子節(jié)點(diǎn)。節(jié)點(diǎn)可以保存1個(gè)或者2個(gè)數(shù)據(jù)項(xiàng)，可以有0個(gè)、1個(gè)、2個(gè)或者3個(gè)子節(jié)點(diǎn)。其它方面，父節(jié)點(diǎn)和子節(jié)點(diǎn)的關(guān)鍵字值的排列順序和2-3-4樹是一樣的。

24.png

不同的是， 2-3樹節(jié)點(diǎn)分裂是自底向上的(不能進(jìn)行預(yù)分裂)，而且2-3樹節(jié)點(diǎn)分裂必須用到新數(shù)據(jù)項(xiàng)。

2.1 插入

• 如果2-3樹中已存在當(dāng)前插入的key，則插入失敗，否則最終一定是在葉子節(jié)點(diǎn)中進(jìn)行插入操作。
• 如果待插入的節(jié)點(diǎn)只有1個(gè)key，則直接插入即可。
• 如果待插入的節(jié)點(diǎn)有2個(gè)key，則對(duì)節(jié)點(diǎn)進(jìn)行分裂，即2個(gè)key加上待插入的key，這3個(gè)key分裂成1個(gè)key跟兩個(gè)子節(jié)點(diǎn)，然后將分裂之后的3個(gè)key中的父節(jié)點(diǎn)看作向上層插入的key，然后重復(fù)第2步、第3步，直到滿足2-3樹的定義性質(zhì)。

25.png

26.png

2.2 刪除

2-3樹有4種節(jié)點(diǎn)：

• 僅1個(gè)key的葉子節(jié)點(diǎn)
• 有 2個(gè)key的葉子節(jié)點(diǎn)
• 僅1個(gè)key的非葉子節(jié)點(diǎn)
• 有2個(gè)key的非葉子節(jié)點(diǎn)

即 1個(gè)key與2個(gè)key的節(jié)點(diǎn) 和 是否為葉子節(jié)點(diǎn) 的組合。下面就從簡(jiǎn)單到復(fù)雜的情況開始分析：

1. 當(dāng)刪除的節(jié)點(diǎn)是2個(gè)key的葉子節(jié)點(diǎn)，則將要?jiǎng)h除的目標(biāo)key刪除即可，此時(shí)原來(lái)待刪除的2個(gè)key的葉子節(jié)點(diǎn)，變成1個(gè)key的葉子節(jié)點(diǎn)，但是符合2-3樹；

2. 當(dāng)刪除的節(jié)點(diǎn)是2個(gè)key的非葉子節(jié)點(diǎn)，則此時(shí)使用中序遍歷找到待刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)，然后將后繼節(jié)點(diǎn)與待刪除節(jié)點(diǎn)位置互換，此時(shí)就將問(wèn)題轉(zhuǎn)化為刪除節(jié)點(diǎn)為葉子節(jié)點(diǎn)（平衡樹的非葉子節(jié)點(diǎn)中序遍歷后繼節(jié)點(diǎn)肯定是葉子節(jié)點(diǎn)），如果該葉子是2個(gè)key，則跟情況1一樣，如果該節(jié)點(diǎn)是只有1個(gè)key，則跟后面的情況4一樣；

3. 當(dāng)刪除的節(jié)點(diǎn)是1個(gè)key的非葉子節(jié)點(diǎn)，實(shí)際上操作跟情況（2）是一樣的，即使用中序遍歷找到待刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)，然后將后繼節(jié)點(diǎn)與待刪除節(jié)點(diǎn)位置互換，此時(shí)問(wèn)題轉(zhuǎn)化為刪除節(jié)點(diǎn)為葉子節(jié)點(diǎn)；

4. 當(dāng)刪除的節(jié)點(diǎn)是1個(gè)key的葉子節(jié)點(diǎn)，則將節(jié)點(diǎn)刪除，此時(shí)樹肯定不滿足2-3樹的性質(zhì)，也即肯定需要調(diào)整，但要分情況來(lái)進(jìn)行調(diào)整，而總結(jié)起來(lái)就是當(dāng)前待刪除節(jié)點(diǎn)的兄弟節(jié)點(diǎn)與父節(jié)點(diǎn)，分別是1個(gè)key還是2個(gè)key，即：

1)當(dāng)父節(jié)點(diǎn)是1個(gè)key（即此時(shí)僅有一個(gè)兄弟節(jié)點(diǎn)），兄弟節(jié)點(diǎn)是2個(gè)key，則將兄弟節(jié)點(diǎn)的一個(gè)key上移成父節(jié)點(diǎn)，而父節(jié)點(diǎn)下移成子節(jié)點(diǎn)，也即跟2個(gè)key中插入新節(jié)點(diǎn)類似，拆成一父兩子，此時(shí)樹滿足2-3樹，完成調(diào)整。

2)當(dāng)父節(jié)點(diǎn)是1個(gè)key，兄弟節(jié)點(diǎn)也是1個(gè)key，則此時(shí)將父節(jié)點(diǎn)與兄弟節(jié)點(diǎn)合并，將合并后的節(jié)點(diǎn)看成當(dāng)前節(jié)點(diǎn)，然后重復(fù)4的判斷，即判斷合并后的當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)與父節(jié)點(diǎn)的情況，然后走對(duì)應(yīng)的1)、2）、3）處理，直到滿足2-3樹，完成調(diào)整。

3)當(dāng)父節(jié)點(diǎn)是2個(gè)key，即此時(shí)有兩個(gè)兄弟節(jié)點(diǎn)，而兄弟節(jié)點(diǎn)又可能有多種情況，窮舉起來(lái)有：刪除節(jié)點(diǎn)的位置左中右3個(gè)，以及另外兩個(gè)兄弟節(jié)點(diǎn)是否為1個(gè)key或2個(gè)key的4種情況，總共3*4=12種。即：

i.若刪除的是左或右節(jié)點(diǎn)，且中間節(jié)點(diǎn)只有1個(gè)key，則此時(shí)父節(jié)點(diǎn)的一個(gè)key下移，與中間節(jié)點(diǎn)合并，此時(shí)父節(jié)點(diǎn)為1個(gè)key，兩個(gè)子節(jié)點(diǎn)，樹滿足2-3樹，完成調(diào)整；
ii.若刪除的是左或右節(jié)點(diǎn)，且中間節(jié)點(diǎn)有2個(gè)key，則此時(shí)父節(jié)點(diǎn)的一個(gè)key下移，中間節(jié)點(diǎn)的一個(gè)key上移與父節(jié)點(diǎn)合并，此時(shí)父節(jié)點(diǎn)為2個(gè)key，3個(gè)子節(jié)點(diǎn)，樹滿足2-3樹，完成調(diào)整；
iii.若刪除的是中間節(jié)點(diǎn)，且右節(jié)點(diǎn)只有1個(gè)key，則此時(shí)父節(jié)點(diǎn)的一個(gè)key下移，與右節(jié)點(diǎn)合并，此時(shí)父節(jié)點(diǎn)為1個(gè)key，兩個(gè)子節(jié)點(diǎn)，樹滿足2-3樹，完成調(diào)整；
iv.若刪除的是中間節(jié)點(diǎn)，且右節(jié)點(diǎn)有2個(gè)key，則此時(shí)父節(jié)點(diǎn)的一個(gè)key下移，右節(jié)點(diǎn)的一個(gè)key上移與父節(jié)點(diǎn)合并，此時(shí)父節(jié)點(diǎn)為2個(gè)key，3個(gè)子節(jié)點(diǎn)，樹滿足2-3樹，完成調(diào)整。

綜述：i與ii刪除左或右節(jié)點(diǎn)兩種情況，中間節(jié)點(diǎn)1個(gè)key或2個(gè)key兩種情況，兄弟節(jié)點(diǎn)1個(gè)key或2個(gè)key兩種情況，總共 2x2x2=8 種；刪除中間節(jié)點(diǎn)一種情況，iii與iv右節(jié)點(diǎn)1個(gè)key或2個(gè)key兩種情況，左節(jié)點(diǎn)1個(gè)或2個(gè)key兩種情況，總共 1x2x2=4 種； 4+8=12 種全齊，雖然場(chǎng)景有12種，但是處理的方式只有2種，一種是父節(jié)點(diǎn)下移與子節(jié)點(diǎn)合并，另一種是父節(jié)點(diǎn)下移成單獨(dú)一個(gè)子節(jié)點(diǎn)，然后2個(gè)key的子節(jié)點(diǎn)上移一個(gè)key與父節(jié)點(diǎn)合并。

最簡(jiǎn)單的刪除情況1，待刪除的節(jié)點(diǎn)是2個(gè)key，直接對(duì)節(jié)點(diǎn)的key “5” 刪除即可：

27.png

若刪除節(jié)點(diǎn)是情況2，如下圖所示，刪除“100”，而且此時(shí)“100”是非葉子節(jié)點(diǎn)且2個(gè)key，則找到后繼節(jié)點(diǎn)“120”與“100”互換位置，然后刪除“100”：

28.png

結(jié)果如下圖所示，將問(wèn)題轉(zhuǎn)化為刪除一個(gè)key的葉子節(jié)點(diǎn)，且父節(jié)點(diǎn)為2個(gè)key，即為情況4，刪除的節(jié)點(diǎn)為右節(jié)點(diǎn)，且中間節(jié)點(diǎn)為一個(gè)key，也即為情況4中3）的1，所以此時(shí)需要將父節(jié)點(diǎn)的一個(gè)key下移與中間節(jié)點(diǎn)合并：

29.png

30.png

再講另外一種，情況4中3）的iv，如下圖所示，刪除節(jié)點(diǎn)“22”，而右兄弟節(jié)點(diǎn)是2個(gè)key，則需要將父節(jié)點(diǎn)的“30”下移成中間節(jié)點(diǎn)，然后右兄弟的一個(gè)key“40”上移與父節(jié)點(diǎn)合并：

31.png

32.png

最后再講一種節(jié)點(diǎn)刪除的情況，就是滿二叉樹的情況，根據(jù)定義的性質(zhì)，滿二叉樹也符合2-3樹，如果當(dāng)滿二叉樹要?jiǎng)h除葉子節(jié)點(diǎn)時(shí)，是符合情況4中的2）的，即將父節(jié)點(diǎn)與兄弟節(jié)點(diǎn)合并，此時(shí)樹的層數(shù)顯然不平衡，即，將合并后的節(jié)點(diǎn)看作被刪除的當(dāng)前節(jié)點(diǎn)，而當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)與父節(jié)點(diǎn)依然是都是一個(gè)key，符合情況4的2），將父節(jié)點(diǎn)與兄弟節(jié)點(diǎn)合并，直至樹平衡。

33.png

另外，實(shí)際上節(jié)點(diǎn)刪除的情況中2、3是可以整合到一起去處理的，即，刪除節(jié)點(diǎn)是非葉子節(jié)點(diǎn)，無(wú)論待刪除節(jié)點(diǎn)的key數(shù)是多少，都用中序排序找到后繼節(jié)點(diǎn)，然后把問(wèn)題轉(zhuǎn)化為刪除一個(gè)key的葉子節(jié)點(diǎn)去處理。
對(duì)于節(jié)點(diǎn)刪除中的4的 2）再補(bǔ)充說(shuō)明一下，如下圖刪除節(jié)點(diǎn)“10”，符合4的 2） 情況，則父節(jié)點(diǎn)“13”與兄弟節(jié)點(diǎn)“18”合并，：

34.png

合并之后如下圖所示，此時(shí)符合4中 3） 的 ii 情況，則父節(jié)點(diǎn)的key“22”下移，中間節(jié)點(diǎn)的key“30”上移：

35.png

變換結(jié)果如下圖所示，此時(shí)2-3樹已經(jīng)調(diào)整完成。這里需要注意的點(diǎn)是，由于之前說(shuō)父子節(jié)點(diǎn)key的上下移對(duì)于葉子節(jié)點(diǎn)來(lái)說(shuō)并沒有子節(jié)點(diǎn)，但對(duì)于非葉子節(jié)點(diǎn)的變換是對(duì)應(yīng)左旋與右旋的，所以上一步的變換，是以節(jié)點(diǎn)“22”做左旋操作，由父節(jié)點(diǎn)“降級(jí)”為子節(jié)點(diǎn)，而原本子節(jié)點(diǎn)“30”晉升為父節(jié)點(diǎn)，并將“30”的左子節(jié)點(diǎn)出讓給“22”作為右子節(jié)點(diǎn)：

36.png