二叉搜索樹

二叉搜索樹（Binary Sort Tree）又稱二叉查找樹（Binary Search Tree），亦稱二叉排序樹。 它或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：
（1）若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
（3）左、右子樹也分別為二叉排序樹；

節(jié)點度：節(jié)點擁有的子樹數(shù)。上圖中，62的度為2，37的度為1，36的度為0。

樹的深度：從根節(jié)點開始（其深度為0）自頂向下逐層累加的。上圖中，36的深度是5，29的深度是4，51的深度是3。

樹的高度：從葉子節(jié)點開始（其高度為0）自底向上逐層累加的。36的高度是0，根節(jié)點62的高度是5。

平衡因子:?此節(jié)點往下?左子樹深度 - 右子樹深度=平衡因子

平衡二叉樹

1.定義

平衡二叉樹也叫自平衡二叉搜索樹（Self-Balancing Binary Search Tree），所以其本質(zhì)也是一顆二叉搜索樹，不過為了限制左右子樹的高度差，避免出現(xiàn)傾斜樹等偏向于線性結(jié)構(gòu)演化的情況，所以對二叉搜索樹中每個節(jié)點的左右子樹作了限制，左右子樹的高度差稱之為平衡因子，樹中每個節(jié)點的平衡因子絕對值不大于1 ，此時二叉搜索樹稱之為平衡二叉樹。

自平衡是指，在對平衡二叉樹執(zhí)行插入或刪除節(jié)點操作后，可能會導致樹中某個節(jié)點的平衡因子絕對值超過1 ，即平衡二叉樹變得“不平衡”，為了恢復該節(jié)點左右子樹的平衡，此時需要對節(jié)點執(zhí)行旋轉(zhuǎn)操作。

2.性質(zhì)

它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

平衡的調(diào)整共有四種情況：分別為LL,LR,RR,RL。

下面我們通過不斷插入數(shù)據(jù)來說明幾種不同的旋轉(zhuǎn)方式:

注意：橘黃色的結(jié)點為旋轉(zhuǎn)中心，黑色結(jié)點的為離插入結(jié)點最近的失衡結(jié)點。

（1）LR型:在左孩子L的節(jié)點上插入了左孩子節(jié)點L的右孩子節(jié)點R

最開始插入數(shù)據(jù)16，3，7后的結(jié)構(gòu)如上圖所示，結(jié)點16失去了平衡，3為16的左孩子，7為失衡結(jié)點的左孩子的右孩子，所以為LR型，接下來通過兩次旋轉(zhuǎn)操作復衡，先通過以3為旋轉(zhuǎn)中心，進行左旋轉(zhuǎn)，結(jié)果如圖所示，然后再以7為旋轉(zhuǎn)中心進行右旋轉(zhuǎn)，旋轉(zhuǎn)后恢復平衡了。

（2）LL型:在左孩子L的節(jié)點上插入了左孩子節(jié)點L的左孩子節(jié)點L

在上面恢復平衡后我們再次插入數(shù)據(jù)11和9,發(fā)現(xiàn)又失去平衡了，這次失衡結(jié)點是16，11是其左孩子，9為其失衡結(jié)點的左孩子的左孩子，所以是LL型，以失衡結(jié)點的左孩子為旋轉(zhuǎn)中心進行一次右旋轉(zhuǎn)即可。

（3）RR型:在右孩子R的節(jié)點上插入了右孩子節(jié)點R的右孩子節(jié)點R

進一步插入數(shù)據(jù)26后又再次失衡了，失衡結(jié)點為7,很明顯這是RR型，以失衡結(jié)點的右孩子為旋轉(zhuǎn)中心左旋轉(zhuǎn)一次即可。

（4）RL型:在右孩子R的節(jié)點上插入了右孩子節(jié)點R的左孩子節(jié)點L

再插入18后又再次失衡了，失衡結(jié)點為16，26為其右孩子，18為其右孩子的左孩子，為RL型，以失衡結(jié)點的右孩子為旋轉(zhuǎn)中心，進行一次右旋轉(zhuǎn)，然后再次已失衡結(jié)點的右孩子為旋轉(zhuǎn)中心進行一次左旋轉(zhuǎn)變恢復了平衡。

