三分鐘基礎：什麼是 2-3-4 樹

2019 年 11 月 20 日
筆記

1）引言

三分鐘基礎知識：什麼是 2-3 樹？。本篇文章將在 2-3 樹的基礎上更進一步，介紹比 2-3 樹更為複雜的數據結構 2-3-4樹 。之所以介紹 2-3-4 樹是因為 2-3-4 樹與極為重要的紅黑樹有著等價關係，通過先學習2-3-4 樹為後面學習紅黑樹打下基礎，增進對於紅黑樹的理解。

2） 2-3-4樹

2-3 樹不再是單純的二叉樹了，因為 2-3 樹中除了 2- 節點之外還存在 3- 節點。在 2-3 樹的基礎上進一步擴展， 2-3-4 樹在 2-3 樹的基礎上添加 4- 節點。4- 節點可以存儲 3 個鍵值，最多可以擁有 4 棵子樹。

3）定義

（1）每個節點每個節點有 1、2 或 3 個 key ，分別稱為 2- 節點，3- 節點，4- 節點。（2）所有葉子節點到根節點的長度一致（也就是說葉子節點都在同一層）。（3）每個節點的 key 從左到右保持了從小到大的順序，兩個 key 之間的子樹中所有的 key 一定大於它的父節點的左 key ，小於父節點的右 key 。

例如圖 3.1 所示的一棵 2-3-4 樹：

圖3.1

4）查找

2-3-4 樹的查找類似了二叉樹的查找過程，通過鍵值的比較來決定遍歷方向。

例如在圖3.1所示樹中查找22：

例如在圖 3.1 所示樹中查找 15 ：

5）插入

如果 2-3-4 樹中已存在當前插入的 key ，則插入失敗，否則最終一定是在葉子節點中進行插入操作，因為查找過程的結束位置在葉子節點。

5.1 非 4- 節點插入

如果待插入的節點不是 4- 節點，那麼直接在該節點插入。例如在 2- 節點插入：

例如在 3- 節點插入：

5.2 4- 節點插入

如果待插入的節點是個 4- 節點，那麼應該先分裂該節點然後再插入。一個 4- 節點可以分裂成一個根節點和兩個子節點（這三個節點各含一個 key ）然後在子節點中插入，我們把分裂形成的根節點中的 key 看成向上層插入的 key ，然後重複 5.1 和 5.2 。

圖解：

5.3 根節點分裂

如果是在 4 節點中進行插入，每次插入會多出一個分支，如果插入操作導致根節點分裂，則 2-3-4 樹會生長一層。

圖解：

6）刪除

執行刪除之前需要對刪除 key 進行查找，若查找失敗則無法刪除。查找成功，才可刪除 key 。刪除節點情況有以下幾種：

6.1 刪除的節點不為 2- 節點

刪除的節點不為 2- 節點，則將要刪除的目標 key 直接刪除即可。

圖解：

6.2 刪除非葉子節點

當刪除的節點是非葉子節點，無論待刪除節點的 key 是多少個，先使用中序遍歷找到待刪除節點的後繼節點，然後將後繼節點與待刪除節點位置互換，此時就將問題轉化為刪除節點為葉子節點（平衡樹的非葉子節點中序遍歷後繼節點肯定葉子節點），如果該葉子是非 2- 節點，則與 2.4.1 一樣，如果該節點是 2- 節點，則跟後面的 2.4.3 情形一樣。

圖解：

6.3 刪除的葉子節點為 2- 節點

當刪除的葉子節點是 2- 節點，則將節點刪除後，需要對樹進行調整，調整規則如下：

1）當前節點的父節點是 2- 節點，兄弟節點不為 2- 節點，則將兄弟節點的一個 key 上移成父節點，而父節點下移成子節點，此時樹滿足 2-3-4 樹，完成調整。

（2）當前節點的父節點是 2-節點，兄弟節點也為 2- 節點，則此時將父節點與兄弟節點合併，將合併後的節點看成當前節點，然後重複的判斷，即判斷合併後的當前節點的兄弟節點與父節點的情況，然後走對應的（1）（2）（3）處理，直到滿足 2-3-4 樹，完成調整。

（3）當前節點的父節點不為 2- 節點，即此時有兩個或三個兄弟節點，此時需要根據相鄰兄弟節點情形進行調整，規則如下：

（3）-a：若當前節點的相鄰兄弟節點為非 3 個 key ，則父節點的一個 key 下移，與相鄰兄弟節點合併，此時樹滿足2-3樹，完成調整。（3）-b：若當前節點的相鄰兄弟節點為 3 個 key ，則父節點的一個 key 下移成 1 個 key 的節點，相鄰兄弟節點的一個 key 上移與父節點合併，此時樹滿足 2-3-4 樹，完成調整。

圖解：

圖解：

圖解：

7）結語

本篇文章主要介紹了 2-3-4 樹的性質，以及插入刪除等操作。介紹 2-3-4 樹的目的主要是為了為後續學習紅黑樹和B- 樹打下一個基礎。紅黑樹可以看這裡：傻瓜都能看懂，30張圖徹底理解紅黑樹！