平衡二叉樹插入操作實(shí)施規(guī)程一、概述

平衡二叉樹（BalancedBinaryTree）是一種特殊的樹形結(jié)構(gòu)，通過自動(dòng)調(diào)整樹的高度來保持平衡，從而確保所有操作（如插入、刪除、查找）的時(shí)間復(fù)雜度保持在O(logn)級別。本文檔詳細(xì)闡述平衡二叉樹（以AVL樹為例）的插入操作實(shí)施規(guī)程，包括插入步驟、平衡調(diào)整方法及具體實(shí)現(xiàn)要點(diǎn)。

---

二、插入操作步驟

平衡二叉樹的插入操作與普通二叉搜索樹的插入操作類似，但在插入后需要檢查并維護(hù)樹的平衡性。以下是具體步驟：

（一）基本插入操作

1.將新節(jié)點(diǎn)按照二叉搜索樹的規(guī)則插入到樹中：

-若當(dāng)前節(jié)點(diǎn)為空，則新節(jié)點(diǎn)成為該位置的節(jié)點(diǎn)。

-若新節(jié)點(diǎn)值小于當(dāng)前節(jié)點(diǎn)值，則插入到左子樹；反之插入到右子樹。

-重復(fù)上述過程直到找到合適的插入位置。

（二）平衡性檢查與調(diào)整

1.插入節(jié)點(diǎn)后，從插入節(jié)點(diǎn)向上遍歷至根節(jié)點(diǎn)，計(jì)算每個(gè)節(jié)點(diǎn)的平衡因子（BalanceFactor=左子樹高度-右子樹高度）：

-平衡因子為0：節(jié)點(diǎn)平衡。

-平衡因子為±1：節(jié)點(diǎn)暫時(shí)平衡，繼續(xù)向上檢查。

-平衡因子為±2：樹不平衡，需要執(zhí)行旋轉(zhuǎn)操作。

2.根據(jù)不平衡節(jié)點(diǎn)的父節(jié)點(diǎn)及插入位置，確定旋轉(zhuǎn)類型：

-LL型：插入節(jié)點(diǎn)在左子樹的左子樹，執(zhí)行右旋（RightRotation）。

-RR型：插入節(jié)點(diǎn)在右子樹的右子樹，執(zhí)行左旋（LeftRotation）。

-LR型：插入節(jié)點(diǎn)在左子樹的右子樹，執(zhí)行左旋-右旋（Left-RightRotation）。

-RL型：插入節(jié)點(diǎn)在右子樹的左子樹，執(zhí)行右旋-左旋（Right-LeftRotation）。

---

三、旋轉(zhuǎn)操作實(shí)施規(guī)程

旋轉(zhuǎn)操作是維護(hù)平衡二叉樹的關(guān)鍵，以下是四種旋轉(zhuǎn)的具體實(shí)施方法：

（一）右旋（RightRotation）

1.適用于LL型不平衡（插入節(jié)點(diǎn)在左子樹的左子樹）：

-將原節(jié)點(diǎn)的左子節(jié)點(diǎn)提升為新的根節(jié)點(diǎn)。

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

-調(diào)整子節(jié)點(diǎn)的父指針及高度信息。

（二）左旋（LeftRotation）

1.適用于RR型不平衡（插入節(jié)點(diǎn)在右子樹的右子樹）：

-將原節(jié)點(diǎn)的右子節(jié)點(diǎn)提升為新的根節(jié)點(diǎn)。

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

-調(diào)整子節(jié)點(diǎn)的父指針及高度信息。

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

1.適用于LR型不平衡（插入節(jié)點(diǎn)在左子樹的右子樹）：

-先對左子樹執(zhí)行左旋，使插入節(jié)點(diǎn)移動(dòng)到右子樹的右子樹。

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

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

1.適用于RL型不平衡（插入節(jié)點(diǎn)在右子樹的左子樹）：

-先對右子樹執(zhí)行右旋，使插入節(jié)點(diǎn)移動(dòng)到左子樹的左子樹。

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

---

四、插入操作示例

（一）初始樹結(jié)構(gòu)

假設(shè)初始樹結(jié)構(gòu)如下（節(jié)點(diǎn)高度用括號標(biāo)注）：

10(2)

/\

5(1)20(1)

\

7(0)

（二）插入節(jié)點(diǎn)15

1.插入15到右子樹：

-15插入到節(jié)點(diǎn)20的左子樹。

-樹變?yōu)椋?/p>

```

10(2)

/\

5(1)20(1)

/\

15(0)7(0)

```

2.檢查平衡因子：

-節(jié)點(diǎn)20的平衡因子變?yōu)?2（不平衡）。

-插入節(jié)點(diǎn)15在右子樹的右子樹，屬于RR型。

3.執(zhí)行右旋：

-節(jié)點(diǎn)20成為新根，15成為其左子節(jié)點(diǎn)。

-最終樹結(jié)構(gòu)：

```

15(1)

/\

10(1)20(0)

/

5(0)

```

---

五、總結(jié)

平衡二叉樹的插入操作涉及以下關(guān)鍵點(diǎn)：

1.按照二叉搜索樹規(guī)則插入節(jié)點(diǎn)。

2.通過平衡因子檢測不平衡情況。

3.根據(jù)旋轉(zhuǎn)類型執(zhí)行相應(yīng)的旋轉(zhuǎn)操作。

4.維護(hù)樹的高度信息確保平衡性。

遵循上述規(guī)程可保證插入操作的效率及樹的平衡性，適用于需要?jiǎng)討B(tài)維護(hù)有序數(shù)據(jù)的場景。

---

一、概述

