二叉搜索樹的平衡技巧一、概述

二叉搜索樹（BinarySearchTree,BST）是一種基于鍵值有序存儲的樹形數(shù)據(jù)結(jié)構(gòu)，其核心特性包括：左子樹所有節(jié)點(diǎn)的鍵值小于根節(jié)點(diǎn)，右子樹所有節(jié)點(diǎn)的鍵值大于根節(jié)點(diǎn)。然而，在非均勻插入或刪除操作下，BST可能退化為鏈表，導(dǎo)致查找、插入、刪除等操作的時間復(fù)雜度降至O(n)。為維持樹的高效性能，需采用平衡技巧，確保樹的高度始終保持在O(logn)級別。本文將介紹二叉搜索樹的平衡技巧，包括旋轉(zhuǎn)操作、AVL樹和紅黑樹的基本原理與實現(xiàn)。

二、二叉搜索樹的平衡問題

（一）不平衡的原因

1.插入操作導(dǎo)致右重左輕

-當(dāng)新節(jié)點(diǎn)持續(xù)插入某一側(cè)時，樹會向該側(cè)傾斜，破壞平衡性。

2.刪除操作導(dǎo)致左重右輕

-刪除節(jié)點(diǎn)可能導(dǎo)致另一側(cè)過度增長，引發(fā)不平衡。

（二）平衡的定義

-樹的任意節(jié)點(diǎn)的左右子樹高度差不超過1，即平衡因子（BalanceFactor）∈{-1,0,1}。

三、旋轉(zhuǎn)操作實現(xiàn)平衡

旋轉(zhuǎn)是調(diào)整樹平衡的基本手段，分為四種情況：左旋、右旋、左-右旋、右-左旋。

（一）左旋（LeftRotation）

1.適用場景：右重左輕（平衡因子為-2）。

2.操作步驟：

(1)將原根節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)為新的根節(jié)點(diǎn)。

(2)原根節(jié)點(diǎn)成為新根節(jié)點(diǎn)的左子節(jié)點(diǎn)。

(3)若原右子節(jié)點(diǎn)存在左子樹，將其掛載至原根節(jié)點(diǎn)的右子節(jié)點(diǎn)。

（二）右旋（RightRotation）

1.適用場景：左重右輕（平衡因子為2）。

2.操作步驟：

(1)將原根節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)為新的根節(jié)點(diǎn)。

(2)原根節(jié)點(diǎn)成為新根節(jié)點(diǎn)的右子節(jié)點(diǎn)。

(3)若原左子節(jié)點(diǎn)存在右子樹，將其掛載至原根節(jié)點(diǎn)的左子節(jié)點(diǎn)。

（三）左-右旋（Left-RightRotation）

1.適用場景：左重且左子樹右重（平衡因子為-2且左子節(jié)點(diǎn)平衡因子為2）。

2.操作步驟：

(1)對左子節(jié)點(diǎn)執(zhí)行左旋。

(2)對原根節(jié)點(diǎn)執(zhí)行右旋。

（四）右-左旋（Right-LeftRotation）

1.適用場景：右重且右子樹左重（平衡因子為2且右子節(jié)點(diǎn)平衡因子為-2）。

2.操作步驟：

(1)對右子節(jié)點(diǎn)執(zhí)行右旋。

(2)對原根節(jié)點(diǎn)執(zhí)行左旋。

四、AVL樹的實現(xiàn)

AVL樹是最早的平衡二叉搜索樹，通過旋轉(zhuǎn)操作維持平衡。

（一）節(jié)點(diǎn)結(jié)構(gòu)

-每個節(jié)點(diǎn)包含：鍵值、左右子節(jié)點(diǎn)指針、高度屬性。

（二）插入操作

1.普通BST插入節(jié)點(diǎn)。

2.更新節(jié)點(diǎn)高度：height(node)=max(height(left),height(right))+1。

3.計算平衡因子：balance(node)=height(left)-height(right)。

4.根據(jù)平衡因子執(zhí)行旋轉(zhuǎn)操作。

（三）刪除操作

1.普通BST刪除節(jié)點(diǎn)。

2.更新高度與平衡因子。

3.若不平衡，執(zhí)行相應(yīng)的旋轉(zhuǎn)操作。

五、紅黑樹優(yōu)化

紅黑樹是更實用的平衡樹，通過顏色屬性（紅/黑）和規(guī)則限制平衡。

（一）紅黑樹規(guī)則

1.每個節(jié)點(diǎn)為紅或黑。

2.根節(jié)點(diǎn)為黑。

3.紅節(jié)點(diǎn)的子節(jié)點(diǎn)必為黑（無連續(xù)紅節(jié)點(diǎn)）。

4.從任一節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡單路徑上黑節(jié)點(diǎn)數(shù)相同。

（二）旋轉(zhuǎn)與著色操作

1.插入時將節(jié)點(diǎn)設(shè)為紅色。

2.若違反規(guī)則，通過旋轉(zhuǎn)（左旋/右旋）和著色（紅變黑/黑變紅）修復(fù)。

3.常見修復(fù)步驟：

(1)祖父節(jié)點(diǎn)為紅、父節(jié)點(diǎn)為紅：將父節(jié)點(diǎn)變黑，祖父變紅，可能需遞歸修復(fù)。

(2)其他情況通過旋轉(zhuǎn)調(diào)整路徑顏色。

六、應(yīng)用場景

-索引數(shù)據(jù)庫（如B+樹基于AVL原理）。

-基于樹的符號表。

-高效查找與動態(tài)集合操作。

七、總結(jié)

一、概述

二叉搜索樹（BinarySearchTree,BST）是一種基于鍵值有序存儲的樹形數(shù)據(jù)結(jié)構(gòu)，其核心特性包括：左子樹所有節(jié)點(diǎn)的鍵值小于根節(jié)點(diǎn)，右子樹所有節(jié)點(diǎn)的鍵值大于根節(jié)點(diǎn)。然而，在非均勻插入或刪除操作下，BST可能退化為鏈表，導(dǎo)致查找、插入、刪除等操作的時間復(fù)雜度降至O(n)。這不僅降低了數(shù)據(jù)結(jié)構(gòu)的效率，也使得其優(yōu)勢無法發(fā)揮。為了維持樹的高效性能，確保查找、插入、刪除等操作的時間復(fù)雜度穩(wěn)定在O(logn)，必須采用平衡技巧。平衡技巧的核心目標(biāo)是通過一系列的調(diào)整操作，確保樹在任意狀態(tài)下都盡可能接近完全平衡，從而保持其高度為O(logn)。本文將詳細(xì)介紹二叉搜索樹的平衡問題，深入解析旋轉(zhuǎn)操作的具體實現(xiàn)，并闡述AVL樹和紅黑樹這兩種經(jīng)典的平衡二叉搜索樹（BalancedBinarySearchTree）的設(shè)計原理、操作方法及其應(yīng)用場景。

二、二叉搜索樹的平衡問題

（一）不平衡的原因

1.插入操作導(dǎo)致右重左輕：當(dāng)新節(jié)點(diǎn)的鍵值持續(xù)大于某個節(jié)點(diǎn)的鍵值，并且這些插入操作都發(fā)生在該節(jié)點(diǎn)的右子樹時，樹會向左傾斜，右側(cè)的深度遠(yuǎn)大于左側(cè)，導(dǎo)致整個樹的平衡被破壞。同樣，若新節(jié)點(diǎn)持續(xù)插入在左子樹，則樹會向右傾斜。這種不均衡會顯著增加樹的高度，從而影響操作效率。

-具體示例：假設(shè)我們依次插入鍵值[10,20,30,40,50]，這些鍵值都大于前一個，樹會迅速變成一條右斜鏈。

2.刪除操作導(dǎo)致左重右輕：刪除節(jié)點(diǎn)的過程可能導(dǎo)致另一側(cè)子樹過快增長，從而引發(fā)不平衡。特別是當(dāng)刪除操作導(dǎo)致某個節(jié)點(diǎn)的替代者是來自其右側(cè)或左側(cè)較深子樹時，更容易引發(fā)不平衡。

-具體示例：假設(shè)我們從傾斜的右重樹中刪除一個節(jié)點(diǎn)，如果其替代者是來自左子樹，可能導(dǎo)致原本較淺的左子樹突然變得非常深。

（二）平衡的定義

-平衡二叉搜索樹要求樹中任意節(jié)點(diǎn)的左右子樹的高度差（稱為平衡因子，BalanceFactor）必須嚴(yán)格小于或等于1。即對于樹中的任意節(jié)點(diǎn)node，滿足`|height(left_subtree(node))-height(right_subtree(node))|<=1`。這個條件保證了從根節(jié)點(diǎn)到任何葉節(jié)點(diǎn)的最長路徑長度（樹的高度）不會超過最短路徑長度的兩倍，從而確保了操作的時間復(fù)雜度為O(logn)。

-高度（Height）的定義：樹的高度是指從根節(jié)點(diǎn)到最遠(yuǎn)葉節(jié)點(diǎn)的最長路徑上的邊數(shù)?？諛涞母叨葹?1，單節(jié)點(diǎn)樹的高度為0。

