1 2-3樹(shù)

1.1 定義

• 2-結(jié)點(diǎn)：含有一個(gè)鍵和兩條孩子（或沒(méi)有），左鏈接指向的2-3樹(shù)中的鍵都小于該結(jié)點(diǎn)，右鏈接指向的2-3樹(shù)中的鍵都大于該結(jié)點(diǎn)。
• 3-結(jié)點(diǎn)：含有兩個(gè)鍵和三條鏈接（或沒(méi)有），左鏈接指向的2-3樹(shù)中的鍵都小于該結(jié)點(diǎn)，中鏈接指向的2-3樹(shù)中的鍵都位于該結(jié)點(diǎn)的兩個(gè)鍵之間，右鏈接指向的2-3樹(shù)中的鍵都大于該結(jié)點(diǎn)。

樹(shù)結(jié)點(diǎn)由2-結(jié)點(diǎn)或者3-結(jié)點(diǎn)組成且所有葉子結(jié)點(diǎn)處于同一高度的樹(shù)（允許是空樹(shù)）即為2-3樹(shù)。

1.2 性質(zhì)

1. 結(jié)點(diǎn)只能為2-結(jié)點(diǎn)或者3-結(jié)點(diǎn)
2. 對(duì)于2-結(jié)點(diǎn)其有一個(gè)數(shù)據(jù)，兩個(gè)指針結(jié)點(diǎn)
3. 對(duì)于3-結(jié)點(diǎn)其有兩個(gè)數(shù)據(jù)，三個(gè)指針結(jié)點(diǎn)
4. 所有葉子結(jié)點(diǎn)的高度保持一只高度

1.3 查找

查找過(guò)程與二叉搜索樹(shù)相類(lèi)似。

1.4 插入

遍歷查找結(jié)點(diǎn)：

• 查找到則不進(jìn)行插入
• 未查找到，則記錄查找結(jié)束的最后結(jié)點(diǎn)

插入操作可以分為四種類(lèi)型：

1. 向2-結(jié)點(diǎn)插入新結(jié)點(diǎn)
2. 向僅有一個(gè)3-結(jié)點(diǎn)的樹(shù)中插入新結(jié)點(diǎn)
3. 向一個(gè)父結(jié)點(diǎn)為2-結(jié)點(diǎn)的3-結(jié)點(diǎn)中插入新結(jié)點(diǎn)
4. 向一個(gè)父結(jié)點(diǎn)為3-結(jié)點(diǎn)的3-結(jié)點(diǎn)插入新結(jié)點(diǎn)

示例：將5,10,15,20,25,30,35,40,45,50依次放入2-3樹(shù)

樹(shù)-23樹(shù)插入.drawio.png

1.5 刪除

刪除操作也要先進(jìn)行元素的查找，找到才繼續(xù)進(jìn)行刪除操作。

1.5.1 刪除葉子結(jié)點(diǎn)

1.5.1.1 位于三結(jié)點(diǎn)葉子結(jié)點(diǎn)

刪除的元素位于三結(jié)點(diǎn)的葉子結(jié)點(diǎn)上，直接刪除改元素即可，不會(huì)影響整個(gè)樹(shù)的其他結(jié)點(diǎn)。

葉子結(jié)點(diǎn)1.png

1.5.1.2 位于二結(jié)點(diǎn)葉子結(jié)點(diǎn)

A. 父結(jié)點(diǎn)是二結(jié)點(diǎn)，右孩子是三結(jié)點(diǎn)

直接刪除元素后，會(huì)導(dǎo)致樹(shù)不滿足定義，此時(shí)進(jìn)行左旋。

葉子結(jié)點(diǎn)2.png

B.父結(jié)點(diǎn)是二結(jié)點(diǎn)，右孩子也是二結(jié)點(diǎn)

通過(guò)中序遍歷，使用前驅(qū)或后繼節(jié)點(diǎn)補(bǔ)位。