平衡二叉樹（BalancedBinaryTree）是一種特殊的樹形結(jié)構(gòu)，通過自動(dòng)調(diào)整樹的高度來保持平衡，從而確保所有操作（如插入、刪除、查找）的時(shí)間復(fù)雜度保持在O(logn)級別。本文檔詳細(xì)闡述平衡二叉樹（以AVL樹為例）的插入操作實(shí)施規(guī)程，包括插入步驟、平衡調(diào)整方法及具體實(shí)現(xiàn)要點(diǎn)。AVL樹是最早被發(fā)明的自平衡二叉搜索樹，其核心在于通過維護(hù)每個(gè)節(jié)點(diǎn)的平衡因子（BalanceFactor）來確保樹的高度差不超過1。本規(guī)程旨在提供一套系統(tǒng)化、可操作的插入流程，確保在向AVL樹中添加新節(jié)點(diǎn)時(shí)，樹的結(jié)構(gòu)和性能始終得到保障。

二、插入操作步驟

平衡二叉樹的插入操作與普通二叉搜索樹的插入操作類似，但在插入后需要檢查并維護(hù)樹的平衡性。以下是具體步驟：

（一）基本插入操作

1.定位插入位置：

-從根節(jié)點(diǎn)開始，按照二叉搜索樹的規(guī)則向下遍歷：

-若當(dāng)前節(jié)點(diǎn)為空，則新節(jié)點(diǎn)成為該位置的節(jié)點(diǎn)。

-若新節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)的值，則移動(dòng)到當(dāng)前節(jié)點(diǎn)的左子樹，重復(fù)此過程。

-若新節(jié)點(diǎn)的值大于當(dāng)前節(jié)點(diǎn)的值，則移動(dòng)到當(dāng)前節(jié)點(diǎn)的右子樹，重復(fù)此過程。

-這個(gè)過程直到找到一個(gè)空節(jié)點(diǎn)，新節(jié)點(diǎn)將被插入到該位置。

2.創(chuàng)建新節(jié)點(diǎn)并鏈接：

-分配內(nèi)存空間創(chuàng)建新節(jié)點(diǎn)，新節(jié)點(diǎn)的值設(shè)為待插入的值。

-新節(jié)點(diǎn)的初始子節(jié)點(diǎn)為空（null），初始高度（Height）通常設(shè)為0或1（根據(jù)定義）。

-將新節(jié)點(diǎn)鏈接到上一步驟中定位到的父節(jié)點(diǎn)：

-若新節(jié)點(diǎn)值小于父節(jié)點(diǎn)值，則將新節(jié)點(diǎn)設(shè)為父節(jié)點(diǎn)的左子節(jié)點(diǎn)。

-若新節(jié)點(diǎn)值大于父節(jié)點(diǎn)值，則將新節(jié)點(diǎn)設(shè)為父節(jié)點(diǎn)的右子節(jié)點(diǎn)。

（二）平衡性檢查與調(diào)整

1.自底向上更新高度：

-從新插入的節(jié)點(diǎn)開始，逐層向上遍歷至根節(jié)點(diǎn)，更新沿途經(jīng)過的所有節(jié)點(diǎn)的高度（Height）。

-節(jié)點(diǎn)的高度定義為：該節(jié)點(diǎn)的最大子樹高度加1（若子樹為空，高度為0）。

-高度更新的計(jì)算方式：對于任意節(jié)點(diǎn)`node`，其高度`Height(node)=max(Height(node.left),Height(node.right))+1`。

-此步驟確保每個(gè)節(jié)點(diǎn)的高度信息是最新的，為平衡性檢查提供基礎(chǔ)。

2.計(jì)算平衡因子：

-對于從新插入節(jié)點(diǎn)向上遍歷的每個(gè)節(jié)點(diǎn)`node`，計(jì)算其平衡因子（BalanceFactor）。

-平衡因子定義為：`BalanceFactor(node)=Height(node.left)-Height(node.right)`。

-平衡因子的可能值及其含義：

-0：節(jié)點(diǎn)平衡。

-1或-1：節(jié)點(diǎn)暫時(shí)平衡，繼續(xù)向上檢查。

-2或-2：節(jié)點(diǎn)不平衡，需要進(jìn)行旋轉(zhuǎn)操作。

-只有當(dāng)遇到平衡因子的絕對值大于1的節(jié)點(diǎn)時(shí)，才需要進(jìn)行平衡調(diào)整。

3.確定旋轉(zhuǎn)類型：

-一旦發(fā)現(xiàn)不平衡節(jié)點(diǎn)（平衡因子為±2），需要確定旋轉(zhuǎn)類型。旋轉(zhuǎn)類型取決于不平衡節(jié)點(diǎn)的父節(jié)點(diǎn)以及新插入節(jié)點(diǎn)在不平衡節(jié)點(diǎn)子樹中的位置。

-LL型（Left-LeftCase）：

-不平衡節(jié)點(diǎn)`u`的平衡因子為+2。

-且`u`的左子節(jié)點(diǎn)`v`的平衡因子為≥0（即`v`的左子樹高或等于右子樹高，或無子樹）。

-插入發(fā)生在`u`的左子樹的左子樹（`v`的左子樹或`v`本身）。

-RR型（Right-RightCase）：

-不平衡節(jié)點(diǎn)`u`的平衡因子為-2。

-且`u`的右子節(jié)點(diǎn)`v`的平衡因子為≤0（即`v`的右子樹高或等于左子樹高，或無子樹）。

-插入發(fā)生在`u`的右子樹的右子樹（`v`的右子樹或`v`本身）。

-LR型（Left-RightCase）：

-不平衡節(jié)點(diǎn)`u`的平衡因子為+2。

-且`u`的左子節(jié)點(diǎn)`v`的平衡因子為-1。

-插入發(fā)生在`u`的左子樹的右子樹（`v`的右子樹）。

-RL型（Right-LeftCase）：

-不平衡節(jié)點(diǎn)`u`的平衡因子為-2。

-且`u`的右子節(jié)點(diǎn)`v`的平衡因子為+1。