三、旋轉(zhuǎn)操作實現(xiàn)平衡

旋轉(zhuǎn)是調(diào)整樹平衡最基本、最常用的操作。通過局部地改變節(jié)點(diǎn)的連接方式，可以重新分配樹中節(jié)點(diǎn)的分布，從而修復(fù)不平衡。旋轉(zhuǎn)操作主要分為四種：左旋（LeftRotation）、右旋（RightRotation）、左-右旋（Left-RightRotation，也稱為LR旋轉(zhuǎn)）、右-左旋（Right-LeftRotation，也稱為RL旋轉(zhuǎn)）。這些旋轉(zhuǎn)操作通常在插入或刪除操作后，根據(jù)節(jié)點(diǎn)的平衡因子來判斷是否需要進(jìn)行以及執(zhí)行哪種旋轉(zhuǎn)。

（一）左旋（LeftRotation）

1.適用場景：當(dāng)某個節(jié)點(diǎn)的平衡因子為-2時，表示其右子樹比左子樹高至少兩層，且不平衡發(fā)生在左子樹的右側(cè)（即右子樹的右子樹更高或右子樹本身就是紅色且右子樹右子樹是紅色，在紅黑樹中更常見）。此時需要進(jìn)行左旋，以提升左子樹的高度，降低右子樹的高度，從而恢復(fù)平衡。左旋針對的是“右重左輕”的情況。

2.操作步驟：

-定位失衡節(jié)點(diǎn)：假設(shè)節(jié)點(diǎn)`y`是失衡的節(jié)點(diǎn)，且`y`的平衡因子為-2。根據(jù)BST性質(zhì)，`y`一定有一個右子節(jié)點(diǎn)`x`。同時，`x`也一定有一個左子節(jié)點(diǎn)`T2`（否則`y`的平衡因子不會是-2）。這里的`T1`、`T2`等表示子樹，是為了描述旋轉(zhuǎn)而引入的符號，其中`T2`是`x`的左子樹。

-執(zhí)行旋轉(zhuǎn)：以`x`為新的根節(jié)點(diǎn)，進(jìn)行旋轉(zhuǎn)。具體來說，將原根節(jié)點(diǎn)`y`連接到`x`的左子節(jié)點(diǎn)`T2`；將`x`連接到原根節(jié)點(diǎn)`y`。即：

-`y`的右子節(jié)點(diǎn)變?yōu)閌x`的左子節(jié)點(diǎn)。

-`x`的左子節(jié)點(diǎn)變?yōu)閌y`的右子節(jié)點(diǎn)。

-`y`成為`x`的父節(jié)點(diǎn)。

-更新父節(jié)點(diǎn)和根節(jié)點(diǎn)：旋轉(zhuǎn)后，`y`的父節(jié)點(diǎn)（如果存在）現(xiàn)在指向`x`。如果`y`是原來的根節(jié)點(diǎn)，那么`x`成為新的根節(jié)點(diǎn)。

-（AVL樹特有）更新高度：旋轉(zhuǎn)后，需要更新受影響的節(jié)點(diǎn)的高度。通常，`y`的高度和`x`的高度都需要重新計算，因為它們的子樹發(fā)生了變化。具體更新規(guī)則依賴于高度的定義（例如，高度是子樹高度的最大值加1）。

-（AVL樹/紅黑樹特有）更新顏色：在AVL樹中，可能需要調(diào)整節(jié)點(diǎn)的黑色高度。在紅黑樹中，左旋通常發(fā)生在父節(jié)點(diǎn)是紅色、子節(jié)點(diǎn)是紅色的場景，左旋后可能需要重新著色（例如，將`x`著為黑色，`y`著為紅色）以修復(fù)紅黑樹的規(guī)則。

3.示例圖示（文字描述）：假設(shè)節(jié)點(diǎn)結(jié)構(gòu)為`node(left,key,right)`，左旋操作可以表示為：將`right`子節(jié)點(diǎn)提升為新的父節(jié)點(diǎn)，原父節(jié)點(diǎn)掛在提升節(jié)點(diǎn)的左側(cè)。具體代碼實現(xiàn)會涉及指針的重新指向。

（二）右旋（RightRotation）

1.適用場景：當(dāng)某個節(jié)點(diǎn)的平衡因子為2時，表示其左子樹比右子樹高至少兩層，且不平衡發(fā)生在左子樹的左側(cè)（即左子樹的左子樹更高或左子樹本身就是紅色且左子樹左子樹是紅色，在紅黑樹中更常見）。此時需要進(jìn)行右旋，以提升右子樹的高度，降低左子樹的高度，從而恢復(fù)平衡。右旋針對的是“左重右輕”的情況。

2.操作步驟：

-定位失衡節(jié)點(diǎn)：假設(shè)節(jié)點(diǎn)`y`是失衡的節(jié)點(diǎn)，且`y`的平衡因子為2。根據(jù)BST性質(zhì)，`y`一定有一個左子節(jié)點(diǎn)`x`。同時，`x`也一定有一個右子節(jié)點(diǎn)`T2`（否則`y`的平衡因子不會是2）。這里的`T1`、`T2`等表示子樹，`T2`是`x`的右子樹。

-執(zhí)行旋轉(zhuǎn)：以`x`為新的根節(jié)點(diǎn)，進(jìn)行旋轉(zhuǎn)。具體來說，將原根節(jié)點(diǎn)`y`連接到`x`的右子節(jié)點(diǎn)`T2`；將`x`連接到原根節(jié)點(diǎn)`y`。即：

-`y`的左子節(jié)點(diǎn)變?yōu)閌x`的右子節(jié)點(diǎn)。

-`x`的右子節(jié)點(diǎn)變?yōu)閌y`的左子節(jié)點(diǎn)。

-`y`成為`x`的父節(jié)點(diǎn)。

-更新父節(jié)點(diǎn)和根節(jié)點(diǎn)：旋轉(zhuǎn)后，`y`的父節(jié)點(diǎn)（如果存在）現(xiàn)在指向`x`。如果`y`是原來的根節(jié)點(diǎn)，那么`x`成為新的根節(jié)點(diǎn)。

-（AVL樹特有）更新高度：旋轉(zhuǎn)后，需要更新受影響的節(jié)點(diǎn)的高度。通常，`y`的高度和`x`的高度都需要重新計算。

-（AVL樹/紅黑樹特有）更新顏色：在AVL樹中，可能需要調(diào)整節(jié)點(diǎn)的黑色高度。在紅黑樹中，右旋通常發(fā)生在父節(jié)點(diǎn)是紅色、子節(jié)點(diǎn)是紅色的場景，右旋后可能需要重新著色（例如，將`x`著為黑色，`y`著為紅色）以修復(fù)紅黑樹的規(guī)則。

3.示例圖示（文字描述）：假設(shè)節(jié)點(diǎn)結(jié)構(gòu)為`node(left,key,right)`，右旋操作可以表示為：將`left`子節(jié)點(diǎn)提升為新的父節(jié)點(diǎn)，原父節(jié)點(diǎn)掛在提升節(jié)點(diǎn)的右側(cè)。具體代碼實現(xiàn)會涉及指針的重新指向。

（三）左-右旋（Left-RightRotation，LR旋轉(zhuǎn)）

1.適用場景：這種旋轉(zhuǎn)發(fā)生在節(jié)點(diǎn)`y`的平衡因子為-2，但其右子節(jié)點(diǎn)`x`的平衡因子為2的情況。這意味著不平衡同時發(fā)生在右子樹的右側(cè)（導(dǎo)致`y`右重）和右子樹的左側(cè)（導(dǎo)致`x`左重）。直接對`y`進(jìn)行左旋無法解決`x`的左重問題，因此需要先解決`x`的不平衡。

2.操作步驟：

(1)第一步：對右子節(jié)點(diǎn)`x`執(zhí)行左旋。

-這一步將`x`的左子節(jié)點(diǎn)提升到`x`的位置，同時將`x`變?yōu)樾碌母腹?jié)點(diǎn)（相對于`y`）。這一步操作修復(fù)了`x`的左重不平衡。

-具體左旋操作步驟同前所述，作用于節(jié)點(diǎn)`x`和其左子節(jié)點(diǎn)。

(2)第二步：對節(jié)點(diǎn)`y`執(zhí)行右旋。

-在第一步左旋之后，`y`的平衡因子可能變?yōu)?或仍然為-2（如果`x`的左子節(jié)點(diǎn)在第一步左旋中變成了`y`的右子節(jié)點(diǎn)，且它原本是紅色）。此時`y`仍然不平衡（右重），所以需要對其執(zhí)行右旋。

-具體右旋操作步驟同前所述，作用于節(jié)點(diǎn)`y`和其新的右子節(jié)點(diǎn)（即原`x`的右子節(jié)點(diǎn)`T3`）。

