【2-3樹】2-3樹的奧秘：3分鐘掌握資料結構世界的秘密

2-3 樹：一種提高搜索效率的平衡樹

2-3 樹是一種平衡搜索樹，其內部節點最多擁有 2 個數據元素和 3 個子節點。葉節點擁有 1 至 2 個數據元素。2-3 樹的關鍵特性在於其每個內部節點要麼擁有 1 個數據元素和 2 個子節點（稱為 2 節點），要麼擁有 2 個數據元素和 3 個子節點（稱為 3 節點）。

插入操作

2-3 樹的插入操作與二叉搜索樹類似，首先通過搜索找到插入位置。但是，與二叉搜索樹不同的是，2-3 樹的插入總是發生在葉節點上。如果待插入節點是一個 2 節點，直接將值插入即可。如果待插入節點是一個 3 節點，則將其分裂為兩個節點，保留最小值，將最大值插入到新分裂出的節點中，並將中間值上移到父節點。

刪除操作

2-3 樹的刪除操作也與其性質密切相關。刪除操作主要有五種情況：

從父節點中刪除：找到前驅值並與待刪除值交換，然後刪除前驅值。
從葉節點中刪除：直接刪除值，將 3 節點轉換為 2 節點。
從只有 1 個非葉節點的葉節點中刪除：合併父節點和葉節點，並調整父節點的值。
從只有 1 個非葉節點且只有一個子女的葉節點中刪除：將非葉節點的唯一子節點提升到父節點，並調整父節點的值。
從只有 1 個非葉節點且有兩或多個子女的葉節點中刪除：重新分配子女，並保留非葉節點的最大值。

與其他平衡樹的比較

與紅黑樹和 AVL 樹等其他平衡樹相比，2-3 樹擁有不同的特性。2-3 樹的內部節點最多可以擁有 2 個子節點，而其他平衡樹的內部節點最多只能擁有 2 個數據元素。此外，2-3 樹的插入和刪除操作需要考慮節點的分裂和合併，而其他平衡樹只需要調整指針和平衡因子。

應用場景

2-3 樹廣泛應用於數據庫管理系統、分佈式系統和文件系統等場景，其平衡的特性和較高的搜索效率使其在海量數據處理中具有優勢。

特性	二叉搜索樹	AVL 樹	紅黑樹	2-3 樹
內部節點數據元素數	1	1	1	1 或 2
內部節點子節點數	2	2	2	2 或 3
搜索時間複雜度	O(logn)	O(logn)	O(logn)	O(logn)
插入時間複雜度	O(logn)	O(logn)	O(logn)	O(logn)
刪除時間複雜度	O(logn)	O(logn)	O(logn)	O(logn)
節點類型	二叉節點	二叉節點	二叉節點	二叉節點和三叉節點
平衡條件	無	保持平衡因子	保持紅黑性質	最小高度
優勢	簡單易理解	快速且穩定	查找效率高	查找效率高，處理大量數據較優
劣勢	高度不平衡可能導致搜索時間較長	平衡操作較複雜	平衡操作較複雜	插入和刪除需要考慮節點的分裂和合併

2-3 樹

在計算機科學中，2-3 樹是一種自平衡搜尋樹，它在每個節點可以儲存 2 到 4 個元素。與二元搜尋樹不同，2-3 樹允許每個節點有 2 到 3 個子節點，這可以減少樹的高度和查詢時間。

2-3 樹的結構

一個 2-3 樹由以下元素組成：

元素	説明
根節點	樹的頂部節點
葉節點	沒有子節點的節點
中間節點	有一個或兩個子節點的節點
鑰匙	節點中儲存的元素
指標	指向子節點的指標

2-3 樹的屬性

2-3 樹具有以下屬性：

屬性	説明
每個節點有 2 到 3 個元素	即每個節點的度數為 2 或 3
每個葉節點在同一層	這確保了所有查詢與插入都會在相同時間完成
自平衡	2-3 樹會自動進行平衡操作，以確保樹的高度保持最小

插入和刪除操作

在 2-3 樹中，插入和刪除操作是通過分裂和合併節點來進行的：

操作	説明
插入	當一個節點滿時，它會分裂成兩個節點，並將中間元素向上移動
刪除	當一個節點只剩下一個元素時，它會與兄弟節點合併，或從樹中刪除

2-3 樹的優點

2-3 樹的優點包括：

優點	説明
快速查詢	由於樹的高度保持最小，查詢操作非常快速
自平衡	樹會自動平衡，無需額外維護
易於實現	與其他平衡樹相比，2-3 樹的實現相對簡單

2-3 樹的應用

2-3 樹被用於各種應用中，包括：

延伸閲讀…

2-3樹- 算法與複雜度| 小白

2-3樹- 維基百科，自由的百科全書

應用	説明
資料庫索引	在資料庫中作為快速查詢索引用
快取	在快取中儲存資料，以提高效能
記憶體管理	在記憶體管理系統中管理記憶體分配