定義
一棵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é)點的距離都應該是相同的.
插入
由于2-3樹也是屬于二叉查找樹中的一種,往樹里面插入一個新節(jié)點時,肯定是插入到某個葉子節(jié)點上.需要分情況討論因為有兩種節(jié)點類型.
葉子節(jié)點是2-節(jié)點: 直接把新節(jié)點加入到2-節(jié)點生成一個新的3-節(jié)點.
2-3_2.jpeg
葉子節(jié)點是3-節(jié)點:當把新節(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
總結
參考算法4.