紅黑樹

紅黑樹是一種自平衡二叉查找樹，與 AVL 樹類似，提供 O(logN) 級別的查詢、插入和刪除節(jié)點復雜度。相對于 AVL 樹單純的對每個節(jié)點的平衡因子進行判斷，紅黑樹給節(jié)點賦予了顏色屬性，并通過對樹中節(jié)點的顏色進行限制，來保持整棵樹的平衡。

之前提到的自平衡二叉查找樹，即 AVL 樹，屬于一種高度平衡的二叉查找樹，對每個節(jié)點的平衡因子進行嚴苛的限制，所以 AVL 樹能夠提供 O(logN) 的節(jié)點查詢復雜度。也因為對每個節(jié)點的平衡因子限制較大，所以插入和刪除節(jié)點時，需要進行很頻繁的平衡調(diào)節(jié)操作。

紅黑樹相對于 AVL 樹，對樹的高度限制較為寬松，所以紅黑樹的查找復雜度要略遜于 AVL 樹。也因為對樹高度的限制較小，所以插入和刪除節(jié)點時需要較少的旋轉(zhuǎn)操作即可達到平衡狀態(tài)。

由于每一棵紅黑樹都是一顆二叉排序樹，因此，在對紅黑樹進行查找時，可以采用運用于普通二叉排序樹上的查找算法，在查找過程中不需要顏色信息。

條件限制

紅黑樹中的節(jié)點存在顏色屬性，通過對節(jié)點顏色的限制來保持樹的平衡性。平衡的紅黑樹要求如下：

1. 節(jié)點是紅色或者黑色；

2. 根節(jié)點是黑色；

3. 所有葉子都是黑色（葉子是NIL結(jié)點）；

4. 每個紅色結(jié)點的兩個子結(jié)點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色結(jié)點）

5. 從任一節(jié)點到其后代的葉子節(jié)點路徑中包含相同個數(shù)的黑色節(jié)點。

這些約束強制了紅黑樹的關(guān)鍵性質(zhì): 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結(jié)果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。

是性質(zhì)4導致路徑上不能有兩個連續(xù)的紅色結(jié)點確保了這個結(jié)果。最短的可能路徑都是黑色結(jié)點，最長的可能路徑有交替的紅色和黑色結(jié)點。因為根據(jù)性質(zhì)5所有最長的路徑都有相同數(shù)目的黑色結(jié)點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。

什么是 NIL

NIL節(jié)點也稱為外部節(jié)點或空節(jié)點，它是紅黑樹中一種特殊的節(jié)點類型。NIL節(jié)點不存儲實際的數(shù)據(jù)，它們的作用是協(xié)助維護紅黑樹的結(jié)構(gòu)和性質(zhì)，同時也簡化了一些操作的實現(xiàn)。

在紅黑樹中，每個節(jié)點要么是紅色的，要么是黑色的，而每個節(jié)點都有左子節(jié)點和右子節(jié)點。NIL節(jié)點是所有葉子節(jié)點的虛擬父節(jié)點，它們都是黑色的，且不包含任何子節(jié)點。這意味著，如果一個節(jié)點沒有左子節(jié)點或右子節(jié)點，那么它的對應子節(jié)點就是一個NIL節(jié)點。

通過將紅黑樹的所有葉子節(jié)點都替換為NIL節(jié)點，我們可以保證紅黑樹的每個節(jié)點都至少有一個子節(jié)點。這樣，我們就可以通過判斷節(jié)點的子節(jié)點是否為NIL節(jié)點來處理邊界情況，避免了在處理節(jié)點時需要特殊處理葉子節(jié)點的情況。

在紅黑樹中，NIL節(jié)點通常用一個特殊的指針表示，比如用 NULL 或 nullptr 表示。在某些實現(xiàn)中，NIL節(jié)點可能會占用一些內(nèi)存空間，但是由于它們不包含任何實際的數(shù)據(jù)，因此這種內(nèi)存開銷通?？梢院雎圆挥?。