如示例先將結(jié)點(diǎn)【20】移到結(jié)點(diǎn)【15】中形成三結(jié)點(diǎn)，再將【25】移到原有【20】結(jié)點(diǎn)位置。此時(shí)【30 40】、【35】和【45 50】結(jié)點(diǎn)形成"C.父結(jié)點(diǎn)是三結(jié)點(diǎn)"類(lèi)型的刪除。

葉子結(jié)點(diǎn)3.png

C.父結(jié)點(diǎn)是三結(jié)點(diǎn)

刪除節(jié)點(diǎn)，意味父節(jié)點(diǎn)不能成為三結(jié)點(diǎn)，需要降為二結(jié)點(diǎn)。

如示例將【30】與【35】合并為三結(jié)點(diǎn)，作為【40】節(jié)點(diǎn)的左孩子。

葉子結(jié)點(diǎn)4.png

D.滿二叉樹(shù)

需要減少層數(shù)。

如示例結(jié)點(diǎn)【10】和【15】合并為三結(jié)點(diǎn)作為結(jié)點(diǎn)【20】左孩子，結(jié)點(diǎn)【30】與【20】合并為三結(jié)點(diǎn)作為根節(jié)點(diǎn)。

葉子結(jié)點(diǎn)5.png

1.5.2 刪除非葉子結(jié)點(diǎn)

通過(guò)中序遍歷得到節(jié)點(diǎn)的前驅(qū)或后繼節(jié)點(diǎn)，進(jìn)行補(bǔ)位。

2 2-3-4樹(shù)

2-3-4樹(shù)其實(shí)是2-3樹(shù)的擴(kuò)展，包含四結(jié)點(diǎn)的使用。

• 4-結(jié)點(diǎn)：含有三個(gè)鍵和四條鏈接（或沒(méi)有），左鏈接指向的2-3-4樹(shù)中的鍵都小于該結(jié)點(diǎn)，第二條鏈接指向的2-3-4樹(shù)中的鍵都位于該結(jié)點(diǎn)的第一和第二個(gè)鍵之間，第三條鏈接指向的2-3-4樹(shù)中的鍵都位于該結(jié)點(diǎn)的第二和第三個(gè)鍵之間，右鏈接指向的2-3-4樹(shù)中的鍵都大于該結(jié)點(diǎn)。

由于2-3-4樹(shù)整體與2-3樹(shù)類(lèi)似，故只以示例方式演示其構(gòu)造和刪除。

示例：將5,10,15,20,25,30,35,40,45,50依次放入2-3-4樹(shù)

樹(shù)-2-3-4樹(shù)插入.drawio.png

3 紅黑樹(shù)

2-3-4樹(shù)與紅黑樹(shù)保持平衡的規(guī)則是一致的，并且可以通過(guò)一些規(guī)則進(jìn)行轉(zhuǎn)換。它們是同構(gòu)關(guān)系。

2-3-4樹(shù)轉(zhuǎn)換紅黑樹(shù).png

紅黑樹(shù)的結(jié)構(gòu)與2-3-4樹(shù)對(duì)應(yīng)，而且兩種樹(shù)操作也一樣。

2-3-4樹(shù)用結(jié)點(diǎn)分裂保持平衡，紅-黑樹(shù)用顏色變換和旋轉(zhuǎn)保持平衡。

3.1 定義

1.每個(gè)結(jié)點(diǎn)要么是紅的，要么是黑的。
2.根結(jié)點(diǎn)是黑的。
3.每個(gè)葉結(jié)點(diǎn)，即空結(jié)點(diǎn)（NIL）是黑的。
4.如果一個(gè)結(jié)點(diǎn)是紅的，那么它的倆個(gè)兒子都是黑的。
5.對(duì)每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)。

3.2 插入

基本流程:

1. 將紅黑樹(shù)當(dāng)作一顆二叉查找樹(shù)，將結(jié)點(diǎn)插入
2. 將插入的結(jié)點(diǎn)著色為紅色
3. 通過(guò)一系列的旋轉(zhuǎn)或著色等操作，使之重新成為一顆紅黑樹(shù)

其中旋轉(zhuǎn)著色根據(jù)插入的結(jié)點(diǎn)父結(jié)點(diǎn)情況分為以下三種類(lèi)型：