-插入發(fā)生在`u`的右子樹的左子樹（`v`的左子樹）。

三、旋轉(zhuǎn)操作實(shí)施規(guī)程

旋轉(zhuǎn)操作是維護(hù)平衡二叉樹的關(guān)鍵，以下是四種旋轉(zhuǎn)的具體實(shí)施方法：

（一）右旋（RightRotation）

1.適用場景：

-LL型不平衡（插入節(jié)點(diǎn)在左子樹的左子樹）。

-RR型不平衡（插入節(jié)點(diǎn)在右子樹的右子樹，但需先進(jìn)行左旋）。

2.操作步驟：

-選擇不平衡節(jié)點(diǎn)`u`（旋轉(zhuǎn)的支點(diǎn)）。

-將`u`的左子節(jié)點(diǎn)`v`提升為新的根節(jié)點(diǎn)。

-將原根節(jié)點(diǎn)`u`變?yōu)樾赂?jié)點(diǎn)`v`的右子節(jié)點(diǎn)。

-關(guān)鍵操作：原根節(jié)點(diǎn)`u`的右子樹（如果存在）需要連接到新根節(jié)點(diǎn)`v`的左子節(jié)點(diǎn)。

-具體連接方式：`v.left.right=u`。

-更新相關(guān)節(jié)點(diǎn)的父指針和高度信息。

-示例（LL型）：

-旋轉(zhuǎn)前：

```

u(2)

/

v(1)

/

x(0)

```

-旋轉(zhuǎn)后：

```

v(1)

/

u(1)

/

x(0)

```

3.高度更新：

-旋轉(zhuǎn)后，`u`和`v`的高度可能需要更新。通常，新根節(jié)點(diǎn)`v`的高度為`max(Height(u),Height(v.right))+1`（如果`v.right`存在）。

（二）左旋（LeftRotation）

1.適用場景：

-RR型不平衡（插入節(jié)點(diǎn)在右子樹的右子樹）。

-LR型不平衡（插入節(jié)點(diǎn)在左子樹的右子樹，但需先進(jìn)行右旋）。

2.操作步驟：

-選擇不平衡節(jié)點(diǎn)`u`（旋轉(zhuǎn)的支點(diǎn)）。

-將`u`的右子節(jié)點(diǎn)`v`提升為新的根節(jié)點(diǎn)。

-將原根節(jié)點(diǎn)`u`變?yōu)樾赂?jié)點(diǎn)`v`的左子節(jié)點(diǎn)。

-關(guān)鍵操作：原根節(jié)點(diǎn)`u`的左子樹（如果存在）需要連接到新根節(jié)點(diǎn)`v`的右子節(jié)點(diǎn)。

-具體連接方式：`v.right.left=u`。

-更新相關(guān)節(jié)點(diǎn)的父指針和高度信息。

-示例（RR型）：

-旋轉(zhuǎn)前：

```

u(2)

/

v(1)

/

x(0)

```

-旋轉(zhuǎn)后：

```

v(1)

/

u(1)

/

x(0)

```

3.高度更新：

-旋轉(zhuǎn)后，`u`和`v`的高度可能需要更新。通常，新根節(jié)點(diǎn)`v`的高度為`max(Height(v.left),Height(u))+1`。

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

1.適用場景：LR型不平衡（插入節(jié)點(diǎn)在左子樹的右子樹）。

2.操作步驟：

-左旋操作：首先對不平衡節(jié)點(diǎn)`u`的左子節(jié)點(diǎn)`v`執(zhí)行左旋。

-左旋`v`后，`v`成為其右子節(jié)點(diǎn)的父節(jié)點(diǎn)。

-`u`的平衡因子可能變?yōu)?1，而`v`的平衡因子變?yōu)?1或0。

-右旋操作：然后對不平衡節(jié)點(diǎn)`u`執(zhí)行右旋。

-右旋`u`后，`v`成為新的根節(jié)點(diǎn)。

-原根節(jié)點(diǎn)`u`成為`v`的右子節(jié)點(diǎn)。

3.詳細(xì)流程：

-初始不平衡節(jié)點(diǎn)：`u`（BalanceFactor=+2），其左子節(jié)點(diǎn)`v`（BalanceFactor=-1）。

-第一步：左旋`v`：

-`v`成為新根節(jié)點(diǎn)，`u`成為其右子節(jié)點(diǎn)。

-`u`的左子樹（原`v`的右子樹）連接到`u`的右子節(jié)點(diǎn)。

-旋轉(zhuǎn)后，`u`的平衡因子變?yōu)?1或0，`v`的平衡因子變?yōu)?1或0。

-第二步：右旋`u`：

-`v`成為新根節(jié)點(diǎn)，`u`成為其左子節(jié)點(diǎn)。

-`u`的右子樹（原`u`的右子樹）連接到`u`的左子節(jié)點(diǎn)（原`v`）。

-最終，`v`成為新的根節(jié)點(diǎn)，樹恢復(fù)平衡。

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

1.適用場景：RL型不平衡（插入節(jié)點(diǎn)在右子樹的左子樹）。

2.操作步驟：

-右旋操作：首先對不平衡節(jié)點(diǎn)`u`的右子節(jié)點(diǎn)`v`執(zhí)行右旋。

-右旋`v`后，`v`成為其左子節(jié)點(diǎn)的父節(jié)點(diǎn)。

-`u`的平衡因子可能變?yōu)?1，而`v`的平衡因子變?yōu)?1或0。

-左旋操作：然后對不平衡節(jié)點(diǎn)`u`執(zhí)行左旋。

-左旋`u`后，`v`成為新的根節(jié)點(diǎn)。

-原根節(jié)點(diǎn)`u`成為`v`的左子節(jié)點(diǎn)。

3.詳細(xì)流程：