-顏色調(diào)整（AVL/紅黑樹特有）：在AVL樹中，可能需要同時更新高度。在紅黑樹中，這種旋轉(zhuǎn)通常發(fā)生在更復(fù)雜的著色場景，可能需要將原`y`和`x`的父節(jié)點(diǎn)、`x`本身、以及`x`的子節(jié)點(diǎn)進(jìn)行著色調(diào)整，以保持紅黑樹的規(guī)則。例如，可能需要將`x`著為黑色，原`y`和`x`的父節(jié)點(diǎn)著為紅色（如果它們原本是黑色），等等。

3.示例圖示（文字描述）：LR旋轉(zhuǎn)可以理解為先“矯正”右子樹的左重問題，再解決原樹的右重問題。先左旋右子節(jié)點(diǎn)，再右旋父節(jié)點(diǎn)。

（四）右-左旋（Right-LeftRotation，RL旋轉(zhuǎn)）

1.適用場景：這種旋轉(zhuǎn)發(fā)生在節(jié)點(diǎn)`y`的平衡因子為2，但其左子節(jié)點(diǎn)`x`的平衡因子為-2的情況。這意味著不平衡同時發(fā)生在左子樹的左側(cè)（導(dǎo)致`y`左重）和左子樹的右側(cè)（導(dǎo)致`x`右重）。

2.操作步驟：

(1)第一步：對左子節(jié)點(diǎn)`x`執(zhí)行右旋。

-這一步將`x`的右子節(jié)點(diǎn)提升到`x`的位置，同時將`x`變?yōu)樾碌母腹?jié)點(diǎn)（相對于`y`）。這一步操作修復(fù)了`x`的右重不平衡。

-具體右旋操作步驟同前所述，作用于節(jié)點(diǎn)`x`和其右子節(jié)點(diǎn)。

(2)第二步：對節(jié)點(diǎn)`y`執(zhí)行左旋。

-在第一步右旋之后，`y`的平衡因子可能變?yōu)?或仍然為2（如果`x`的右子節(jié)點(diǎn)在第一步右旋中變成了`y`的左子節(jié)點(diǎn)，且它原本是紅色）。此時`y`仍然不平衡（左重），所以需要對其執(zhí)行左旋。

-具體左旋操作步驟同前所述，作用于節(jié)點(diǎn)`y`和其新的左子節(jié)點(diǎn)（即原`x`的左子節(jié)點(diǎn)`T3`）。

-顏色調(diào)整（AVL/紅黑樹特有）：在AVL樹中，可能需要同時更新高度。在紅黑樹中，這種旋轉(zhuǎn)通常發(fā)生在更復(fù)雜的著色場景，可能需要將原`y`和`x`的父節(jié)點(diǎn)、`x`本身、以及`x`的子節(jié)點(diǎn)進(jìn)行著色調(diào)整，以保持紅黑樹的規(guī)則。例如，可能需要將`x`著為黑色，原`y`和`x`的父節(jié)點(diǎn)著為紅色（如果它們原本是黑色），等等。

3.示例圖示（文字描述）：RL旋轉(zhuǎn)可以理解為先“矯正”左子樹的右重問題，再解決原樹的左重問題。先右旋左子節(jié)點(diǎn)，再左旋父節(jié)點(diǎn)。

四、AVL樹的實現(xiàn)

AVL樹是第一個被發(fā)明的自平衡二叉搜索樹，由Adelson-Velsky和Landis于1962年提出。AVL樹通過強(qiáng)制要求樹中任何節(jié)點(diǎn)的左右子樹高度差不超過1（即平衡因子滿足`-1<=balance(node)<=1`），來保證樹的高度始終為O(logn)。

（一）節(jié)點(diǎn)結(jié)構(gòu)

-AVL樹的節(jié)點(diǎn)通常包含以下字段：

-`key`：存儲節(jié)點(diǎn)鍵值的字段。

-`left`：指向左子節(jié)點(diǎn)的指針。

-`right`：指向右子節(jié)點(diǎn)的指針。

-`height`：存儲該節(jié)點(diǎn)子樹高度的字段。

-（可選）`color`：在AVL樹中通常不使用顏色字段，除非是AVL紅黑混合樹，但標(biāo)準(zhǔn)AVL樹關(guān)注的是高度平衡。

-節(jié)點(diǎn)的高度計算方式通常為：`height(node)=max(height(node.left),height(node.right))+1`。如果節(jié)點(diǎn)是葉節(jié)點(diǎn)，其高度為0；如果節(jié)點(diǎn)是空節(jié)點(diǎn)，其高度為-1（這種定義方式使得樹的高度計算更簡潔）。

（二）插入操作

1.普通BST插入：首先按照BST的規(guī)則將節(jié)點(diǎn)插入到樹中。即，如果新節(jié)點(diǎn)的鍵值小于當(dāng)前節(jié)點(diǎn)的鍵值，則嘗試插入到左子樹；如果大于，則嘗試插入到右子樹；如果等于，則根據(jù)具體實現(xiàn)策略處理（例如，不插入、覆蓋、或者插入到左/右子樹）。

2.更新高度：插入新節(jié)點(diǎn)后，從插入點(diǎn)開始，向上遍歷至根節(jié)點(diǎn)，更新沿途經(jīng)過的所有節(jié)點(diǎn)的`height`字段。因為插入操作可能改變子樹的高度（例如，一個葉節(jié)點(diǎn)變成了一個內(nèi)部節(jié)點(diǎn)的子節(jié)點(diǎn)）。更新高度的過程是從底向上的。

-具體步驟：假設(shè)在插入新節(jié)點(diǎn)后，需要更新節(jié)點(diǎn)`p`及其祖先節(jié)點(diǎn)`q`的高度。如果插入發(fā)生在`p`的左子樹或右子樹，那么`p`的子樹高度會發(fā)生變化（或者`p`的某個子節(jié)點(diǎn)的高度從0變?yōu)?）。這會導(dǎo)致`p`的高度`height(p)=max(height(p.left),height(p.right))+1`可能改變。如果`p`的高度改變了，那么它的父節(jié)點(diǎn)`q`的`height(q)`也可能需要更新，依此類推，直到根節(jié)點(diǎn)。

3.檢查平衡因子并旋轉(zhuǎn)：在更新完高度后，從插入點(diǎn)所在的節(jié)點(diǎn)開始，向上遍歷至根節(jié)點(diǎn)，依次檢查每個節(jié)點(diǎn)的平衡因子`balance(node)=height(node.left)-height(node.right)`。

-如果遇到某個節(jié)點(diǎn)的平衡因子絕對值大于1（即`|balance(node)|>1`），則表示該節(jié)點(diǎn)失衡，需要進(jìn)行旋轉(zhuǎn)操作。

-旋轉(zhuǎn)的具體類型（左旋、右旋、左-右旋、右-左旋）取決于失衡節(jié)點(diǎn)的父節(jié)點(diǎn)的平衡因子以及失衡節(jié)點(diǎn)的位置（是父節(jié)點(diǎn)的左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)）。例如，如果失衡節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)且平衡因子為-2，則檢查其父節(jié)點(diǎn)的右子節(jié)點(diǎn)的平衡因子，決定是直接左旋還是先右旋再左旋。

-旋轉(zhuǎn)操作后，需要再次檢查旋轉(zhuǎn)點(diǎn)及其父節(jié)點(diǎn)的平衡因子，確保平衡被修復(fù)，并且可能需要繼續(xù)向上檢查。

4.（可選）更新顏色（紅黑樹特性）：標(biāo)準(zhǔn)AVL樹不涉及顏色。但如果是AVL紅黑樹，在旋轉(zhuǎn)和插入過程中，還需要進(jìn)行相應(yīng)的顏色調(diào)整，以保持紅黑樹的特性。例如，在進(jìn)行旋轉(zhuǎn)時，可能需要將某些節(jié)點(diǎn)從紅色變?yōu)楹谏蛘叻粗?，同時確保沒有紅色節(jié)點(diǎn)有紅色子節(jié)點(diǎn)，以及從任一節(jié)點(diǎn)到葉節(jié)點(diǎn)的所有簡單路徑上黑色節(jié)點(diǎn)數(shù)相同。

（三）刪除操作

1.普通BST刪除：首先按照BST的規(guī)則查找并刪除目標(biāo)節(jié)點(diǎn)。BST的刪除有三種情況：

-被刪除節(jié)點(diǎn)是葉節(jié)點(diǎn)：直接刪除該節(jié)點(diǎn)，其父節(jié)點(diǎn)相應(yīng)地斷開對該節(jié)點(diǎn)的引用。

-被刪除節(jié)點(diǎn)只有一個子節(jié)點(diǎn)：刪除該節(jié)點(diǎn)，將其子節(jié)點(diǎn)替換到該節(jié)點(diǎn)的位置。

-被刪除節(jié)點(diǎn)有兩個子節(jié)點(diǎn)：通常找到其中序后繼（右子樹中最小的節(jié)點(diǎn)）或中序前驅(qū)（左子樹中最大的節(jié)點(diǎn)），用其替換被刪除節(jié)點(diǎn)的鍵值和（或）數(shù)據(jù)，然后刪除那個后繼（或前驅(qū)）節(jié)點(diǎn)（它變成了葉節(jié)點(diǎn)或只有一個子節(jié)點(diǎn)的情況）。

