前言

前面講到了二叉搜索樹 (BST) 和二叉平衡樹 (AVL) ，二叉搜索樹在最好的情況下搜索的時間復(fù)雜度為 O(logn) ，但如果插入節(jié)點時，插入元素序列本身就是有序的，那么BST樹就退化成一個線性表了，搜索的時間復(fù)雜度為 O(n)。
如果想要減少比較次數(shù)，就需要降低樹的高度。在插入和刪除節(jié)點時，要保證插入節(jié)點后不能使葉子節(jié)點之間的深度之差大于 1，這樣就能保證整棵樹的深度最小，這就是AVL 樹解決 BST 搜索性能降低的策略。但由于每次插入或刪除節(jié)點后，都可能會破壞 AVL 的平衡，而要動態(tài)保證 AVL 的平衡需要很多操作，這些操作會影響整個數(shù)據(jù)結(jié)構(gòu)的性能，除非是在樹的結(jié)構(gòu)變化特別少的情形下，否則 AVL 樹平衡帶來的搜索性能提升有可能還不足為了平衡樹所帶來的性能損耗。
因此，引入了 2-3 樹來提升效率。2-3 樹本質(zhì)也是一種平衡搜索樹，但 2-3 樹已經(jīng)不是一棵二叉樹了，因為 2-3 樹允許存在 3 這種節(jié)點，3- 節(jié)點中可以存放兩個元素，并且可以有三個子節(jié)點。

2-3 樹定義

2-3 樹的定義如下：
（1）2-3 樹要么為空要么具有以下性質(zhì)：
（2）對于 2- 節(jié)點，和普通的 BST 節(jié)點一樣，有一個數(shù)據(jù)域和兩個子節(jié)點指針，兩個子節(jié)點要么為空，要么也是一個2-3樹，當前節(jié)點的數(shù)據(jù)的值要大于左子樹中所有節(jié)點的數(shù)據(jù)，要小于右子樹中所有節(jié)點的數(shù)據(jù)。
（3）對于 3- 節(jié)點，有兩個數(shù)據(jù)域 a 和 b 和三個子節(jié)點指針，左子樹中所有的節(jié)點數(shù)據(jù)要小于a，中子樹中所有節(jié)點數(shù)據(jù)要大于 a 而小于 b ，右子樹中所有節(jié)點數(shù)據(jù)要大于 b 。
例如圖 2.1 所示的樹為一棵 2-3 樹：

2-3 樹性質(zhì)

性質(zhì)：
（1）對于每一個結(jié)點有 1 或者 2 個關(guān)鍵碼。
（2）當節(jié)點有一個關(guān)鍵碼的時，節(jié)點有 2 個子樹。
（3）當節(jié)點有 2 個關(guān)鍵碼時，節(jié)點有 3 個子樹。
（4）所有葉子點都在樹的同一層。

2-3樹查找

2-3 樹的查找類似二叉搜索樹的查找過程，根據(jù)鍵值的比較來決定查找的方向。

例如在圖 2.1 所示的 2-3 樹中查找鍵為H的節(jié)點：

例如在圖 2.1 所示的 2-3 樹中查找鍵為 B 的節(jié)點：

2-3樹插入

插入

在樹的插入之前需要對帶插入的節(jié)點進行一次查找操作，若樹中已經(jīng)有此節(jié)點則不予插入，若沒有查找到此節(jié)點則記錄未命中查找結(jié)束時訪問的最后一個節(jié)點。
空樹的插入最簡單，創(chuàng)建一個節(jié)點即可，這里不予贅述。
對于非空樹插入主要分為 4 種情況：
（1）向 2- 節(jié)點中插入新節(jié)點
（2）向一棵只含 3- 節(jié)點的樹中插入新節(jié)點
（3）向一個父節(jié)點為 2- 節(jié)點的 3- 節(jié)點中插入新節(jié)點
（4）向一個父節(jié)點為 3- 節(jié)點的 3- 節(jié)點中插入新節(jié)點

向2-節(jié)點中插入新節(jié)點

操作步驟：如果未命中查找結(jié)束于一個 2-節(jié)點，直接將 2- 節(jié)點替換為一個 3- 節(jié)點，并將要插入的鍵保存在其中。

圖解：

向一棵只含 3- 節(jié)點的樹中插入新節(jié)點

操作步驟：先臨時將新鍵存入唯一的 3- 節(jié)點中，使其成為一個 4- 節(jié)點，再將它轉(zhuǎn)化為一顆由 3 個 2- 節(jié)點組成的 2-3 樹，分解后樹高會增加 1。

