1. 2-3-4樹及2-3樹的定義以及操作
參見紅黑樹專題
2. 2-3-4樹以及2-3樹的第一個實現(xiàn)——紅黑樹
參見紅黑樹專題
參見查找樹（搜索樹）中的紅黑樹
3. 2-3-4樹的第二實現(xiàn)——1-2-3確定性跳躍表
4. 2-3樹的實現(xiàn)——AA樹（基于2-3樹的右傾紅黑樹變種）
4.1 AA樹的定義與實現(xiàn)
一棵紅黑樹是滿足下面紅黑性質(zhì)的二叉搜索樹：
- 1.每個結(jié)點(diǎn)或是紅色的，或是黑色的
- 2.根節(jié)點(diǎn)是黑色的
- 3.每個葉節(jié)點(diǎn)NIL時黑色的（這條性質(zhì)可去掉）
- 4.如果一個結(jié)點(diǎn)是紅色的在张，則它的兩個子節(jié)點(diǎn)都是黑色的
- 5.對每個結(jié)點(diǎn)，從該節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡單路徑上范舀，均包含相同數(shù)目的黑色結(jié)點(diǎn)
AA樹的附加條件：
- 一個結(jié)點(diǎn)最多可以有一個紅兒子供璧，并且只有右兒子可以是紅兒子（消除了約一半的可能情形）。
如果一個內(nèi)部結(jié)點(diǎn)只有一個兒子，那么這個兒子一定是右兒子（紅色）弯屈。那么在刪除時，總是可以用一個內(nèi)部結(jié)點(diǎn)的右子樹中的最小結(jié)點(diǎn)代替該內(nèi)部結(jié)點(diǎn)恋拷。（一個兒子結(jié)點(diǎn)是右兒子资厉，兩個兒子結(jié)點(diǎn)用右兒子代替，因此總是用右兒子代替蔬顾。） - 結(jié)點(diǎn)的層次（本質(zhì)上是2-3樹每個結(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 插入
實質(zhì)上是自底向上的2-3樹插入
1）skew和split操作
插入的問題：
- 產(chǎn)生一個左水平鏈接——通過右旋消除
-
產(chǎn)生兩個連續(xù)的右水平鏈接——通過左旋消除
2）插入操作（遞歸操作實現(xiàn)的是自底向上的插入）
4.2.2 刪除
刪除總可以歸結(jié)為葉子節(jié)點(diǎn)的刪除窄刘，如果該節(jié)點(diǎn)不是樹葉，則總是可以歸結(jié)為其右子樹上最小的兒子（葉子節(jié)點(diǎn)）來代替這個節(jié)點(diǎn)舷胜。
注意：
- 代碼中娩践，DeletePtr和LastPtr是static變量，因此只有在最底層葉子的時候烹骨，LastPtr才等于T翻伺，其余時候都不等于。因此才有了step2和step3的區(qū)分展氓。
- 最底層葉子刪除的時候穆趴，指向的是NullNode，該節(jié)點(diǎn)的高度為0.因此會有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)時，會主動使2-3樹父節(jié)點(diǎn)的高度減一空入，即將2-3樹的2-結(jié)點(diǎn)或者3-結(jié)點(diǎn)與該結(jié)點(diǎn)還剩下的兒子結(jié)點(diǎn)合并络它，然后通過分裂達(dá)到平衡。 - skew是將左鏈接改為右鏈接歪赢，使其符合AA樹的定義化戳，但是對于2-3樹來說，是在一個結(jié)點(diǎn)內(nèi)的改變
- split是將4-結(jié)點(diǎn)分裂成3個2-結(jié)點(diǎn)，使得2-3樹增加