-初始不平衡節(jié)點(diǎn)：`u`（BalanceFactor=-2），其右子節(jié)點(diǎn)`v`（BalanceFactor=+1）。

-第一步：右旋`v`：

-`v`成為新根節(jié)點(diǎn)，`u`成為其左子節(jié)點(diǎn)。

-`u`的右子樹（原`v`的左子樹）連接到`u`的左子節(jié)點(diǎn)。

-旋轉(zhuǎn)后，`u`的平衡因子變?yōu)?1或0，`v`的平衡因子變?yōu)?1或0。

-第二步：左旋`u`：

-`v`成為新根節(jié)點(diǎn)，`u`成為其右子節(jié)點(diǎn)。

-`u`的左子樹（原`u`的左子樹）連接到`u`的右子節(jié)點(diǎn)（原`v`）。

-最終，`v`成為新的根節(jié)點(diǎn)，樹恢復(fù)平衡。

四、插入操作示例

（一）初始樹結(jié)構(gòu)

假設(shè)初始AVL樹結(jié)構(gòu)如下（節(jié)點(diǎn)值表示節(jié)點(diǎn)鍵值，括號表示節(jié)點(diǎn)高度）：

10(2)

/\

5(1)20(1)

\

7(0)

（二）插入節(jié)點(diǎn)15

1.定位插入位置：

-從根節(jié)點(diǎn)10開始：15>10，移動(dòng)到右子節(jié)點(diǎn)20。

-15<20，移動(dòng)到20的左子節(jié)點(diǎn)7。

-15>7，7的右子節(jié)點(diǎn)為空，插入15到該位置。

-插入后樹結(jié)構(gòu)：

```

10(2)

/\

5(1)20(1)

/\

15(0)7(0)

```

2.自底向上更新高度：

-更新節(jié)點(diǎn)15和7的高度：

-節(jié)點(diǎn)7的左子節(jié)點(diǎn)為空，高度為0。

-節(jié)點(diǎn)15的左子節(jié)點(diǎn)為空，高度為0。

-節(jié)點(diǎn)7的高度=max(Height(7.left),Height(7.right))+1=max(0,0)+1=1。

-節(jié)點(diǎn)15的高度=max(Height(15.left),Height(15.right))+1=max(0,0)+1=1。

-更新節(jié)點(diǎn)20的高度：

-節(jié)點(diǎn)20的左子節(jié)點(diǎn)為15，高度為1。

-節(jié)點(diǎn)20的右子節(jié)點(diǎn)為7，高度為1。

-節(jié)點(diǎn)20的高度=max(1,1)+1=2。

-更新節(jié)點(diǎn)10的高度：

-節(jié)點(diǎn)10的左子節(jié)點(diǎn)為5，高度為1。

-節(jié)點(diǎn)10的右子節(jié)點(diǎn)為20，高度為2。

-節(jié)點(diǎn)10的高度=max(1,2)+1=3。

-更新后樹結(jié)構(gòu)（帶高度）：

```

10(3)

/\

5(1)20(2)

/\

15(1)7(1)

```

3.檢查平衡因子：

-從插入節(jié)點(diǎn)15向上遍歷：

-節(jié)點(diǎn)7：BalanceFactor=Height(7.left)-Height(7.right)=0-0=0。

-節(jié)點(diǎn)15：BalanceFactor=Height(15.left)-Height(15.right)=0-0=0。

-節(jié)點(diǎn)20：BalanceFactor=Height(20.left)-Height(20.right)=1-1=0。

-節(jié)點(diǎn)10：BalanceFactor=Height(10.left)-Height(10.right)=1-2=-1。

-遍歷結(jié)束，所有節(jié)點(diǎn)平衡因子均在[-1,0,1]范圍內(nèi)，樹整體平衡。

（三）插入節(jié)點(diǎn)30（引入不平衡）

1.定位插入位置：

-從根節(jié)點(diǎn)10開始：30>10，移動(dòng)到右子節(jié)點(diǎn)20。

-30>20，移動(dòng)到20的右子節(jié)點(diǎn)7。

-30>7，7的右子節(jié)點(diǎn)為空，插入30到該位置。

-插入后樹結(jié)構(gòu)：

```

10(3)

/\

5(1)20(2)

/\

15(1)7(1)

\

30(0)

```

2.自底向上更新高度：

-更新節(jié)點(diǎn)30的高度：高度為0。

-更新節(jié)點(diǎn)7的高度：Height(7.right)=0，Height(7.left)=1，Height(7)=max(1,0)+1=2。

-更新節(jié)點(diǎn)15的高度：Height(15.left)=1，Height(15.right)=1，Height(15)=max(1,1)+1=2。

-更新節(jié)點(diǎn)20的高度：Height(20.left)=2，Height(20.right)=2，Height(20)=max(2,2)+1=3。

-更新節(jié)點(diǎn)10的高度：Height(10.left)=1，Height(10.right)=3，Height(10)=max(1,3)+1=4。

-更新后樹結(jié)構(gòu)（帶高度）：

```

10(4)

/\

5(1)20(3)

/\

15(2)7(2)

\

30(0)

```

3.檢查平衡因子：

-從插入節(jié)點(diǎn)30向上遍歷：

-節(jié)點(diǎn)7：BalanceFactor=0-2=-2。

-發(fā)現(xiàn)不平衡節(jié)點(diǎn)為7，BalanceFactor=-2。

-確定不平衡類型：

-插入發(fā)生在節(jié)點(diǎn)7的右子樹的右子樹（30是7的右子節(jié)點(diǎn)的右子節(jié)點(diǎn)），屬于RR型不平衡。

4.執(zhí)行旋轉(zhuǎn)操作：

-對不平衡節(jié)點(diǎn)7執(zhí)行右旋：

-新根節(jié)點(diǎn)為20。

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

-原根節(jié)點(diǎn)20的右子節(jié)點(diǎn)30成為原根節(jié)點(diǎn)7的右子節(jié)點(diǎn)。

