作者：disappearedgod
文章出處：
時間：2014-4-18
源自部落格文章，由于2-3樹實在有太多面試意義，是以單獨抽出來成文。
由于叙述衆多，不在本部落格中做詳細解釋，正文部分中有相關連結，請點選查閱。
定義 一棵2-3查找樹或為一棵空樹，或由以下結點組成：
2-結點，含有一個鍵(及其對應的值)和兩條連結，左連結指向的2-3樹中的鍵都小于該結點，右連結指向的2-3樹中的鍵都大于該結點。
3-結點，含有兩個鍵(及其對應的值)和三條連結，左連結指向的2-3樹中的鍵都小于該結點，左連結指向的2-3樹中的鍵都小于該結點，中連結指向的2-3樹中的鍵都位于該結點的兩個鍵之間，右連結指向的2-3樹中的鍵都待遇該結點。
将指向一棵空樹的連結成為空連結。
和标準二叉樹有上向下生長不同，2-3樹是由下向上生長的（堆排序恰巧也是符合這個思想的二叉樹）。一個簡單的構造例子如下：
2-3樹的查找效率與樹的高度是息息相關的。
在最壞的情況下，也就是所有的節點都是2-node節點，查找效率為lgn
在最好的情況下，所有的節點都是3-node節點，查找效率為log3n約等于0.631lgn
1百萬個節點的2-3樹，樹的高度為12-20之間,對于10億個節點的2-3樹，樹的高度為18-30之間。
因為它是balanced的！一棵高度為k的2-3 tree有2k – 1 到 3k – 1 之間的葉；一棵有elements 為n的2-3 tree 高度最小為 1+log3n， 最大為 1+log2n。它的檢索時間為o(logn)。
僞代碼如下：
假設已處平衡狀态，我們先看基本操作。
2-3樹的查找和二叉查找樹類似，要确定一個樹是否屬于2-3樹，我們首先和其跟節點進行比較，如果相等，則查找成功；否則根據比較的條件，在其左中右子樹中遞歸查找，如果找到的節點為空，則未找到，否則傳回。
二叉樹按照升序插入10個key會得到高度為9的一棵最差樹，2-3tree的高度為2.
含有10億個結點的一棵2-3樹的高度僅在19-30之間。（也就是說，通路最多30個結點可查）
插入：1. 未命中查找;2.新節點挂在底部；3.平衡。
對于2-3 tree，所有的插入（新值）都必須發生在leaf。是以，首先找到新值應該所在的leaf，然後根據這個leaf的情況做出判斷：
1． 該點隻有一個元素。直接加入就可以了，判斷是small還是large。
2． 該點full（small和large都有值），其父結點不是full。那就split該結點，并把中間值推上去。
3． 該點和其父結點都full。如果父結點full，表示父結點已經有3個子樹。那就需要一直split 并一直往上推，直到發生以下情況：
1) 父結點最多隻有3個子樹
2) 父結點是根，建立一個新root，儲存中間值。樹的高度增加1
往2-3樹中插入元素和往二叉查找樹中插入元素一樣，首先要進行查找，然後将節點挂到未找到的節點上。2-3樹之是以能夠保證在最差的情況下的效率的原因在于其插入之後仍然能夠保持平衡狀态。如果查找後未找到的節點是一個2-node節點，那麼很容易，我們隻需要将新的元素放到這個2-node節點裡面使其變成一個3-node節點即可。但是如果查找的節點結束于一個3-node節點，那麼可能有點麻煩。
往一個3-node節點插入一個新的節點可能會遇到很多種不同的情況，下面首先從一個最簡單的隻包含一個3-node節點的樹開始讨論。
建立插入，臨時将新鍵存入該節點中，使之成為4-結點。
3-key 4-link，為了容易轉化為一棵由3個2-node組成的2-3 tree
需要在維持樹的完美平衡的前提下為建立騰出空間。
分析：父節點既然是2-node，就要改成3-node，隻有将新的4-node中的中值賦給2-node，作為3-node中後面的一個點。
将上述的父節點（3.1.2.2中分解出的父節點）與其真正的父節點（2-node）合并。
當我們插入的節點是3-node的時候，我們将該節點拆分，中間元素提升至父節點，但是此時父節點是一個3-node節點，插入之後，父節點變成了4-node節點，然後繼續将中間元素提升至其父節點，直至遇到一個父節點是2-node節點，然後将其變為3-node，不需要繼續進行拆分。
當根節點到位元組點都是3-node節點的時候，這是如果我們要在位元組點插入新的元素的時候，會一直查分到跟節點，在最後一步的時候，跟節點變成了一個4-node節點，這個時候，就需要将跟節點查分為兩個2-node節點，樹的高度加1，這個操作過程如下：
2-3 tree插入算法的根本在于這些變換都是局部的：除了相關節點和連結之外不必修改或檢查樹的其他部分。換句話說，每次變換中，變更的連接配接數不會超過一個很小的常數。
全局有序性和全局平衡性：任意空連結到根節點的路徑長度都是相等的。
一個有趣的小例子：
reference：
gross, r. hernández, j. c. lázaro, r. dormido, s. ros (2001). estructura de datos y algoritmos. prentice hall. isbn 84-205-2980-x.
aho, alfred v.; hopcroft, john e.; ullman, jeffrey d. (1974). the design and analysis of computer algorithms.
addison-wesley.,
p.145-147