定義

一棵2-3查找樹或為一棵空樹,或由以下節(jié)點組成:

2-節(jié)點:含有一個鍵和兩條鏈接,左鏈接指向的2-3樹中的鍵都小于該節(jié)點,右鏈接指向的2-3樹中的鍵都大于該節(jié)點.
3-節(jié)點:含有兩個鍵和三條鏈接,左鏈接指向的2-3樹中的鍵都小于該節(jié)點,中鏈接指向的2-3樹中的鍵都位于該節(jié)點的兩個鍵之間,右鏈接指向的2-3樹中的鍵都大于該節(jié)點.

2-3_1.jpeg

一棵完美平衡的2-3查找樹中的所有空鏈接到根節(jié)點的距離都應(yīng)該是相同的.

插入

由于2-3樹也是屬于二叉查找樹中的一種,往樹里面插入一個新節(jié)點時,肯定是插入到某個葉子節(jié)點上.需要分情況討論因為有兩種節(jié)點類型.

葉子節(jié)點是2-節(jié)點: 直接把新節(jié)點加入到2-節(jié)點生成一個新的3-節(jié)點.

2-3_2.jpeg

葉子節(jié)點是3-節(jié)點:當(dāng)把新節(jié)點加入到3-節(jié)點會變成臨時的4-節(jié)點,然后再進行分解成3個2-節(jié)點.

2-3_3.jpeg

把中間的2-節(jié)點傳遞給父親節(jié)點,至于父親節(jié)點是2-節(jié)點或者3-節(jié)點就可以進行遞歸處理.直接上圖會比較好理解.

2-3_4.jpeg

再看一張圖

2-3_5.jpeg

總結(jié)

參考算法4.