1. 2-3-4樹及2-3樹的定義以及操作
參見紅黑樹專題
2. 2-3-4樹以及2-3樹的第一個(gè)實(shí)現(xiàn)——紅黑樹
參見紅黑樹專題
參見查找樹（搜索樹）中的紅黑樹
3. 2-3-4樹的第二實(shí)現(xiàn)——1-2-3確定性跳躍表
4. 2-3樹的實(shí)現(xiàn)——AA樹（基于2-3樹的右傾紅黑樹變種）
4.1 AA樹的定義與實(shí)現(xiàn)
一棵紅黑樹是滿足下面紅黑性質(zhì)的二叉搜索樹：
- 1.每個(gè)結(jié)點(diǎn)或是紅色的，或是黑色的
- 2.根節(jié)點(diǎn)是黑色的
- 3.每個(gè)葉節(jié)點(diǎn)NIL時(shí)黑色的（這條性質(zhì)可去掉）
- 4.如果一個(gè)結(jié)點(diǎn)是紅色的，則它的兩個(gè)子節(jié)點(diǎn)都是黑色的
- 5.對(duì)每個(gè)結(jié)點(diǎn)，從該節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡(jiǎn)單路徑上，均包含相同數(shù)目的黑色結(jié)點(diǎn)
AA樹的附加條件：
- 一個(gè)結(jié)點(diǎn)最多可以有一個(gè)紅兒子，并且只有右兒子可以是紅兒子（消除了約一半的可能情形）。
如果一個(gè)內(nèi)部結(jié)點(diǎn)只有一個(gè)兒子，那么這個(gè)兒子一定是右兒子（紅色）。那么在刪除時(shí)，總是可以用一個(gè)內(nèi)部結(jié)點(diǎn)的右子樹中的最小結(jié)點(diǎn)代替該內(nèi)部結(jié)點(diǎn)。（一個(gè)兒子結(jié)點(diǎn)是右兒子，兩個(gè)兒子結(jié)點(diǎn)用右兒子代替，因此總是用右兒子代替。） - 結(jié)點(diǎn)的層次（本質(zhì)上是2-3樹每個(gè)結(jié)點(diǎn)的高度）：
1）若該結(jié)點(diǎn)是樹葉，則為1
2）若該結(jié)點(diǎn)是紅的，則為其父結(jié)點(diǎn)的層次
3）若該結(jié)點(diǎn)是黑的，則比父結(jié)點(diǎn)少1
本質(zhì)上是一棵2-3樹
4.2 AA樹的操作
4.2.1 插入
實(shí)質(zhì)上是自底向上的2-3樹插入
1）skew和split操作
插入的問題：
- 產(chǎn)生一個(gè)左水平鏈接——通過右旋消除
-
產(chǎn)生兩個(gè)連續(xù)的右水平鏈接——通過左旋消除
2）插入操作（遞歸操作實(shí)現(xiàn)的是自底向上的插入）
4.2.2 刪除
刪除總可以歸結(jié)為葉子節(jié)點(diǎn)的刪除，如果該節(jié)點(diǎn)不是樹葉，則總是可以歸結(jié)為其右子樹上最小的兒子（葉子節(jié)點(diǎn)）來代替這個(gè)節(jié)點(diǎn)。
注意：
- 代碼中，DeletePtr和LastPtr是static變量，因此只有在最底層葉子的時(shí)候，LastPtr才等于T，其余時(shí)候都不等于。因此才有了step2和step3的區(qū)分。
- 最底層葉子刪除的時(shí)候，指向的是NullNode，該節(jié)點(diǎn)的高度為0.因此會(huì)有step3的條件：
T->Right->level < T->level - 1或者
T->Left->level < T->level - 1 - 當(dāng)刪除紅色結(jié)點(diǎn)，不要挑戰(zhàn)；
（重要——核心本質(zhì)）當(dāng)刪除黑色結(jié)點(diǎn)時(shí)，會(huì)主動(dòng)使2-3樹父節(jié)點(diǎn)的高度減一，即將2-3樹的2-結(jié)點(diǎn)或者3-結(jié)點(diǎn)與該結(jié)點(diǎn)還剩下的兒子結(jié)點(diǎn)合并，然后通過分裂達(dá)到平衡。 - skew是將左鏈接改為右鏈接，使其符合AA樹的定義，但是對(duì)于2-3樹來說，是在一個(gè)結(jié)點(diǎn)內(nèi)的改變
- split是將4-結(jié)點(diǎn)分裂成3個(gè)2-結(jié)點(diǎn)，使得2-3樹增加