2.更新高度：刪除節(jié)點(diǎn)后，從刪除點(diǎn)所在的節(jié)點(diǎn)開始，向上遍歷至根節(jié)點(diǎn)，更新沿途經(jīng)過的所有節(jié)點(diǎn)的`height`字段。與插入操作類似，這是一個從上向下的過程（或者說是從被刪除節(jié)點(diǎn)的父節(jié)點(diǎn)向上）。

-具體步驟：假設(shè)在刪除節(jié)點(diǎn)后，需要更新節(jié)點(diǎn)`p`及其祖先節(jié)點(diǎn)`q`的高度。如果刪除發(fā)生在`p`的子樹中，那么`p`的子樹高度會發(fā)生變化。這會導(dǎo)致`p`的高度`height(p)=max(height(p.left),height(p.right))+1`可能改變。如果`p`的高度改變了，那么它的父節(jié)點(diǎn)`q`的`height(q)`也可能需要更新，依此類推，直到根節(jié)點(diǎn)。

3.檢查平衡因子并旋轉(zhuǎn)：在更新完高度后，從刪除點(diǎn)所在的節(jié)點(diǎn)開始，向上遍歷至根節(jié)點(diǎn)，依次檢查每個節(jié)點(diǎn)的平衡因子`balance(node)=height(node.left)-height(node.right)`。

-如果遇到某個節(jié)點(diǎn)的平衡因子絕對值大于1，則表示該節(jié)點(diǎn)失衡，需要進(jìn)行旋轉(zhuǎn)操作。旋轉(zhuǎn)的類型和方向取決于失衡節(jié)點(diǎn)及其父節(jié)點(diǎn)的平衡關(guān)系。

-旋轉(zhuǎn)后，可能需要繼續(xù)向上檢查。

4.（可選）更新顏色（紅黑樹特性）：同樣，標(biāo)準(zhǔn)AVL樹不涉及顏色。在AVL紅黑樹中，刪除操作后的顏色調(diào)整更為復(fù)雜，可能涉及多種情況：刪除操作可能改變黑色高度路徑，需要通過旋轉(zhuǎn)和重新著色來恢復(fù)。例如，可能會出現(xiàn)“雙黑”問題（一個節(jié)點(diǎn)有兩個黑色子節(jié)點(diǎn)，導(dǎo)致其子節(jié)點(diǎn)的子樹黑色高度比預(yù)期少），需要通過“顏色翻轉(zhuǎn)”或“旋轉(zhuǎn)”來修復(fù)。

五、紅黑樹優(yōu)化

紅黑樹是由Bertzelmann、Guibas、Symons和Turner等人獨(dú)立提出，并在1978年由RudolfBayer和RobertMcGeoch重新發(fā)現(xiàn)的一種更實用的自平衡二叉搜索樹。紅黑樹通過引入節(jié)點(diǎn)的顏色屬性（紅色或黑色）以及一系列嚴(yán)格的規(guī)則，來保證樹的高度始終為O(logn)，同時插入和刪除操作的平攤時間復(fù)雜度也是O(logn)。相較于AVL樹，紅黑樹的旋轉(zhuǎn)次數(shù)通常更少，但在最壞情況下會稍多一些。

（一）紅黑樹規(guī)則

紅黑樹的節(jié)點(diǎn)除了鍵值、左右子節(jié)點(diǎn)指針外，還包含一個顏色屬性（通常是紅色或黑色）。紅黑樹的特性由以下七條公理（或稱為規(guī)則）定義：

1.每個節(jié)點(diǎn)要么是紅色，要么是黑色。

-這是最基本的定義，每個節(jié)點(diǎn)必須被著色為這兩種顏色之一。

2.根節(jié)點(diǎn)是黑色。

-這是紅黑樹結(jié)構(gòu)的一個關(guān)鍵特征，它保證了從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的任何路徑上不可能出現(xiàn)連續(xù)的紅色節(jié)點(diǎn)。這個規(guī)則對于維護(hù)路徑上的黑高計數(shù)至關(guān)重要。

3.每個葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)或空節(jié)點(diǎn)）是黑色。

-為了保持一致性，空子節(jié)點(diǎn)在邏輯上被看作是黑色葉子節(jié)點(diǎn)。這確保了從任何節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑上，黑色節(jié)點(diǎn)的數(shù)量是相同的。

4.如果一個節(jié)點(diǎn)是紅色的，則它的兩個子節(jié)點(diǎn)都是黑色的。

-這條規(guī)則禁止連續(xù)的紅色節(jié)點(diǎn)，從而保證了從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的任何路徑上，紅色節(jié)點(diǎn)的數(shù)量最多是黑色節(jié)點(diǎn)的數(shù)量的一半。這是紅黑樹高度受限的關(guān)鍵。

5.從任一節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡單路徑上，均包含相同數(shù)目的黑色節(jié)點(diǎn)。

-這是紅黑樹最核心的規(guī)則之一，稱為“黑高”規(guī)則。從根節(jié)點(diǎn)到任何葉子節(jié)點(diǎn)的路徑上，黑色節(jié)點(diǎn)的數(shù)量（稱為“黑高”）必須相等。這條規(guī)則直接導(dǎo)致了紅黑樹的高度上限。具體來說，如果一棵紅黑樹的黑高為`h`，那么其任意節(jié)點(diǎn)的高度最多為`2h-1`。由于樹的高度`H`滿足`H<=2h`，因此`H<=2(黑高)`，保證了O(logn)的高度。

6.紅黑樹的插入和刪除操作必須通過旋轉(zhuǎn)和重新著色來維護(hù)這些性質(zhì)。

-這條規(guī)則強(qiáng)調(diào)了紅黑樹的自我平衡機(jī)制。當(dāng)插入或刪除操作破壞了上述任何一條規(guī)則時，必須通過一系列的局部調(diào)整（旋轉(zhuǎn)和著色）來恢復(fù)所有規(guī)則。

7.紅黑樹是近似平衡的。

-紅黑樹不保證像AVL樹那樣嚴(yán)格的平衡（即所有節(jié)點(diǎn)的平衡因子都是-1、0或1），但它通過紅黑規(guī)則保證了樹的高度是O(logn)，從而提供了高效的性能。實際上，紅黑樹的高度更接近于`2log_2(n+1)`。

（二）旋轉(zhuǎn)與著色操作

紅黑樹的旋轉(zhuǎn)操作與AVL樹類似，也分為左旋、右旋、左-右旋和右-左旋。但在紅黑樹中，旋轉(zhuǎn)的目的不僅僅是調(diào)整樹的高度，更重要的是通過改變節(jié)點(diǎn)的連接方式和重新著色節(jié)點(diǎn)，來修復(fù)因插入或刪除操作而破壞的紅黑規(guī)則（尤其是規(guī)則4和規(guī)則5）。著色操作是紅黑樹區(qū)別于AVL樹的關(guān)鍵特性。

1.旋轉(zhuǎn)操作（RedandBlack）：

-紅黑樹的旋轉(zhuǎn)操作與AVL樹的旋轉(zhuǎn)操作在物理連接方式上是完全相同的（改變指針指向）。例如，左旋只是將一個節(jié)點(diǎn)的左子節(jié)點(diǎn)提升為父節(jié)點(diǎn)，父節(jié)點(diǎn)掛在其右側(cè)。旋轉(zhuǎn)本身不會改變節(jié)點(diǎn)的顏色。

-但是，旋轉(zhuǎn)后必須檢查并可能調(diào)整節(jié)點(diǎn)的顏色，以確保旋轉(zhuǎn)后的樹仍然滿足紅黑規(guī)則。例如，在進(jìn)行左旋或右旋后，原本是紅色的節(jié)點(diǎn)可能變成黑色，其子節(jié)點(diǎn)可能需要從黑色變?yōu)榧t色。

2.著色操作（Colorflips）：

-著色操作是指將一個節(jié)點(diǎn)的顏色從紅色變?yōu)楹谏?，或者從黑色變?yōu)榧t色。這是紅黑樹平衡的核心機(jī)制之一。通常在旋轉(zhuǎn)操作之后進(jìn)行。

-例如，在處理插入操作導(dǎo)致的不平衡時，可能會遇到以下情況：某個紅色節(jié)點(diǎn)有兩個紅色的子節(jié)點(diǎn)。為了修復(fù)規(guī)則4（紅色節(jié)點(diǎn)的子節(jié)點(diǎn)必須是黑色），需要將這兩個子節(jié)點(diǎn)變?yōu)楹谏?，而將父?jié)點(diǎn)變?yōu)榧t色。如果父節(jié)點(diǎn)已經(jīng)是黑色，可能需要更高層的操作。

-著色操作的具體策略取決于當(dāng)前的具體情況（不平衡節(jié)點(diǎn)的位置、其父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的顏色等）。常見的著色調(diào)整包括：

-將一個紅色節(jié)點(diǎn)變?yōu)楹谏ㄍǔＪ菫榱诵迯?fù)連續(xù)紅色）。

-將兩個或三個連續(xù)的紅色節(jié)點(diǎn)變?yōu)楹谏?，同時將它們的共同父節(jié)點(diǎn)變?yōu)榧t色。

