理论基础 —— 索引 —— 2-3 树
【概述】
2-3 樹是一種多路查找樹，其滿足于以下性質：
- 每個結點都具有兩個孩子或三個孩子，具有兩個孩子的結點稱為 2 結點，具有三個孩子的結點稱為 3 結點
- 2 結點包含一個元素和兩個孩子，左子樹包含元素小于根結點元素，右子樹包含元素大于根結點元素
- 3 結點包含一大一小兩個元素和三個孩子，左子樹包含較小元素，右子樹包含較大元素，中間子樹包含介于兩者之間的元素
- 所有的葉結點都在同一層
如上圖，12、48、10、15、24、31 都是 2 結點，{18,33}、{23,30}、{20,21}、{45,47}、{50,52} 都是 3 結點。
當所有的葉結點都處于同一層時，那么這棵樹就是樹高平衡的，可見 2-3 樹是樹高平衡的，其能夠以相對較低的代價保持樹高平衡。
此外，容易從 2-3 樹的定義推出樹的葉結點個數與樹的深度間的關系：
- 一個高度為 k 的 2-3 樹至少有 2^(k-1) 個葉結點，此時每個分支結點都有 2 個孩子，形成一棵滿二叉樹的形狀
- 一個高度為 k 的 2-3 樹最多有 3^(k-1) 個葉結點，此時每個分支結點都有 3 個孩子，形成一棵滿三叉樹的形狀
【查找】
在 2-3 樹中，查找一個關鍵碼的過程類似于在二叉排序樹中的查找。
在 2-3 樹中查找給定值 k 的過程是：
上述過程一直持續到 k 被找到或者待查找的子樹為空，若待查找的子樹為空，則查找失敗。值得注意的是，當查找失敗時，恰好找到了以 k 為鍵值的新結點在二叉排序樹中的插入位置。
以下圖為例，要如果查找 24，首先查找根結點，由于 24 大于 smallData=18，小于 bigData 33，那么進入中間子樹，在下一層中，同樣進入中間分支，到達包含 24 的葉結點。
【插入】
在 2-3 樹中，插入一個關鍵碼的過程類似于在二叉排序樹中的插入，新紀錄同樣是插入到葉結點中。
插入過程如下：
1.對于空樹，直接插入一個 2 節點
2.找到被插入記錄應該插入的葉結點
3.如果應插入位置的葉結點是 2 結點，直接將新紀錄插入，將 2 結點升級為 3 結點
4.如果應插入位置的葉結點是 3 結點，則需將其分裂，拆分為兩個 2 結點
1）設要插入的葉結點為 L，創建一個新結點 L'
2）L 得到三個關鍵碼中最小的一個，L' 得到三個關鍵碼中最小的一個
3）進行一次提升：將中間的關鍵碼與一個指向 L' 的指針傳回父結點，并將被提升的關鍵碼插入父結點
4）如果父結點為 2 結點，那么重復步驟 3
5）如果父結點為 3 結點，那么重復步驟 4 的分裂-提升過程
例如：在下圖中插入 14、55
?
1）插入 14 時：從根結點開始查找，到達存儲 15 的葉結點，其是一個 2 結點，直接將 14 插入即可
2）插入 55 時：從根結點開始查找，到達存儲 {50,52} 的結點，其是一個 3 結點，需要進行分裂，加入 55 后，三個關鍵碼的值為 50、52、55，其中，令中值 52 提升，小值 50 與大值 55 作為父結點的葉結點
【刪除】
在 2-3 樹中，刪除一個結點與插入一個結點相反。
其過程為：
1.所刪除的元素位于非葉子的分支結點時，將樹按中序遍歷后得到的前驅或后繼元素，用其補位即可。
2.所刪除的元素位于?3 結點時，在該結點刪除該元素即可，不會影響整棵樹的結構。
3.所刪除的元素位于 2 結點時，此時分為四種情況：
1）2 結點的父結點是 3 結點：此時將 3 結點進行拆分，根據刪除要刪除的元素的大小，將被拆分的點與 3 結點的子樹進行合并
?
2）2 結點的父結點是 2 結點，且擁有一個 3 結點的右孩子：將父結點與右孩子一起進行左旋，令父結點的右孩子的較小值成為新的父結點，原先的父結點成為新的左孩子，原先的右孩子的較大值不做改變
3）2 結點的父結點是 2 結點，且擁有一個 2 結點的右孩子：先在不破壞 2-3 樹的性質的前提下，將 2 結點的右孩子變為 3 結點的右孩子，然后刪除要刪除的元素，并將剩下的三個點進行左旋調整。
4）當前樹是一個滿二叉樹：此時刪除任意一個結點都會破壞 2-3 樹的性質，需要考慮在不改變 2-3 樹的順序的情況下，將 2-3 樹的層次減少一層。
總結
以上是生活随笔為你收集整理的理论基础 —— 索引 —— 2-3 树的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 线性结构 —— 分块算法
- 下一篇： 理论基础 —— 查找 —— 二叉排序树