旋轉(zhuǎn)

當對紅黑樹進行插入或刪除時，就有可能破壞紅黑樹的性質(zhì)，這時需要通過變色、左旋與右旋操作平衡紅黑樹。變色操作很簡單，紅變黑，黑變紅，就不仔細介紹了，下面介紹左旋與右旋

左旋

此圖是以X為旋轉(zhuǎn)結(jié)點

定義：以某個結(jié)點作為支點(旋轉(zhuǎn)結(jié)點)，其右子結(jié)點變?yōu)樾D(zhuǎn)結(jié)點的父結(jié)點，右子結(jié)點的左子結(jié)點變?yōu)樾D(zhuǎn)結(jié)點的右子結(jié)點，左子結(jié)點保持不變。

右旋

此圖是以Y結(jié)點為旋轉(zhuǎn)結(jié)點

定義：以某個結(jié)點作為支點(旋轉(zhuǎn)結(jié)點)，其左子結(jié)點變?yōu)樾D(zhuǎn)結(jié)點的父結(jié)點，左子結(jié)點的右子結(jié)點變?yōu)樾D(zhuǎn)結(jié)點的左子結(jié)點，右子結(jié)點保持不變。

插入節(jié)點情況

待插入新節(jié)點顏色初始為紅色，因為紅色節(jié)點的插入不一定影響紅黑樹的平衡性，而黑色節(jié)點的插入一定會引起紅黑樹的不平衡。

新節(jié)點的插入有如下幾種情形：

1. 新節(jié)點為根節(jié)點。

即當前紅黑樹為空樹，插入新節(jié)點后，只需要變換節(jié)點顏色為黑色，即可滿足紅黑樹的平衡限制條件；

2. 新節(jié)點的父節(jié)點為黑色。

若新節(jié)點不為根節(jié)點，則具有父節(jié)點，父節(jié)點顏色無外乎黑、紅兩種。當父節(jié)點顏色為黑色時，此時插入新節(jié)點不影響紅黑樹的平衡性，所以不需要調(diào)整操作；

3. 新節(jié)點的父節(jié)點為紅色，同時叔父節(jié)點的顏色也為紅色。

若父節(jié)點和叔父節(jié)點的顏色都為紅色，則根據(jù)條件 4 ，祖父節(jié)點的顏色為黑色。因為新插入節(jié)點顏色為紅色，違反了條件 4，此時只需要變換父節(jié)點和叔父節(jié)點的顏色為黑色，祖父節(jié)點的顏色為紅色即可。變換顏色后，只需要考慮祖父節(jié)點顏色為紅色，是否違反了條件限制，將祖父節(jié)點作為“新”節(jié)點，遞歸進行處理即可。

此時無所謂新節(jié)點是其父節(jié)點的左子節(jié)點或右子節(jié)點。

4. 新節(jié)點的父節(jié)點為紅色，叔父節(jié)點的顏色不為紅色。且新節(jié)點 N 是其父節(jié)點 P 的左子節(jié)點，同時父 P 節(jié)點 是祖父節(jié)點 G 的左子節(jié)點；或者新節(jié)點 N 是其父節(jié)點 P 的右子節(jié)點，同時父節(jié)點 P 是祖父節(jié)點 G 的右子節(jié)點。

不妨假設新節(jié)點 N 是其父節(jié)點 P 的左子節(jié)點，同時父節(jié)點 P 是祖父節(jié)點 G 的左子節(jié)點。因為父節(jié)點 P 為紅色，所以祖父節(jié)點 G 顏色為黑色。此時以 P 節(jié)點為軸心執(zhí)行一次右旋操作，并對父節(jié)點 P 和祖父節(jié)點 G 進行顏色變換。

旋轉(zhuǎn)后的變色操作，保證了通過每個節(jié)點到后代葉子節(jié)點的路徑上，包含的黑色節(jié)點個數(shù)不變，即滿足了條件約束。