-通過一系列的旋轉(zhuǎn)和著色組合，將不平衡傳播到更高的層級，或者局部修復(fù)問題。

3.典型插入修復(fù)步驟（概述）：

-插入節(jié)點(diǎn)，默認(rèn)為紅色。

-從插入點(diǎn)向上遍歷，檢查路徑上的節(jié)點(diǎn)是否滿足紅黑規(guī)則。

-一旦發(fā)現(xiàn)規(guī)則被破壞（通常是因為出現(xiàn)兩個連續(xù)的紅色節(jié)點(diǎn)），進(jìn)行局部修復(fù)。

-修復(fù)通常涉及：

(1)對某個節(jié)點(diǎn)執(zhí)行旋轉(zhuǎn)（左旋或右旋）。

(2)對旋轉(zhuǎn)點(diǎn)及其相關(guān)節(jié)點(diǎn)執(zhí)行著色操作（例如，將一個節(jié)點(diǎn)變黑，另一個節(jié)點(diǎn)變紅）。

-如果修復(fù)將問題傳播到更高的層級，需要繼續(xù)向上檢查和修復(fù)，直到根節(jié)點(diǎn)或問題被解決。

-整個過程保證在O(logn)時間內(nèi)完成，并且最終樹滿足所有紅黑規(guī)則。

六、應(yīng)用場景

平衡二叉搜索樹（包括AVL樹和紅黑樹）因其高效的操作性能，在許多需要有序數(shù)據(jù)集合的場景中得到廣泛應(yīng)用：

-數(shù)據(jù)庫索引：許多關(guān)系型數(shù)據(jù)庫管理系統(tǒng)（RDBMS）使用B樹或B+樹的變體作為索引結(jié)構(gòu)，這些結(jié)構(gòu)的核心思想與AVL樹或紅黑樹相似，能夠高效地支持?jǐn)?shù)據(jù)的快速查找、插入和刪除。B+樹通常在葉節(jié)點(diǎn)存儲數(shù)據(jù)或指向數(shù)據(jù)的指針，而內(nèi)部節(jié)點(diǎn)存儲鍵值作為分隔值，這使得范圍查詢非常高效。

-符號表：在編譯器中，符號表用于存儲變量名、函數(shù)名等標(biāo)識符及其屬性。平衡二叉搜索樹可以提供快速的鍵值查找、插入和刪除，適用于需要維護(hù)有序集合的場景。

-集合與映射實現(xiàn)：一些編程語言的標(biāo)準(zhǔn)庫使用紅黑樹或AVL樹實現(xiàn)`Set`（集合）和`Map`（映射）接口，例如Java的`TreeSet`和`TreeMap`，C++的`std::set`和`std::map`。這些數(shù)據(jù)結(jié)構(gòu)提供了對元素進(jìn)行有序存儲和快速檢索的能力。

-文件系統(tǒng)索引：在某些文件系統(tǒng)中，用于快速定位文件或目錄的索引可能采用平衡二叉搜索樹結(jié)構(gòu)。

-圖形學(xué)中的空間劃分：如八叉樹（3D版本的二叉搜索樹）可用于表示三維空間，進(jìn)行碰撞檢測或空間查詢。

七、總結(jié)

二叉搜索樹的平衡是保證其操作效率的關(guān)鍵。不平衡的BST會退化為鏈表，導(dǎo)致查找、插入、刪除操作的時間復(fù)雜度降為O(n)。通過引入旋轉(zhuǎn)操作（左旋、右旋、左-右旋、右-左旋）和著色操作（在紅黑樹中），可以動態(tài)調(diào)整樹的結(jié)構(gòu)和節(jié)點(diǎn)的顏色，確保樹在任何時候都保持近似平衡的狀態(tài)。AVL樹通過嚴(yán)格的平衡因子限制（-1,0,1）和旋轉(zhuǎn)操作來維持平衡，保證了O(logn)的高度。紅黑樹則通過引入顏色屬性和七條規(guī)則，以更靈活的方式實現(xiàn)平衡，旋轉(zhuǎn)次數(shù)通常少于AVL樹，同樣保證O(logn)的高度。這兩種結(jié)構(gòu)在數(shù)據(jù)庫索引、符號表、集合映射等眾多領(lǐng)域發(fā)揮著重要作用，為有序數(shù)據(jù)的高效管理提供了強(qiáng)大的工具。理解并掌握這些平衡技巧，對于設(shè)計和實現(xiàn)高性能的數(shù)據(jù)結(jié)構(gòu)至關(guān)重要。

一、概述

二叉搜索樹（BinarySearchTree,BST）是一種基于鍵值有序存儲的樹形數(shù)據(jù)結(jié)構(gòu)，其核心特性包括：左子樹所有節(jié)點(diǎn)的鍵值小于根節(jié)點(diǎn)，右子樹所有節(jié)點(diǎn)的鍵值大于根節(jié)點(diǎn)。然而，在非均勻插入或刪除操作下，BST可能退化為鏈表，導(dǎo)致查找、插入、刪除等操作的時間復(fù)雜度降至O(n)。為維持樹的高效性能，需采用平衡技巧，確保樹的高度始終保持在O(logn)級別。本文將介紹二叉搜索樹的平衡技巧，包括旋轉(zhuǎn)操作、AVL樹和紅黑樹的基本原理與實現(xiàn)。

二、二叉搜索樹的平衡問題

（一）不平衡的原因

1.插入操作導(dǎo)致右重左輕

-當(dāng)新節(jié)點(diǎn)持續(xù)插入某一側(cè)時，樹會向該側(cè)傾斜，破壞平衡性。

2.刪除操作導(dǎo)致左重右輕

-刪除節(jié)點(diǎn)可能導(dǎo)致另一側(cè)過度增長，引發(fā)不平衡。

（二）平衡的定義

-樹的任意節(jié)點(diǎn)的左右子樹高度差不超過1，即平衡因子（BalanceFactor）∈{-1,0,1}。

三、旋轉(zhuǎn)操作實現(xiàn)平衡

旋轉(zhuǎn)是調(diào)整樹平衡的基本手段，分為四種情況：左旋、右旋、左-右旋、右-左旋。

（一）左旋（LeftRotation）

1.適用場景：右重左輕（平衡因子為-2）。

2.操作步驟：

(1)將原根節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)為新的根節(jié)點(diǎn)。

(2)原根節(jié)點(diǎn)成為新根節(jié)點(diǎn)的左子節(jié)點(diǎn)。

(3)若原右子節(jié)點(diǎn)存在左子樹，將其掛載至原根節(jié)點(diǎn)的右子節(jié)點(diǎn)。

（二）右旋（RightRotation）

1.適用場景：左重右輕（平衡因子為2）。

2.操作步驟：

(1)將原根節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)為新的根節(jié)點(diǎn)。

(2)原根節(jié)點(diǎn)成為新根節(jié)點(diǎn)的右子節(jié)點(diǎn)。

(3)若原左子節(jié)點(diǎn)存在右子樹，將其掛載至原根節(jié)點(diǎn)的左子節(jié)點(diǎn)。

（三）左-右旋（Left-RightRotation）

1.適用場景：左重且左子樹右重（平衡因子為-2且左子節(jié)點(diǎn)平衡因子為2）。

2.操作步驟：

(1)對左子節(jié)點(diǎn)執(zhí)行左旋。

(2)對原根節(jié)點(diǎn)執(zhí)行右旋。

（四）右-左旋（Right-LeftRotation）

1.適用場景：右重且右子樹左重（平衡因子為2且右子節(jié)點(diǎn)平衡因子為-2）。

2.操作步驟：

(1)對右子節(jié)點(diǎn)執(zhí)行右旋。

(2)對原根節(jié)點(diǎn)執(zhí)行左旋。

四、AVL樹的實現(xiàn)

AVL樹是最早的平衡二叉搜索樹，通過旋轉(zhuǎn)操作維持平衡。

（一）節(jié)點(diǎn)結(jié)構(gòu)

-每個節(jié)點(diǎn)包含：鍵值、左右子節(jié)點(diǎn)指針、高度屬性。

（二）插入操作

1.普通BST插入節(jié)點(diǎn)。

2.更新節(jié)點(diǎn)高度：height(node)=max(height(left),height(right))+1。

3.計算平衡因子：balance(node)=height(left)-height(right)。

4.根據(jù)平衡因子執(zhí)行旋轉(zhuǎn)操作。

（三）刪除操作

1.普通BST刪除節(jié)點(diǎn)。

2.更新高度與平衡因子。

3.若不平衡，執(zhí)行相應(yīng)的旋轉(zhuǎn)操作。

五、紅黑樹優(yōu)化

紅黑樹是更實用的平衡樹，通過顏色屬性（紅/黑）和規(guī)則限制平衡。

（一）紅黑樹規(guī)則

1.每個節(jié)點(diǎn)為紅或黑。

2.根節(jié)點(diǎn)為黑。

3.紅節(jié)點(diǎn)的子節(jié)點(diǎn)必為黑（無連續(xù)紅節(jié)點(diǎn)）。

4.從任一節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡單路徑上黑節(jié)點(diǎn)數(shù)相同。