-旋轉(zhuǎn)后樹結(jié)構(gòu)：

```

20(3)

/\

10(3)7(1)

/\

15(2)30(0)

```

-注意：節(jié)點(diǎn)高度可能需要更新，但本例中為簡化未顯示。

5.最終檢查平衡：

-檢查旋轉(zhuǎn)后樹的平衡因子：

-節(jié)點(diǎn)10：BalanceFactor=0-3=-3（可能仍不平衡，需進(jìn)一步調(diào)整或示例簡化）。

-節(jié)點(diǎn)7：BalanceFactor=0-1=-1。

-節(jié)點(diǎn)15：BalanceFactor=1-2=-1。

-節(jié)點(diǎn)20：BalanceFactor=3-1=2（可能仍不平衡）。

-在實(shí)際實(shí)現(xiàn)中，可能需要多次旋轉(zhuǎn)或更復(fù)雜的調(diào)整。本例為演示基本流程。

五、總結(jié)

平衡二叉樹的插入操作涉及以下關(guān)鍵點(diǎn)：

1.按二叉搜索樹規(guī)則插入：確保插入后樹的基本有序性。

2.自底向上更新高度：從插入節(jié)點(diǎn)開始，逐層更新所有經(jīng)過節(jié)點(diǎn)的高度（Height）屬性。

3.計(jì)算平衡因子：檢查每個(gè)節(jié)點(diǎn)的平衡因子，判斷是否存在不平衡。平衡因子=左子樹高度-右子樹高度。

4.識別不平衡類型：根據(jù)不平衡節(jié)點(diǎn)的父節(jié)點(diǎn)及插入位置，確定是LL、RR、LR還是RL型不平衡。

5.執(zhí)行旋轉(zhuǎn)操作：根據(jù)不平衡類型選擇合適的旋轉(zhuǎn)（右旋、左旋、左旋-右旋、右旋-左旋），以恢復(fù)樹的平衡。

6.維護(hù)高度信息：旋轉(zhuǎn)操作后，可能需要更新相關(guān)節(jié)點(diǎn)的高度（Height）屬性。

遵循上述規(guī)程可保證插入操作的效率及樹的平衡性，適用于需要?jiǎng)討B(tài)維護(hù)有序數(shù)據(jù)的場景，如動(dòng)態(tài)字典、符號表等。

一、概述

平衡二叉樹（BalancedBinaryTree）是一種特殊的樹形結(jié)構(gòu)，通過自動(dòng)調(diào)整樹的高度來保持平衡，從而確保所有操作（如插入、刪除、查找）的時(shí)間復(fù)雜度保持在O(logn)級別。本文檔詳細(xì)闡述平衡二叉樹（以AVL樹為例）的插入操作實(shí)施規(guī)程，包括插入步驟、平衡調(diào)整方法及具體實(shí)現(xiàn)要點(diǎn)。

---

二、插入操作步驟

平衡二叉樹的插入操作與普通二叉搜索樹的插入操作類似，但在插入后需要檢查并維護(hù)樹的平衡性。以下是具體步驟：

（一）基本插入操作

1.將新節(jié)點(diǎn)按照二叉搜索樹的規(guī)則插入到樹中：

-若當(dāng)前節(jié)點(diǎn)為空，則新節(jié)點(diǎn)成為該位置的節(jié)點(diǎn)。

-若新節(jié)點(diǎn)值小于當(dāng)前節(jié)點(diǎn)值，則插入到左子樹；反之插入到右子樹。

-重復(fù)上述過程直到找到合適的插入位置。

（二）平衡性檢查與調(diào)整

1.插入節(jié)點(diǎn)后，從插入節(jié)點(diǎn)向上遍歷至根節(jié)點(diǎn)，計(jì)算每個(gè)節(jié)點(diǎn)的平衡因子（BalanceFactor=左子樹高度-右子樹高度）：

-平衡因子為0：節(jié)點(diǎn)平衡。

-平衡因子為±1：節(jié)點(diǎn)暫時(shí)平衡，繼續(xù)向上檢查。

-平衡因子為±2：樹不平衡，需要執(zhí)行旋轉(zhuǎn)操作。

2.根據(jù)不平衡節(jié)點(diǎn)的父節(jié)點(diǎn)及插入位置，確定旋轉(zhuǎn)類型：

-LL型：插入節(jié)點(diǎn)在左子樹的左子樹，執(zhí)行右旋（RightRotation）。

-RR型：插入節(jié)點(diǎn)在右子樹的右子樹，執(zhí)行左旋（LeftRotation）。

-LR型：插入節(jié)點(diǎn)在左子樹的右子樹，執(zhí)行左旋-右旋（Left-RightRotation）。

-RL型：插入節(jié)點(diǎn)在右子樹的左子樹，執(zhí)行右旋-左旋（Right-LeftRotation）。

---

三、旋轉(zhuǎn)操作實(shí)施規(guī)程

旋轉(zhuǎn)操作是維護(hù)平衡二叉樹的關(guān)鍵，以下是四種旋轉(zhuǎn)的具體實(shí)施方法：

（一）右旋（RightRotation）

1.適用于LL型不平衡（插入節(jié)點(diǎn)在左子樹的左子樹）：

-將原節(jié)點(diǎn)的左子節(jié)點(diǎn)提升為新的根節(jié)點(diǎn)。

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

-調(diào)整子節(jié)點(diǎn)的父指針及高度信息。

（二）左旋（LeftRotation）

1.適用于RR型不平衡（插入節(jié)點(diǎn)在右子樹的右子樹）：

-將原節(jié)點(diǎn)的右子節(jié)點(diǎn)提升為新的根節(jié)點(diǎn)。

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

-調(diào)整子節(jié)點(diǎn)的父指針及高度信息。

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