新節(jié)點 N 不一定只是一個單一的新插入節(jié)點，也可能是一顆二叉樹的根節(jié)點，例如情形 3 的處理后，遞歸處理的“新”節(jié)點就是二叉樹的根節(jié)點?？瞻椎牟糠直硎敬颂幙赡転榭諛浠蚍强諛?，其實這里的叔父節(jié)點 U 也可以是空樹或非空樹。

5. 新節(jié)點的父節(jié)點為紅色，叔父節(jié)點的顏色不為紅色。且新節(jié)點 N 是其父節(jié)點 P 的右子節(jié)點，同時父節(jié)點 P 是祖父節(jié)點 G 的左子節(jié)點；或者新節(jié)點 N 是其父節(jié)點 P 的左子節(jié)點，同時父節(jié)點 P 是祖父節(jié)點 G 的右子節(jié)點。

不妨假設新節(jié)點 P 是其父節(jié)點 N 的右子節(jié)點，同時父節(jié)點 P 是祖父節(jié)點 G 的左子節(jié)點。因為父節(jié)點 P 為紅色，所以祖父節(jié)點 G 顏色為黑色。此時以節(jié)點 N 為軸心執(zhí)行一次左旋操作。

旋轉(zhuǎn)操作前后，通過每個節(jié)點到后代葉子節(jié)點的路徑上，所經(jīng)過的黑色節(jié)點個數(shù)不發(fā)生變化。此時情形轉(zhuǎn)變?yōu)榍樾?4，所以按照情形 4 進行處理即可。

由插入節(jié)點的情形分析可知，插入節(jié)點時最多只會進行兩次旋轉(zhuǎn)操作，即情形 5 旋轉(zhuǎn)后變?yōu)榍樾?4，情形 4 旋轉(zhuǎn)變色后滿足平衡條件。變色操作則可能遞歸進行到根節(jié)點。

刪除節(jié)點情況

二叉查找樹在進行節(jié)點刪除時，若待刪除節(jié)點的度為 2 時，則可以將刪除操作“轉(zhuǎn)移”到其后代度不為 2 的子節(jié)點上，所以后續(xù)討論的待刪除節(jié)點的度都不為 2。

節(jié)點刪除有如下幾種情形：

1. 待刪除節(jié)點顏色為紅色。

因為待刪除節(jié)點的度為 0 或 1，根據(jù)條件 5 可知，該待刪除節(jié)點為葉子節(jié)點，所以直接刪除該節(jié)點并不影響二叉樹的平衡性。

2. 待刪除節(jié)點為黑色，度為 1。

根據(jù)條件 5 可知，若待刪除節(jié)點度為 1，則子節(jié)點顏色為紅色。此時可以直接刪除該節(jié)點，用子節(jié)點來填充該節(jié)點位置，對子節(jié)點進行顏色變換即可。

3. 待刪除節(jié)點為黑色，度為 0。

情形 1, 2 中的節(jié)點刪除場景較為簡單，可以直接進行節(jié)點刪除操作，最多只需要通過節(jié)點顏色變換即可保持二叉樹的平衡性（注意根節(jié)點的變化）。若待刪除節(jié)點度為 0，此時不妨對二叉樹先進行一番預平衡操作，然后再進行節(jié)點刪除，以此保證刪除節(jié)點后二叉樹處于平衡狀態(tài)。

下面以 N 表示待刪除節(jié)點，以 P 表示待刪除節(jié)點的父節(jié)點，以 S 表示待刪除節(jié)點的兄弟節(jié)點，以 SL表示兄弟節(jié)點的左子節(jié)點，以 SR?表示兄弟節(jié)點的右子節(jié)點。不妨以 N 節(jié)點作為 P 節(jié)點的左子節(jié)點進行討論，對稱的情況下處理過程類似。

3.1 兄弟節(jié)點 S 為黑色， SR節(jié)點為紅色。

