2-3樹

2-3樹
類型	樹
發明時間	1970
發明者	約翰·霍普克洛夫特
用大O符號表示的時間複雜度
算法 平均 最差 空間 $O(n)$ $O(n)$ 搜尋 $O(\log n)$ $O(\log n)$ 插入 $O(\log n)$ $O(\log n)$ 刪除 $O(\log n)$ $O(\log n)$

計算機科學中，2–3樹（英語：2–3 tree）是一種樹型數據結構，由約翰·霍普克洛夫特於1970年發明。

2–3樹中的內部節點可以有2個子節點和1個數據元素、或有3個子節點和2個數據元素，葉子節點有1至2個數據元素。

• 
  2節點
• 
  3節點

2–3樹和AA樹是等距同構的，意味着它們是同一種數據結構。換句話說，對於每個2–3樹，都至少存在1種AA樹和它的元素排列是相同的。2–3樹是平衡樹，意味着右邊，左邊，中間的子樹的元素數量都是相同或接近的。

定義

如果一個內部節點擁有一個數據元素、兩個子節點，則此節點為2節點。

如果一個內部節點擁有兩個數據元素、三個子節點，則此節點為3節點。

當且僅當以下敘述中有一條成立時，T為2–3樹：

• T為空。即T不包含任何節點。
• T為擁有數據元素a的2節點。若T的左子節點為L、右子節點為R，則：
  • L和R是等高的2–3樹；
  • a大於L中的所有數據元素；同時
  • a小於等於R中的所有數據元素。
• T為擁有數據元素a和b的3節點，其中a < b。若T的左子節點為L、中子節點為M、右子節點為R，則：
  • L、M、和R是等高的2–3樹；
  • a大於L中的所有數據元素，並且小於等於M中的所有數據元素；同時
  • b大於M中的所有數據元素，並且小於等於R中的所有數據元素。

操作

2–3樹的查找元素操作與二叉搜索樹的查找類似。因為節點中的數據元素都是有序的，所以查找函數可以據此進入正確的子樹進行查找，最終找到正確的節點。

進行插入操作時，可以先通過查找操作確定合適的位置，然後將數據插入對應節點。如果插入後的節點變成4節點（包含三個數據元素），則需將該節點拆分為兩個2節點，中間的數據元素進入父節點。這樣一來，該父節點也可能也會因此變成4節點，則該父節點也會拆分為兩個2節點，中間的數據元素進入該父節點的父節點，以此類推，直到修改後的父節點不需要分裂，或者被拆分的是根節點，此時中間數據元素就會單獨形成2節點，成為新的根節點。

2-3樹插入操作的三種情況

外部連結

• 2–3 Trees Complete Description
• 2–3 Tree Java Applet
• 2–3 Tree In-depth description（頁面存檔備份，存於網際網路檔案館）
• 2–3 Tree in F#（頁面存檔備份，存於網際網路檔案館）
• 2–3 Tree in Python（頁面存檔備份，存於網際網路檔案館）