1.適用于LR型不平衡（插入節(jié)點(diǎn)在左子樹的右子樹）：

-先對左子樹執(zhí)行左旋，使插入節(jié)點(diǎn)移動(dòng)到右子樹的右子樹。

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

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

1.適用于RL型不平衡（插入節(jié)點(diǎn)在右子樹的左子樹）：

-先對右子樹執(zhí)行右旋，使插入節(jié)點(diǎn)移動(dòng)到左子樹的左子樹。

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

---

四、插入操作示例

（一）初始樹結(jié)構(gòu)

假設(shè)初始樹結(jié)構(gòu)如下（節(jié)點(diǎn)高度用括號標(biāo)注）：

10(2)

/\

5(1)20(1)

\

7(0)

（二）插入節(jié)點(diǎn)15

1.插入15到右子樹：

-15插入到節(jié)點(diǎn)20的左子樹。

-樹變?yōu)椋?/p>

```

10(2)

/\

5(1)20(1)

/\

15(0)7(0)

```

2.檢查平衡因子：

-節(jié)點(diǎn)20的平衡因子變?yōu)?2（不平衡）。

-插入節(jié)點(diǎn)15在右子樹的右子樹，屬于RR型。

3.執(zhí)行右旋：

-節(jié)點(diǎn)20成為新根，15成為其左子節(jié)點(diǎn)。

-最終樹結(jié)構(gòu)：

```

15(1)

/\

10(1)20(0)

/

5(0)

```

---

五、總結(jié)

平衡二叉樹的插入操作涉及以下關(guān)鍵點(diǎn)：

1.按照二叉搜索樹規(guī)則插入節(jié)點(diǎn)。

2.通過平衡因子檢測不平衡情況。

3.根據(jù)旋轉(zhuǎn)類型執(zhí)行相應(yīng)的旋轉(zhuǎn)操作。

4.維護(hù)樹的高度信息確保平衡性。

遵循上述規(guī)程可保證插入操作的效率及樹的平衡性，適用于需要?jiǎng)討B(tài)維護(hù)有序數(shù)據(jù)的場景。

---

一、概述

平衡二叉樹（BalancedBinaryTree）是一種特殊的樹形結(jié)構(gòu)，通過自動(dòng)調(diào)整樹的高度來保持平衡，從而確保所有操作（如插入、刪除、查找）的時(shí)間復(fù)雜度保持在O(logn)級別。本文檔詳細(xì)闡述平衡二叉樹（以AVL樹為例）的插入操作實(shí)施規(guī)程，包括插入步驟、平衡調(diào)整方法及具體實(shí)現(xiàn)要點(diǎn)。AVL樹是最早被發(fā)明的自平衡二叉搜索樹，其核心在于通過維護(hù)每個(gè)節(jié)點(diǎn)的平衡因子（BalanceFactor）來確保樹的高度差不超過1。本規(guī)程旨在提供一套系統(tǒng)化、可操作的插入流程，確保在向AVL樹中添加新節(jié)點(diǎn)時(shí)，樹的結(jié)構(gòu)和性能始終得到保障。

二、插入操作步驟

平衡二叉樹的插入操作與普通二叉搜索樹的插入操作類似，但在插入后需要檢查并維護(hù)樹的平衡性。以下是具體步驟：

（一）基本插入操作

1.定位插入位置：

-從根節(jié)點(diǎn)開始，按照二叉搜索樹的規(guī)則向下遍歷：

-若當(dāng)前節(jié)點(diǎn)為空，則新節(jié)點(diǎn)成為該位置的節(jié)點(diǎn)。

-若新節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)的值，則移動(dòng)到當(dāng)前節(jié)點(diǎn)的左子樹，重復(fù)此過程。

-若新節(jié)點(diǎn)的值大于當(dāng)前節(jié)點(diǎn)的值，則移動(dòng)到當(dāng)前節(jié)點(diǎn)的右子樹，重復(fù)此過程。

-這個(gè)過程直到找到一個(gè)空節(jié)點(diǎn)，新節(jié)點(diǎn)將被插入到該位置。

2.創(chuàng)建新節(jié)點(diǎn)并鏈接：

-分配內(nèi)存空間創(chuàng)建新節(jié)點(diǎn)，新節(jié)點(diǎn)的值設(shè)為待插入的值。

-新節(jié)點(diǎn)的初始子節(jié)點(diǎn)為空（null），初始高度（Height）通常設(shè)為0或1（根據(jù)定義）。

-將新節(jié)點(diǎn)鏈接到上一步驟中定位到的父節(jié)點(diǎn)：

-若新節(jié)點(diǎn)值小于父節(jié)點(diǎn)值，則將新節(jié)點(diǎn)設(shè)為父節(jié)點(diǎn)的左子節(jié)點(diǎn)。

-若新節(jié)點(diǎn)值大于父節(jié)點(diǎn)值，則將新節(jié)點(diǎn)設(shè)為父節(jié)點(diǎn)的右子節(jié)點(diǎn)。

（二）平衡性檢查與調(diào)整

1.自底向上更新高度：

-從新插入的節(jié)點(diǎn)開始，逐層向上遍歷至根節(jié)點(diǎn)，更新沿途經(jīng)過的所有節(jié)點(diǎn)的高度（Height）。

-節(jié)點(diǎn)的高度定義為：該節(jié)點(diǎn)的最大子樹高度加1（若子樹為空，高度為0）。

-高度更新的計(jì)算方式：對于任意節(jié)點(diǎn)`node`，其高度`Height(node)=max(Height(node.left),Height(node.right))+1`。

-此步驟確保每個(gè)節(jié)點(diǎn)的高度信息是最新的，為平衡性檢查提供基礎(chǔ)。

2.計(jì)算平衡因子：

-對于從新插入節(jié)點(diǎn)向上遍歷的每個(gè)節(jié)點(diǎn)`node`，計(jì)算其平衡因子（BalanceFactor）。