圖解：

向一個父節(jié)點為 2- 節(jié)點的 3- 節(jié)點中插入新節(jié)點

操作步驟：先構(gòu)造一個臨時的 4- 節(jié)點并將其分解，分解時將中鍵移動到父節(jié)點中(中鍵移動后，其父節(jié)點中的位置由鍵的大小確定)

圖解：

向一個父節(jié)點為3-節(jié)點的3-節(jié)點中插入新節(jié)點

操作步驟：插入節(jié)點后一直向上分解構(gòu)造的臨時4-節(jié)點并將中鍵移動到更高層雙親節(jié)點，直到遇到一個-2節(jié)點并將其替換為一個不需要繼續(xù)分解的3-節(jié)點，或是到達樹根(3-節(jié)點)。

圖解：

分解根節(jié)點

操作步驟：如果從插入節(jié)點到根節(jié)點的路徑上全是3-節(jié)點（包含根節(jié)點在內(nèi)），根節(jié)點將最終被替換為一個臨時的4-節(jié)點，將臨時的4-節(jié)點分解為3個2-節(jié)點，分解后樹高會增加1。

圖解：

2-3樹刪除

刪除之前，先要對2-3樹進行一次命中的查找，查找成功才可以進行刪除操作。
刪除節(jié)點大概分為3種情形

（1）刪除非葉子節(jié)點。
（2）刪除不為2-節(jié)點的葉子節(jié)點。
（3）刪除為2-節(jié)點的葉子節(jié)點。

刪除非葉子節(jié)點

操作步驟：使用中序遍歷下的直接后繼節(jié)點key來覆蓋當前待刪除節(jié)點key，再刪除用來覆蓋的后繼節(jié)點key。

圖解：

刪除不為2-節(jié)點的葉子節(jié)點

操作步驟：刪除不為2-節(jié)點的葉子節(jié)點，直接刪除節(jié)點即可。**

圖解：

刪除為2-節(jié)點的葉子節(jié)點

刪除為2-節(jié)點的葉子節(jié)點的步驟相對復(fù)雜，刪除節(jié)點后需要做出相應(yīng)判斷，并根據(jù)判斷結(jié)果調(diào)整樹結(jié)構(gòu)。主要分為四種情形：

刪除節(jié)點為2-節(jié)點，父節(jié)點為2-節(jié)點，兄弟節(jié)點為3-節(jié)點

操作步驟：當前待刪除節(jié)點的父節(jié)點是2-節(jié)點、兄弟節(jié)點是3-節(jié)點，將父節(jié)點移動到當前待刪除節(jié)點位置，再將兄弟節(jié)點中最接近當前位置的key移動到父節(jié)點中。

圖解：

刪除節(jié)點為2-節(jié)點，父節(jié)點為2-節(jié)點，兄弟節(jié)點為2-節(jié)點

操作步驟：當前待刪除節(jié)點的父節(jié)點是2-節(jié)點、兄弟節(jié)點也是2-節(jié)點，先通過移動兄弟節(jié)點的中序遍歷直接后驅(qū)到兄弟節(jié)點，以使兄弟節(jié)點變?yōu)?-節(jié)點；再進行6.3.1的操作。

圖解：

刪除節(jié)點為2-節(jié)點，父節(jié)點為3-節(jié)點

操作步驟：當前待刪除節(jié)點的父節(jié)點是3-節(jié)點，拆分父節(jié)點使其成為2-節(jié)點，再將再將父節(jié)點中最接近的一個拆分key與中孩子合并，將合并后的節(jié)點作為當前節(jié)點。

圖解：

2-3樹為滿二叉樹，刪除葉子節(jié)點

操作步驟：若2-3樹是一顆滿二叉樹，將2-3樹層樹減少，并將當前刪除節(jié)點的兄弟節(jié)點合并到父節(jié)點中，同時將父節(jié)點的所有兄弟節(jié)點合并到父節(jié)點的父節(jié)點中，如果生成了4-節(jié)點，再分解4-節(jié)點。

圖解：

結(jié)語

2-3 樹作為一種平衡查找樹，查詢效率比普通的二叉排序樹要穩(wěn)定許多。但是2-3樹需要維護兩種不同類型的結(jié)點，查找和插入操作的實現(xiàn)需要大量的代碼，而且它們所產(chǎn)生的額外開銷可能會使算法比標準的二叉查找樹更慢。