（二）旋轉(zhuǎn)與著色操作

1.插入時將節(jié)點(diǎn)設(shè)為紅色。

2.若違反規(guī)則，通過旋轉(zhuǎn)（左旋/右旋）和著色（紅變黑/黑變紅）修復(fù)。

3.常見修復(fù)步驟：

(1)祖父節(jié)點(diǎn)為紅、父節(jié)點(diǎn)為紅：將父節(jié)點(diǎn)變黑，祖父變紅，可能需遞歸修復(fù)。

(2)其他情況通過旋轉(zhuǎn)調(diào)整路徑顏色。

六、應(yīng)用場景

-索引數(shù)據(jù)庫（如B+樹基于AVL原理）。

-基于樹的符號表。

-高效查找與動態(tài)集合操作。

七、總結(jié)

一、概述

二叉搜索樹（BinarySearchTree,BST）是一種基于鍵值有序存儲的樹形數(shù)據(jù)結(jié)構(gòu)，其核心特性包括：左子樹所有節(jié)點(diǎn)的鍵值小于根節(jié)點(diǎn)，右子樹所有節(jié)點(diǎn)的鍵值大于根節(jié)點(diǎn)。然而，在非均勻插入或刪除操作下，BST可能退化為鏈表，導(dǎo)致查找、插入、刪除等操作的時間復(fù)雜度降至O(n)。這不僅降低了數(shù)據(jù)結(jié)構(gòu)的效率，也使得其優(yōu)勢無法發(fā)揮。為了維持樹的高效性能，確保查找、插入、刪除等操作的時間復(fù)雜度穩(wěn)定在O(logn)，必須采用平衡技巧。平衡技巧的核心目標(biāo)是通過一系列的調(diào)整操作，確保樹在任意狀態(tài)下都盡可能接近完全平衡，從而保持其高度為O(logn)。本文將詳細(xì)介紹二叉搜索樹的平衡問題，深入解析旋轉(zhuǎn)操作的具體實現(xiàn)，并闡述AVL樹和紅黑樹這兩種經(jīng)典的平衡二叉搜索樹（BalancedBinarySearchTree）的設(shè)計原理、操作方法及其應(yīng)用場景。

二、二叉搜索樹的平衡問題

（一）不平衡的原因

1.插入操作導(dǎo)致右重左輕：當(dāng)新節(jié)點(diǎn)的鍵值持續(xù)大于某個節(jié)點(diǎn)的鍵值，并且這些插入操作都發(fā)生在該節(jié)點(diǎn)的右子樹時，樹會向左傾斜，右側(cè)的深度遠(yuǎn)大于左側(cè)，導(dǎo)致整個樹的平衡被破壞。同樣，若新節(jié)點(diǎn)持續(xù)插入在左子樹，則樹會向右傾斜。這種不均衡會顯著增加樹的高度，從而影響操作效率。

-具體示例：假設(shè)我們依次插入鍵值[10,20,30,40,50]，這些鍵值都大于前一個，樹會迅速變成一條右斜鏈。

2.刪除操作導(dǎo)致左重右輕：刪除節(jié)點(diǎn)的過程可能導(dǎo)致另一側(cè)子樹過快增長，從而引發(fā)不平衡。特別是當(dāng)刪除操作導(dǎo)致某個節(jié)點(diǎn)的替代者是來自其右側(cè)或左側(cè)較深子樹時，更容易引發(fā)不平衡。

-具體示例：假設(shè)我們從傾斜的右重樹中刪除一個節(jié)點(diǎn)，如果其替代者是來自左子樹，可能導(dǎo)致原本較淺的左子樹突然變得非常深。

（二）平衡的定義

-平衡二叉搜索樹要求樹中任意節(jié)點(diǎn)的左右子樹的高度差（稱為平衡因子，BalanceFactor）必須嚴(yán)格小于或等于1。即對于樹中的任意節(jié)點(diǎn)node，滿足`|height(left_subtree(node))-height(right_subtree(node))|<=1`。這個條件保證了從根節(jié)點(diǎn)到任何葉節(jié)點(diǎn)的最長路徑長度（樹的高度）不會超過最短路徑長度的兩倍，從而確保了操作的時間復(fù)雜度為O(logn)。

-高度（Height）的定義：樹的高度是指從根節(jié)點(diǎn)到最遠(yuǎn)葉節(jié)點(diǎn)的最長路徑上的邊數(shù)?？諛涞母叨葹?1，單節(jié)點(diǎn)樹的高度為0。

三、旋轉(zhuǎn)操作實現(xiàn)平衡

旋轉(zhuǎn)是調(diào)整樹平衡最基本、最常用的操作。通過局部地改變節(jié)點(diǎn)的連接方式，可以重新分配樹中節(jié)點(diǎn)的分布，從而修復(fù)不平衡。旋轉(zhuǎn)操作主要分為四種：左旋（LeftRotation）、右旋（RightRotation）、左-右旋（Left-RightRotation，也稱為LR旋轉(zhuǎn)）、右-左旋（Right-LeftRotation，也稱為RL旋轉(zhuǎn)）。這些旋轉(zhuǎn)操作通常在插入或刪除操作后，根據(jù)節(jié)點(diǎn)的平衡因子來判斷是否需要進(jìn)行以及執(zhí)行哪種旋轉(zhuǎn)。

（一）左旋（LeftRotation）

1.適用場景：當(dāng)某個節(jié)點(diǎn)的平衡因子為-2時，表示其右子樹比左子樹高至少兩層，且不平衡發(fā)生在左子樹的右側(cè)（即右子樹的右子樹更高或右子樹本身就是紅色且右子樹右子樹是紅色，在紅黑樹中更常見）。此時需要進(jìn)行左旋，以提升左子樹的高度，降低右子樹的高度，從而恢復(fù)平衡。左旋針對的是“右重左輕”的情況。

2.操作步驟：

-定位失衡節(jié)點(diǎn)：假設(shè)節(jié)點(diǎn)`y`是失衡的節(jié)點(diǎn)，且`y`的平衡因子為-2。根據(jù)BST性質(zhì)，`y`一定有一個右子節(jié)點(diǎn)`x`。同時，`x`也一定有一個左子節(jié)點(diǎn)`T2`（否則`y`的平衡因子不會是-2）。這里的`T1`、`T2`等表示子樹，是為了描述旋轉(zhuǎn)而引入的符號，其中`T2`是`x`的左子樹。

-執(zhí)行旋轉(zhuǎn)：以`x`為新的根節(jié)點(diǎn)，進(jìn)行旋轉(zhuǎn)。具體來說，將原根節(jié)點(diǎn)`y`連接到`x`的左子節(jié)點(diǎn)`T2`；將`x`連接到原根節(jié)點(diǎn)`y`。即：

-`y`的右子節(jié)點(diǎn)變?yōu)閌x`的左子節(jié)點(diǎn)。

-`x`的左子節(jié)點(diǎn)變?yōu)閌y`的右子節(jié)點(diǎn)。

-`y`成為`x`的父節(jié)點(diǎn)。

-更新父節(jié)點(diǎn)和根節(jié)點(diǎn)：旋轉(zhuǎn)后，`y`的父節(jié)點(diǎn)（如果存在）現(xiàn)在指向`x`。如果`y`是原來的根節(jié)點(diǎn)，那么`x`成為新的根節(jié)點(diǎn)。

-（AVL樹特有）更新高度：旋轉(zhuǎn)后，需要更新受影響的節(jié)點(diǎn)的高度。通常，`y`的高度和`x`的高度都需要重新計算，因為它們的子樹發(fā)生了變化。具體更新規(guī)則依賴于高度的定義（例如，高度是子樹高度的最大值加1）。

-（AVL樹/紅黑樹特有）更新顏色：在AVL樹中，可能需要調(diào)整節(jié)點(diǎn)的黑色高度。在紅黑樹中，左旋通常發(fā)生在父節(jié)點(diǎn)是紅色、子節(jié)點(diǎn)是紅色的場景，左旋后可能需要重新著色（例如，將`x`著為黑色，`y`著為紅色）以修復(fù)紅黑樹的規(guī)則。

3.示例圖示（文字描述）：假設(shè)節(jié)點(diǎn)結(jié)構(gòu)為`node(left,key,right)`，左旋操作可以表示為：將`right`子節(jié)點(diǎn)提升為新的父節(jié)點(diǎn)，原父節(jié)點(diǎn)掛在提升節(jié)點(diǎn)的左側(cè)。具體代碼實現(xiàn)會涉及指針的重新指向。

（二）右旋（RightRotation）

1.適用場景：當(dāng)某個節(jié)點(diǎn)的平衡因子為2時，表示其左子樹比右子樹高至少兩層，且不平衡發(fā)生在左子樹的左側(cè)（即左子樹的左子樹更高或左子樹本身就是紅色且左子樹左子樹是紅色，在紅黑樹中更常見）。此時需要進(jìn)行右旋，以提升右子樹的高度，降低左子樹的高度，從而恢復(fù)平衡。右旋針對的是“左重右輕”的情況。

2.操作步驟：