3.2.1 插入根結(jié)點(diǎn)

直接改為黑色

3.2.2 插入結(jié)點(diǎn)的父結(jié)點(diǎn)是黑色

紅黑樹(shù)插入1.png

3.2.3 插入結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色

處理思路：將紅色的結(jié)點(diǎn)移到根結(jié)點(diǎn)，再將根結(jié)點(diǎn)設(shè)為黑色。

實(shí)際又可以細(xì)化如下幾種情況：

3.2.3.1 叔叔結(jié)點(diǎn)為紅色

處理步驟：

1. 父結(jié)點(diǎn)設(shè)置為黑色
2. 叔叔結(jié)點(diǎn)設(shè)置為黑色
3. 祖父結(jié)點(diǎn)設(shè)為紅色
4. 祖父結(jié)點(diǎn)設(shè)為“當(dāng)前結(jié)點(diǎn)”，繼續(xù)向上遍歷

3.2.3.2 父結(jié)點(diǎn)是左結(jié)點(diǎn)，叔叔結(jié)點(diǎn)是黑色

處理步驟：

1. 對(duì)祖父節(jié)點(diǎn)右旋
2. 父結(jié)點(diǎn)設(shè)為黑色
3. 祖父節(jié)點(diǎn)設(shè)為紅色

3.2.3.3 父結(jié)點(diǎn)是右結(jié)點(diǎn)，叔叔結(jié)點(diǎn)是黑色

處理步驟：

1. 對(duì)父結(jié)點(diǎn)左旋
2. 按照步驟二處理

詳細(xì)圖解：

紅黑樹(shù)插入2.png

3.3 刪除

3.3.1 葉子結(jié)點(diǎn)

3.3.1.1 葉子結(jié)點(diǎn)是紅色

無(wú)需處理

3.3.1.2 葉子結(jié)點(diǎn)是黑色

當(dāng)前結(jié)點(diǎn)是左結(jié)點(diǎn)：

左結(jié)點(diǎn)1.png

左結(jié)點(diǎn)2.png

左結(jié)點(diǎn)3.png

左結(jié)點(diǎn)4.png

E. 兄弟結(jié)點(diǎn)設(shè)為紅色，父結(jié)點(diǎn)設(shè)為遞歸結(jié)點(diǎn)遞歸，指導(dǎo)根節(jié)點(diǎn)或紅色節(jié)點(diǎn)

左結(jié)點(diǎn)5.png

當(dāng)前結(jié)點(diǎn)是右結(jié)點(diǎn)：

右結(jié)點(diǎn)1.png

右結(jié)點(diǎn)2.png

右結(jié)點(diǎn)3.png

右結(jié)點(diǎn)4.png

E. 兄弟結(jié)點(diǎn)設(shè)為紅色，父結(jié)點(diǎn)設(shè)為遞歸結(jié)點(diǎn)遞歸，指導(dǎo)根節(jié)點(diǎn)或紅色節(jié)點(diǎn)

右結(jié)點(diǎn)5.png

3.3.2 非葉子結(jié)點(diǎn)，只有一個(gè)結(jié)點(diǎn)

父結(jié)點(diǎn)P下面只有一個(gè)子節(jié)點(diǎn)C，則可以將結(jié)點(diǎn)P和節(jié)點(diǎn)C交換，則可以轉(zhuǎn)換成【3.3.1 葉子結(jié)點(diǎn)】情景。

3.3.3 非葉子結(jié)點(diǎn)，有兩個(gè)子結(jié)點(diǎn)

刪除的結(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，通過(guò)交換結(jié)點(diǎn)P和后繼節(jié)點(diǎn)N的方式，將刪除結(jié)點(diǎn)P轉(zhuǎn)化為結(jié)點(diǎn)N。

后繼結(jié)點(diǎn)N分為兩種情況：

• 是葉子結(jié)點(diǎn)【3.3.1 葉子結(jié)點(diǎn)】
• 有一個(gè)子結(jié)點(diǎn)【3.3.2 非葉子結(jié)點(diǎn)，只有一個(gè)結(jié)點(diǎn)】