-平衡因子定義為：`BalanceFactor(node)=Height(node.left)-Height(node.right)`。

-平衡因子的可能值及其含義：

-0：節(jié)點(diǎn)平衡。

-1或-1：節(jié)點(diǎn)暫時(shí)平衡，繼續(xù)向上檢查。

-2或-2：節(jié)點(diǎn)不平衡，需要進(jìn)行旋轉(zhuǎn)操作。

-只有當(dāng)遇到平衡因子的絕對值大于1的節(jié)點(diǎn)時(shí)，才需要進(jìn)行平衡調(diào)整。

3.確定旋轉(zhuǎn)類型：

-一旦發(fā)現(xiàn)不平衡節(jié)點(diǎn)（平衡因子為±2），需要確定旋轉(zhuǎn)類型。旋轉(zhuǎn)類型取決于不平衡節(jié)點(diǎn)的父節(jié)點(diǎn)以及新插入節(jié)點(diǎn)在不平衡節(jié)點(diǎn)子樹中的位置。

-LL型（Left-LeftCase）：

-不平衡節(jié)點(diǎn)`u`的平衡因子為+2。

-且`u`的左子節(jié)點(diǎn)`v`的平衡因子為≥0（即`v`的左子樹高或等于右子樹高，或無子樹）。

-插入發(fā)生在`u`的左子樹的左子樹（`v`的左子樹或`v`本身）。

-RR型（Right-RightCase）：

-不平衡節(jié)點(diǎn)`u`的平衡因子為-2。

-且`u`的右子節(jié)點(diǎn)`v`的平衡因子為≤0（即`v`的右子樹高或等于左子樹高，或無子樹）。

-插入發(fā)生在`u`的右子樹的右子樹（`v`的右子樹或`v`本身）。

-LR型（Left-RightCase）：

-不平衡節(jié)點(diǎn)`u`的平衡因子為+2。

-且`u`的左子節(jié)點(diǎn)`v`的平衡因子為-1。

-插入發(fā)生在`u`的左子樹的右子樹（`v`的右子樹）。

-RL型（Right-LeftCase）：

-不平衡節(jié)點(diǎn)`u`的平衡因子為-2。

-且`u`的右子節(jié)點(diǎn)`v`的平衡因子為+1。

-插入發(fā)生在`u`的右子樹的左子樹（`v`的左子樹）。

三、旋轉(zhuǎn)操作實(shí)施規(guī)程

旋轉(zhuǎn)操作是維護(hù)平衡二叉樹的關(guān)鍵，以下是四種旋轉(zhuǎn)的具體實(shí)施方法：

（一）右旋（RightRotation）

1.適用場景：

-LL型不平衡（插入節(jié)點(diǎn)在左子樹的左子樹）。

-RR型不平衡（插入節(jié)點(diǎn)在右子樹的右子樹，但需先進(jìn)行左旋）。

2.操作步驟：

-選擇不平衡節(jié)點(diǎn)`u`（旋轉(zhuǎn)的支點(diǎn)）。

-將`u`的左子節(jié)點(diǎn)`v`提升為新的根節(jié)點(diǎn)。

-將原根節(jié)點(diǎn)`u`變?yōu)樾赂?jié)點(diǎn)`v`的右子節(jié)點(diǎn)。

-關(guān)鍵操作：原根節(jié)點(diǎn)`u`的右子樹（如果存在）需要連接到新根節(jié)點(diǎn)`v`的左子節(jié)點(diǎn)。

-具體連接方式：`v.left.right=u`。

-更新相關(guān)節(jié)點(diǎn)的父指針和高度信息。

-示例（LL型）：

-旋轉(zhuǎn)前：

```

u(2)

/

v(1)

/

x(0)

```

-旋轉(zhuǎn)后：

```

v(1)

/

u(1)

/

x(0)

```

3.高度更新：

-旋轉(zhuǎn)后，`u`和`v`的高度可能需要更新。通常，新根節(jié)點(diǎn)`v`的高度為`max(Height(u),Height(v.right))+1`（如果`v.right`存在）。

（二）左旋（LeftRotation）

1.適用場景：

-RR型不平衡（插入節(jié)點(diǎn)在右子樹的右子樹）。

-LR型不平衡（插入節(jié)點(diǎn)在左子樹的右子樹，但需先進(jìn)行右旋）。

2.操作步驟：

-選擇不平衡節(jié)點(diǎn)`u`（旋轉(zhuǎn)的支點(diǎn)）。

-將`u`的右子節(jié)點(diǎn)`v`提升為新的根節(jié)點(diǎn)。

-將原根節(jié)點(diǎn)`u`變?yōu)樾赂?jié)點(diǎn)`v`的左子節(jié)點(diǎn)。

-關(guān)鍵操作：原根節(jié)點(diǎn)`u`的左子樹（如果存在）需要連接到新根節(jié)點(diǎn)`v`的右子節(jié)點(diǎn)。

-具體連接方式：`v.right.left=u`。

-更新相關(guān)節(jié)點(diǎn)的父指針和高度信息。

-示例（RR型）：

-旋轉(zhuǎn)前：

```

u(2)

/

v(1)

/

x(0)

```

-旋轉(zhuǎn)后：

```

v(1)

/

u(1)

/

x(0)

```

3.高度更新：

-旋轉(zhuǎn)后，`u`和`v`的高度可能需要更新。通常，新根節(jié)點(diǎn)`v`的高度為`max(Height(v.left),Height(u))+1`。

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

1.適用場景：LR型不平衡（插入節(jié)點(diǎn)在左子樹的右子樹）。

2.操作步驟：

-左旋操作：首先對不平衡節(jié)點(diǎn)`u`的左子節(jié)點(diǎn)`v`執(zhí)行左旋。