-定位失衡節(jié)點(diǎn)：假設(shè)節(jié)點(diǎn)`y`是失衡的節(jié)點(diǎn)，且`y`的平衡因子為2。根據(jù)BST性質(zhì)，`y`一定有一個左子節(jié)點(diǎn)`x`。同時，`x`也一定有一個右子節(jié)點(diǎn)`T2`（否則`y`的平衡因子不會是2）。這里的`T1`、`T2`等表示子樹，`T2`是`x`的右子樹。

-執(zhí)行旋轉(zhuǎn)：以`x`為新的根節(jié)點(diǎn)，進(jìn)行旋轉(zhuǎn)。具體來說，將原根節(jié)點(diǎn)`y`連接到`x`的右子節(jié)點(diǎn)`T2`；將`x`連接到原根節(jié)點(diǎn)`y`。即：

-`y`的左子節(jié)點(diǎn)變?yōu)閌x`的右子節(jié)點(diǎn)。

-`x`的右子節(jié)點(diǎn)變?yōu)閌y`的左子節(jié)點(diǎn)。

-`y`成為`x`的父節(jié)點(diǎn)。

-更新父節(jié)點(diǎn)和根節(jié)點(diǎn)：旋轉(zhuǎn)后，`y`的父節(jié)點(diǎn)（如果存在）現(xiàn)在指向`x`。如果`y`是原來的根節(jié)點(diǎn)，那么`x`成為新的根節(jié)點(diǎn)。

-（AVL樹特有）更新高度：旋轉(zhuǎn)后，需要更新受影響的節(jié)點(diǎn)的高度。通常，`y`的高度和`x`的高度都需要重新計算。

-（AVL樹/紅黑樹特有）更新顏色：在AVL樹中，可能需要調(diào)整節(jié)點(diǎn)的黑色高度。在紅黑樹中，右旋通常發(fā)生在父節(jié)點(diǎn)是紅色、子節(jié)點(diǎn)是紅色的場景，右旋后可能需要重新著色（例如，將`x`著為黑色，`y`著為紅色）以修復(fù)紅黑樹的規(guī)則。

3.示例圖示（文字描述）：假設(shè)節(jié)點(diǎn)結(jié)構(gòu)為`node(left,key,right)`，右旋操作可以表示為：將`left`子節(jié)點(diǎn)提升為新的父節(jié)點(diǎn)，原父節(jié)點(diǎn)掛在提升節(jié)點(diǎn)的右側(cè)。具體代碼實現(xiàn)會涉及指針的重新指向。

（三）左-右旋（Left-RightRotation，LR旋轉(zhuǎn)）

1.適用場景：這種旋轉(zhuǎn)發(fā)生在節(jié)點(diǎn)`y`的平衡因子為-2，但其右子節(jié)點(diǎn)`x`的平衡因子為2的情況。這意味著不平衡同時發(fā)生在右子樹的右側(cè)（導(dǎo)致`y`右重）和右子樹的左側(cè)（導(dǎo)致`x`左重）。直接對`y`進(jìn)行左旋無法解決`x`的左重問題，因此需要先解決`x`的不平衡。

2.操作步驟：

(1)第一步：對右子節(jié)點(diǎn)`x`執(zhí)行左旋。

-這一步將`x`的左子節(jié)點(diǎn)提升到`x`的位置，同時將`x`變?yōu)樾碌母腹?jié)點(diǎn)（相對于`y`）。這一步操作修復(fù)了`x`的左重不平衡。

-具體左旋操作步驟同前所述，作用于節(jié)點(diǎn)`x`和其左子節(jié)點(diǎn)。

(2)第二步：對節(jié)點(diǎn)`y`執(zhí)行右旋。

-在第一步左旋之后，`y`的平衡因子可能變?yōu)?或仍然為-2（如果`x`的左子節(jié)點(diǎn)在第一步左旋中變成了`y`的右子節(jié)點(diǎn)，且它原本是紅色）。此時`y`仍然不平衡（右重），所以需要對其執(zhí)行右旋。

-具體右旋操作步驟同前所述，作用于節(jié)點(diǎn)`y`和其新的右子節(jié)點(diǎn)（即原`x`的右子節(jié)點(diǎn)`T3`）。

-顏色調(diào)整（AVL/紅黑樹特有）：在AVL樹中，可能需要同時更新高度。在紅黑樹中，這種旋轉(zhuǎn)通常發(fā)生在更復(fù)雜的著色場景，可能需要將原`y`和`x`的父節(jié)點(diǎn)、`x`本身、以及`x`的子節(jié)點(diǎn)進(jìn)行著色調(diào)整，以保持紅黑樹的規(guī)則。例如，可能需要將`x`著為黑色，原`y`和`x`的父節(jié)點(diǎn)著為紅色（如果它們原本是黑色），等等。

3.示例圖示（文字描述）：LR旋轉(zhuǎn)可以理解為先“矯正”右子樹的左重問題，再解決原樹的右重問題。先左旋右子節(jié)點(diǎn)，再右旋父節(jié)點(diǎn)。

（四）右-左旋（Right-LeftRotation，RL旋轉(zhuǎn)）

1.適用場景：這種旋轉(zhuǎn)發(fā)生在節(jié)點(diǎn)`y`的平衡因子為2，但其左子節(jié)點(diǎn)`x`的平衡因子為-2的情況。這意味著不平衡同時發(fā)生在左子樹的左側(cè)（導(dǎo)致`y`左重）和左子樹的右側(cè)（導(dǎo)致`x`右重）。

2.操作步驟：

(1)第一步：對左子節(jié)點(diǎn)`x`執(zhí)行右旋。

-這一步將`x`的右子節(jié)點(diǎn)提升到`x`的位置，同時將`x`變?yōu)樾碌母腹?jié)點(diǎn)（相對于`y`）。這一步操作修復(fù)了`x`的右重不平衡。

-具體右旋操作步驟同前所述，作用于節(jié)點(diǎn)`x`和其右子節(jié)點(diǎn)。

(2)第二步：對節(jié)點(diǎn)`y`執(zhí)行左旋。

-在第一步右旋之后，`y`的平衡因子可能變?yōu)?或仍然為2（如果`x`的右子節(jié)點(diǎn)在第一步右旋中變成了`y`的左子節(jié)點(diǎn)，且它原本是紅色）。此時`y`仍然不平衡（左重），所以需要對其執(zhí)行左旋。

-具體左旋操作步驟同前所述，作用于節(jié)點(diǎn)`y`和其新的左子節(jié)點(diǎn)（即原`x`的左子節(jié)點(diǎn)`T3`）。

-顏色調(diào)整（AVL/紅黑樹特有）：在AVL樹中，可能需要同時更新高度。在紅黑樹中，這種旋轉(zhuǎn)通常發(fā)生在更復(fù)雜的著色場景，可能需要將原`y`和`x`的父節(jié)點(diǎn)、`x`本身、以及`x`的子節(jié)點(diǎn)進(jìn)行著色調(diào)整，以保持紅黑樹的規(guī)則。例如，可能需要將`x`著為黑色，原`y`和`x`的父節(jié)點(diǎn)著為紅色（如果它們原本是黑色），等等。

3.示例圖示（文字描述）：RL旋轉(zhuǎn)可以理解為先“矯正”左子樹的右重問題，再解決原樹的左重問題。先右旋左子節(jié)點(diǎn)，再左旋父節(jié)點(diǎn)。

四、AVL樹的實現(xiàn)

AVL樹是第一個被發(fā)明的自平衡二叉搜索樹，由Adelson-Velsky和Landis于1962年提出。AVL樹通過強(qiáng)制要求樹中任何節(jié)點(diǎn)的左右子樹高度差不超過1（即平衡因子滿足`-1<=balance(node)<=1`），來保證樹的高度始終為O(logn)。

（一）節(jié)點(diǎn)結(jié)構(gòu)

-AVL樹的節(jié)點(diǎn)通常包含以下字段：

-`key`：存儲節(jié)點(diǎn)鍵值的字段。

-`left`：指向左子節(jié)點(diǎn)的指針。

-`right`：指向右子節(jié)點(diǎn)的指針。

-`height`：存儲該節(jié)點(diǎn)子樹高度的字段。

-（可選）`color`：在AVL樹中通常不使用顏色字段，除非是AVL紅黑混合樹，但標(biāo)準(zhǔn)AVL樹關(guān)注的是高度平衡。

-節(jié)點(diǎn)的高度計算方式通常為：`height(node)=max(height(node.left),height(node.right))+1`。如果節(jié)點(diǎn)是葉節(jié)點(diǎn)，其高度為0；如果節(jié)點(diǎn)是空節(jié)點(diǎn)，其高度為-1（這種定義方式使得樹的高度計算更簡潔）。

（二）插入操作

1.普通BST插入：首先按照BST的規(guī)則將節(jié)點(diǎn)插入到樹中。即，如果新節(jié)點(diǎn)的鍵值小于當(dāng)前節(jié)點(diǎn)的鍵值，則嘗試插入到左子樹；如果大于，則嘗試插入到右子樹；如果等于，則根據(jù)具體實現(xiàn)策略處理（例如，不插入、覆蓋、或者插入到左/右子樹）。