兄弟節(jié)點 S 的右子節(jié)點 SR?為紅色，則兄弟節(jié)點 S 為黑色，父節(jié)點 P 顏色不確定。此時以節(jié)點 S 為軸心執(zhí)行左旋操作，并對部分節(jié)點執(zhí)行顏色變換操作。

左旋操作后，變換 SR?節(jié)點顏色。若 P 節(jié)點為紅色，則左旋操作后，對 P 節(jié)點和 S 節(jié)點進行顏色變換。此時刪除節(jié)點 N 之后，通過其他節(jié)點的路徑上黑色節(jié)點個數(shù)不變，滿足平衡條件。

3.2 兄弟節(jié)點 S 為黑色，SL?節(jié)點為紅色，SR節(jié)點不為紅色。

兄弟節(jié)點 S 的左子節(jié)點 SR?為紅色，則兄弟節(jié)點 S 為黑色，父節(jié)點 P 顏色不確定， SR?節(jié)點不存在或存在為黑色。此時以節(jié)點 SL?為軸心執(zhí)行右旋操作，并對 S 和 SL?節(jié)點執(zhí)行顏色變換操作。

執(zhí)行右旋操作后可以發(fā)現(xiàn)，此時情形演變?yōu)榍樾?3.1，所以此時再次對待刪除節(jié)點 N 進行平衡操作即可。

3.3 兄弟節(jié)點 S 為黑色，S 節(jié)點沒有紅色子節(jié)點，且父節(jié)點 P 為黑色。

兄弟節(jié)點 S 和父節(jié)點 P 為黑色，且兄弟節(jié)點 S 沒有紅色子節(jié)點，此時對 S 進行顏色變換。

對兄弟節(jié)點 S 進行顏色變換后，可以發(fā)現(xiàn)，忽略待刪除節(jié)點 N，此時父節(jié)點 P 處于和待刪除節(jié)點 N 同樣的處境，即通過該節(jié)點的路徑上黑色節(jié)點個數(shù)減一。所以此時將父節(jié)點 P 作為新的節(jié)點 N 進行同樣的預平衡操作。

3.4 兄弟節(jié)點 S 為黑色，S 節(jié)點沒有紅色子節(jié)點，且父節(jié)點 P 為紅色。

兄弟節(jié)點 S 為黑色，且沒有紅色子節(jié)點，父節(jié)點 P 為紅色，此時只需要對節(jié)點 S 和 P 進行顏色變換即可。

對兄弟節(jié)點 S 和父節(jié)點 P 進行顏色變換后，可以發(fā)現(xiàn)，忽略待刪除節(jié)點 N ，此時通過各節(jié)點的路徑上黑色節(jié)點個數(shù)不變，即二叉樹處于平衡狀態(tài)。

3.5 兄弟節(jié)點 S 為紅色。

兄弟節(jié)點 S 為紅色，則此時父節(jié)點 P 為黑色。此時以 S 節(jié)點為軸心進行左旋操作，并對節(jié)點 S 和 P 進行變色操作。

旋轉(zhuǎn)并進行節(jié)點顏色變換后，可以發(fā)現(xiàn)，此時的二叉樹同樣處于平衡狀態(tài)，所以這一步的旋轉(zhuǎn)與顏色變換操作只是一個過渡處理，并沒有起到預平衡的作用，即刪除節(jié)點 N 之后，二叉樹仍然是不平衡的。但是經(jīng)過該步的處理之后，二叉樹的狀態(tài)演變?yōu)榍樾?3.1，3.2 或者 3.4 中的一種，所以可以對待刪除節(jié)點 N 再次進行預平衡處理。

節(jié)點刪除的所有情況如上，由各個情形描述可知，節(jié)點刪除最多經(jīng)過三次旋轉(zhuǎn)即可達到平衡狀態(tài)，即情形 3.5 旋轉(zhuǎn)后變?yōu)榍樾?3.2，情形 3.2 旋轉(zhuǎn)后變?yōu)榍樾?3.1，情形 3.1 旋轉(zhuǎn)后滿足平衡條件。變色操作則可能遞歸進行到根節(jié)點。