2-3 樹

本頁面介紹 2-3 樹。2-3 樹是一種多路搜索樹，是絕對平衡的樹，其所有葉節點都處於同一層級上。2-3 樹是 3 階 B 樹。

定義

2-3 樹中的每一個節點都有兩個孩子（稱為 2 節點，2-node）或三個孩子（稱為 3 節點，3-node)。

2 節點，有一個數據元素和兩個孩子。只能有兩個孩子或沒有孩子，不能出現只有一個孩子的情況。如果 2 節點有孩子，左子樹包含的元素小於 \(a\)，右子樹包含的元素大於 \(a\)。
3 節點，有兩個數據元素和三個孩子。只能有三個孩子或沒有孩子，不能出現有一個孩子或有兩個孩子的情況。如果 3 節點有孩子，左子樹包含小於較小元素的元素，右子樹包含大於較大元素的元素，中間子樹包含介於兩元素之間的元素。
4 節點，有三個數據元素。只會在操作樹時暫時創建，而不會永久存儲在樹上。

2-3 樹的葉節點不含有子節點，有一個或兩個數據元素。

樹 \(T\) 是一個 2-3 樹，當且僅當以下表述之一成立：

\(T\) 是空樹。
\(T\) 是一個 2 節點，並帶有元素 \(a\)。如果 \(T\) 有左孩子 \(p\) 和右孩子 \(q\)，則：
- \(p\) 和 \(q\) 是相同高度的 2-3 樹。
- \(a\) 大於 \(p\) 中的每個元素。
- \(a\) 小於 \(q\) 中的每個數據元素。
\(T\) 是一個 3 節點，並帶有數據元素 \(a\) 和 \(b\)，其中 \(a\) 小於 \(b\)。如果 \(T\) 有左孩子 \(p\)，中間孩子 \(q\) 和右孩子 \(r\)，則：
- \(p\)、\(q\) 和 \(r\) 是相等高度的 2-3 樹。
- \(a\) 大於 \(p\) 中的每個數據元素且小於 \(q\) 中的每個數據元素。
- \(b\) 大於 \(q\) 中的每個數據元素且小於 \(r\) 中的每個數據元素。

由於 2-3 樹上的元素是按一定順序存儲的，所以 2-3 樹的查找與二叉搜索樹類似。下面在樹 \(T\) 中查找元素 \(d\)。

如果 2–3 樹 \(T\) 為空，那麼 \(d\) 肯定不在 \(T\) 中，查找結束。
假設 \(t\) 是 \(T\) 的根節點。
如果 \(t\) 是一個葉子節點：
- 如果 \(d\) 不在節點 \(t\) 中，那麼 \(d\) 肯定不在整個樹 \(T\) 中，查找結束。
- 如果 \(d\) 在節點 \(t\) 中，那麼 \(d\) 在樹 \(T\) 中，查找成功結束。
假設 \(t\) 是一個 "2 節點"，具有左子節點 \(p\) 和右子節點 \(q\)，\(a\) 是節點 \(t\) 中的數據元素。有以下三種情況：
- 如果 \(d\) 等於 \(a\)，那麼找到 \(d\) 在樹 \(T\) 中，查找成功結束。
- 如果 \(d\) 小於 \(a\)，將 \(T\) 設為子樹 \(p\)，並回到步驟 2 繼續查找。
- 如果 \(d\) 大於 \(a\)，將 \(T\) 設為子樹 \(q\)，並回到步驟 2 繼續查找。
假設 \(t\) 是一個 "3 節點"，具有左子節點 \(p\)、中間子節點 \(q\) 和右子節點 \(r\)，\(a\) 和 \(b\) 是節點 \(t\) 中的兩個數據元素，滿足 \(a<b\)。有以下四種情況：
- 如果 \(d\) 等於 \(a\) 或 \(b\)，那麼找到 \(d\) 在樹 \(T\) 中，查找成功結束。
- 如果 \(d\) 小於 \(a\)，將 \(T\) 設為子樹 \(p\)，回到步驟 2 繼續查找。
- 如果 \(d\) 在 \(a\) 和 \(b\) 之間，將 \(T\) 設為子樹 \(q\)，回到步驟 2 繼續查找。
- 如果 \(d\) 大於 \(b\)，將 \(T\) 設為子樹 \(r\)，回到步驟 2 繼續查找。

插入節點需要維持樹的平衡。

對於空樹，直接插入一個 2 節點即可。此外，為了保持完美平衡性，向 2-3 樹添加元素不會直接添加到空節點，而是先進行搜索，將待插入元素添加到最後搜索到的葉子節點，與它融合。

如果插入 2 節點，則融合形成 3 節點。如下圖插入元素 4。
如果插入 3 節點，則先融合形成 4 節點，再拆解形成 2 個 2 節點。
- 如果父節點為 2 節點，則中間元素上移與父節點融合形成 3 節點。如下圖插入元素 10。
- 如果父節點為 3 節點，則重複步驟 2。如下圖插入元素 1。

通過上述深度增加的例子，可以看出 2-3 樹和標準二叉樹不同，標準的二叉樹的的深度是由上到下的增加的，而 2-3 樹的深度是由下至上的增加的。

刪除節點需要維持樹的平衡。2-3 樹的刪除可以分為三種情況。

2-3-tree-delete

待刪除的元素位於非葉子的分支節點。通常先按中序遍歷後得到此元素的前驅或後繼元素，讓他們來補位，再刪除用於補位的前驅或後繼元素。如果我們要刪除的分支節點是 2 節點，如上下圖所示，待刪除的元素是 4，前驅是 1，後繼是 6，顯然 \((6，7)\) 是 3 節點，只需要用 6 來補位即可。這裏就不講解刪除的分支節點是 3 節點的情況了，與上述類似。

2-3-tree-delete

3. 所刪除的元素位於一個 2 節點上。如果刪除一個 2 節點，很有可能造成 2-3 樹平衡破壞的情況，因為對於每一個 2 節點，要麼有兩個子樹要麼沒有，對於每一個 3 節點要麼有三個子樹要麼沒有，貿然刪除一個 2 節點，很可能出現平衡遭到破壞，所以我們需要分情況討論。

此節點的父親節點是 2 節點，兄弟節點是 3 節點。將父親節點移動到當前位置，再將兄弟節點中最接近當前位置的元素移動到父親節點中。如下圖所示，待刪除元素為 1。
此節點的父親節點是 2 節點，兄弟節點也是 2 節點。先通過移動兄弟節點中序遍歷的直接後驅到兄弟節點，使兄弟節點變為 3 節點，再進行上述 3.1 的操作。如下圖所示，待刪除元素為 4，如果直接執行上述 3.1 的操作會造成沒有右孩子，因此需要對整棵樹變形。通過移動兄弟節點 7 中序遍歷的直接後驅 8 到兄弟節點，讓節點 7 變成 3 節點，再讓比 8 大的 9 補充到 8 的位置，最後再執行上述 3.1 的操作。
此節點的父親節點是 3 節點。拆分父親節點使其成為 2 節點，再將父親節點中最接近刪除元素的元素與中孩子合併，將合併後的節點作為當前節點。如下圖所示，待刪除元素為 10。
當前 2-3 樹是一個滿二叉樹。將 2-3 樹的層數減少，並將兄弟節點合併到父親節點中，同時將父親節點的所有兄弟節點合併到父親節點的父親節點中，如果生成了 4 節點，再分解 4 節點即可。