2.更新高度：插入新節(jié)點(diǎn)后，從插入點(diǎn)開始，向上遍歷至根節(jié)點(diǎn)，更新沿途經(jīng)過的所有節(jié)點(diǎn)的`height`字段。因為插入操作可能改變子樹的高度（例如，一個葉節(jié)點(diǎn)變成了一個內(nèi)部節(jié)點(diǎn)的子節(jié)點(diǎn)）。更新高度的過程是從底向上的。

-具體步驟：假設(shè)在插入新節(jié)點(diǎn)后，需要更新節(jié)點(diǎn)`p`及其祖先節(jié)點(diǎn)`q`的高度。如果插入發(fā)生在`p`的左子樹或右子樹，那么`p`的子樹高度會發(fā)生變化（或者`p`的某個子節(jié)點(diǎn)的高度從0變?yōu)?）。這會導(dǎo)致`p`的高度`height(p)=max(height(p.left),height(p.right))+1`可能改變。如果`p`的高度改變了，那么它的父節(jié)點(diǎn)`q`的`height(q)`也可能需要更新，依此類推，直到根節(jié)點(diǎn)。

3.檢查平衡因子并旋轉(zhuǎn)：在更新完高度后，從插入點(diǎn)所在的節(jié)點(diǎn)開始，向上遍歷至根節(jié)點(diǎn)，依次檢查每個節(jié)點(diǎn)的平衡因子`balance(node)=height(node.left)-height(node.right)`。

-如果遇到某個節(jié)點(diǎn)的平衡因子絕對值大于1（即`|balance(node)|>1`），則表示該節(jié)點(diǎn)失衡，需要進(jìn)行旋轉(zhuǎn)操作。

-旋轉(zhuǎn)的具體類型（左旋、右旋、左-右旋、右-左旋）取決于失衡節(jié)點(diǎn)的父節(jié)點(diǎn)的平衡因子以及失衡節(jié)點(diǎn)的位置（是父節(jié)點(diǎn)的左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)）。例如，如果失衡節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)且平衡因子為-2，則檢查其父節(jié)點(diǎn)的右子節(jié)點(diǎn)的平衡因子，決定是直接左旋還是先右旋再左旋。

-旋轉(zhuǎn)操作后，需要再次檢查旋轉(zhuǎn)點(diǎn)及其父節(jié)點(diǎn)的平衡因子，確保平衡被修復(fù)，并且可能需要繼續(xù)向上檢查。

4.（可選）更新顏色（紅黑樹特性）：標(biāo)準(zhǔn)AVL樹不涉及顏色。但如果是AVL紅黑樹，在旋轉(zhuǎn)和插入過程中，還需要進(jìn)行相應(yīng)的顏色調(diào)整，以保持紅黑樹的特性。例如，在進(jìn)行旋轉(zhuǎn)時，可能需要將某些節(jié)點(diǎn)從紅色變?yōu)楹谏?，或者反之，同時確保沒有紅色節(jié)點(diǎn)有紅色子節(jié)點(diǎn)，以及從任一節(jié)點(diǎn)到葉節(jié)點(diǎn)的所有簡單路徑上黑色節(jié)點(diǎn)數(shù)相同。

（三）刪除操作

1.普通BST刪除：首先按照BST的規(guī)則查找并刪除目標(biāo)節(jié)點(diǎn)。BST的刪除有三種情況：

-被刪除節(jié)點(diǎn)是葉節(jié)點(diǎn)：直接刪除該節(jié)點(diǎn)，其父節(jié)點(diǎn)相應(yīng)地斷開對該節(jié)點(diǎn)的引用。

-被刪除節(jié)點(diǎn)只有一個子節(jié)點(diǎn)：刪除該節(jié)點(diǎn)，將其子節(jié)點(diǎn)替換到該節(jié)點(diǎn)的位置。

-被刪除節(jié)點(diǎn)有兩個子節(jié)點(diǎn)：通常找到其中序后繼（右子樹中最小的節(jié)點(diǎn)）或中序前驅(qū)（左子樹中最大的節(jié)點(diǎn)），用其替換被刪除節(jié)點(diǎn)的鍵值和（或）數(shù)據(jù)，然后刪除那個后繼（或前驅(qū)）節(jié)點(diǎn)（它變成了葉節(jié)點(diǎn)或只有一個子節(jié)點(diǎn)的情況）。

2.更新高度：刪除節(jié)點(diǎn)后，從刪除點(diǎn)所在的節(jié)點(diǎn)開始，向上遍歷至根節(jié)點(diǎn)，更新沿途經(jīng)過的所有節(jié)點(diǎn)的`height`字段。與插入操作類似，這是一個從上向下的過程（或者說是從被刪除節(jié)點(diǎn)的父節(jié)點(diǎn)向上）。

-具體步驟：假設(shè)在刪除節(jié)點(diǎn)后，需要更新節(jié)點(diǎn)`p`及其祖先節(jié)點(diǎn)`q`的高度。如果刪除發(fā)生在`p`的子樹中，那么`p`的子樹高度會發(fā)生變化。這會導(dǎo)致`p`的高度`height(p)=max(height(p.left),height(p.right))+1`可能改變。如果`p`的高度改變了，那么它的父節(jié)點(diǎn)`q`的`height(q)`也可能需要更新，依此類推，直到根節(jié)點(diǎn)。

3.檢查平衡因子并旋轉(zhuǎn)：在更新完高度后，從刪除點(diǎn)所在的節(jié)點(diǎn)開始，向上遍歷至根節(jié)點(diǎn)，依次檢查每個節(jié)點(diǎn)的平衡因子`balance(node)=height(node.left)-height(node.right)`。

-如果遇到某個節(jié)點(diǎn)的平衡因子絕對值大于1，則表示該節(jié)點(diǎn)失衡，需要進(jìn)行旋轉(zhuǎn)操作。旋轉(zhuǎn)的類型和方向取決于失衡節(jié)點(diǎn)及其父節(jié)點(diǎn)的平衡關(guān)系。

-旋轉(zhuǎn)后，可能需要繼續(xù)向上檢查。

4.（可選）更新顏色（紅黑樹特性）：同樣，標(biāo)準(zhǔn)AVL樹不涉及顏色。在AVL紅黑樹中，刪除操作后的顏色調(diào)整更為復(fù)雜，可能涉及多種情況：刪除操作可能改變黑色高度路徑，需要通過旋轉(zhuǎn)和重新著色來恢復(fù)。例如，可能會出現(xiàn)“雙黑”問題（一個節(jié)點(diǎn)有兩個黑色子節(jié)點(diǎn)，導(dǎo)致其子節(jié)點(diǎn)的子樹黑色高度比預(yù)期少），需要通過“顏色翻轉(zhuǎn)”或“旋轉(zhuǎn)”來修復(fù)。

五、紅黑樹優(yōu)化

紅黑樹是由Bertzelmann、Guibas、Symons和Turner等人獨(dú)立提出，并在1978年由RudolfBayer和RobertMcGeoch重新發(fā)現(xiàn)的一種更實用的自平衡二叉搜索樹。紅黑樹通過引入節(jié)點(diǎn)的顏色屬性（紅色或黑色）以及一系列嚴(yán)格的規(guī)則，來保證樹的高度始終為O(logn)，同時插入和刪除操作的平攤時間復(fù)雜度也是O(logn)。相較于AVL樹，紅黑樹的旋轉(zhuǎn)次數(shù)通常更少，但在最壞情況下會稍多一些。

（一）紅黑樹規(guī)則

紅黑樹的節(jié)點(diǎn)除了鍵值、左右子節(jié)點(diǎn)指針外，還包含一個顏色屬性（通常是紅色或黑色）。紅黑樹的特性由以下七條公理（或稱為規(guī)則）定義：

1.每個節(jié)點(diǎn)要么是紅色，要么是黑色。

-這是最基本的定義，每個節(jié)點(diǎn)必須被著色為這兩種顏色之一。

2.根節(jié)點(diǎn)是黑色。

-這是紅黑樹結(jié)構(gòu)的一個關(guān)鍵特征，它保證了從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的任何路徑上不可能出現(xiàn)連續(xù)的紅色節(jié)點(diǎn)。這個規(guī)則對于維護(hù)路徑上的黑高計數(shù)至關(guān)重要。

3.每個葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)或空節(jié)點(diǎn)）是黑色。

-為了保持一致性，空子節(jié)點(diǎn)在邏輯上被看作是黑色葉子節(jié)點(diǎn)。這確保了從任何節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑上，黑色節(jié)點(diǎn)的數(shù)量是相同的。

4.如果一個節(jié)點(diǎn)是紅色的，則它的兩個子節(jié)點(diǎn)都是黑色的。

-這條規(guī)則禁止連續(xù)的紅色節(jié)點(diǎn)，從而保證了從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的任何路徑上，紅色節(jié)點(diǎn)的數(shù)量最多是黑色節(jié)點(diǎn)的數(shù)量的一半。這是紅黑樹高度受限的關(guān)鍵。

5.從任一節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡單路徑上