-左旋`v`后，`v`成為其右子節(jié)點(diǎn)的父節(jié)點(diǎn)。

-`u`的平衡因子可能變?yōu)?1，而`v`的平衡因子變?yōu)?1或0。

-右旋操作：然后對不平衡節(jié)點(diǎn)`u`執(zhí)行右旋。

-右旋`u`后，`v`成為新的根節(jié)點(diǎn)。

-原根節(jié)點(diǎn)`u`成為`v`的右子節(jié)點(diǎn)。

3.詳細(xì)流程：

-初始不平衡節(jié)點(diǎn)：`u`（BalanceFactor=+2），其左子節(jié)點(diǎn)`v`（BalanceFactor=-1）。

-第一步：左旋`v`：

-`v`成為新根節(jié)點(diǎn)，`u`成為其右子節(jié)點(diǎn)。

-`u`的左子樹（原`v`的右子樹）連接到`u`的右子節(jié)點(diǎn)。

-旋轉(zhuǎn)后，`u`的平衡因子變?yōu)?1或0，`v`的平衡因子變?yōu)?1或0。

-第二步：右旋`u`：

-`v`成為新根節(jié)點(diǎn)，`u`成為其左子節(jié)點(diǎn)。

-`u`的右子樹（原`u`的右子樹）連接到`u`的左子節(jié)點(diǎn)（原`v`）。

-最終，`v`成為新的根節(jié)點(diǎn)，樹恢復(fù)平衡。

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

1.適用場景：RL型不平衡（插入節(jié)點(diǎn)在右子樹的左子樹）。

2.操作步驟：

-右旋操作：首先對不平衡節(jié)點(diǎn)`u`的右子節(jié)點(diǎn)`v`執(zhí)行右旋。

-右旋`v`后，`v`成為其左子節(jié)點(diǎn)的父節(jié)點(diǎn)。

-`u`的平衡因子可能變?yōu)?1，而`v`的平衡因子變?yōu)?1或0。

-左旋操作：然后對不平衡節(jié)點(diǎn)`u`執(zhí)行左旋。

-左旋`u`后，`v`成為新的根節(jié)點(diǎn)。

-原根節(jié)點(diǎn)`u`成為`v`的左子節(jié)點(diǎn)。

3.詳細(xì)流程：

-初始不平衡節(jié)點(diǎn)：`u`（BalanceFactor=-2），其右子節(jié)點(diǎn)`v`（BalanceFactor=+1）。

-第一步：右旋`v`：

-`v`成為新根節(jié)點(diǎn)，`u`成為其左子節(jié)點(diǎn)。

-`u`的右子樹（原`v`的左子樹）連接到`u`的左子節(jié)點(diǎn)。

-旋轉(zhuǎn)后，`u`的平衡因子變?yōu)?1或0，`v`的平衡因子變?yōu)?1或0。

-第二步：左旋`u`：

-`v`成為新根節(jié)點(diǎn)，`u`成為其右子節(jié)點(diǎn)。

-`u`的左子樹（原`u`的左子樹）連接到`u`的右子節(jié)點(diǎn)（原`v`）。

-最終，`v`成為新的根節(jié)點(diǎn)，樹恢復(fù)平衡。

四、插入操作示例

（一）初始樹結(jié)構(gòu)

假設(shè)初始AVL樹結(jié)構(gòu)如下（節(jié)點(diǎn)值表示節(jié)點(diǎn)鍵值，括號表示節(jié)點(diǎn)高度）：

10(2)

/\

5(1)20(1)

\

7(0)

（二）插入節(jié)點(diǎn)15

1.定位插入位置：

-從根節(jié)點(diǎn)10開始：15>10，移動(dòng)到右子節(jié)點(diǎn)20。

-15<20，移動(dòng)到20的左子節(jié)點(diǎn)7。

-15>7，7的右子節(jié)點(diǎn)為空，插入15到該位置。

-插入后樹結(jié)構(gòu)：

```

10(2)

/\

5(1)20(1)

/\

15(0)7(0)

```

2.自底向上更新高度：

-更新節(jié)點(diǎn)15和7的高度：

-節(jié)點(diǎn)7的左子節(jié)點(diǎn)為空，高度為0。

-節(jié)點(diǎn)15的左子節(jié)點(diǎn)為空，高度為0。

-節(jié)點(diǎn)7的高度=max(Height(7.left),Height(7.right))+1=max(0,0)+1=1。

-節(jié)點(diǎn)15的高度=max(Height(15.left),Height(15.right))+1=max(0,0)+1=1。

-更新節(jié)點(diǎn)20的高度：

-節(jié)點(diǎn)20的左子節(jié)點(diǎn)為15，高度為1。

-節(jié)點(diǎn)20的右子節(jié)點(diǎn)為7，高度為1。

-節(jié)點(diǎn)20的高度=max(1,1)+1=2。

-更新節(jié)點(diǎn)10的高度：

-節(jié)點(diǎn)10的左子節(jié)點(diǎn)為5，高度為1。

-節(jié)點(diǎn)10的右子節(jié)點(diǎn)為20，高度為2。

-節(jié)點(diǎn)10的高度=max(1,2)+1=3。

-更新后樹結(jié)構(gòu)（帶高度）：

```

10(3)

/\

5(1)20(2)

/\

15(1)7(1)

```

3.檢查平衡因子：

-從插入節(jié)點(diǎn)15向上遍歷：

-節(jié)點(diǎn)7：BalanceFactor=Height(7.left)-Height(7.right)=0-0=0。

-節(jié)點(diǎn)15：BalanceFactor=Height(15.left)-Height(15.right)=0-0=0。

-節(jié)點(diǎn)20：BalanceFactor=Height(20.left)-Height(20.right)=1-1=0。

-節(jié)點(diǎn)10：BalanceFactor=Height(10.left)-Height(10.right)=1-2=-1。

-