目錄

搭建“創世”的舞臺

注入序列，觀察演化

注入 10

注入 20

注入 30

注入 40

注入 50

注入 25

再次審視

---

上一講，我們已經從最根本的邏輯出發，推導出了 AVL 樹失衡時所必需的修復操作——旋轉 (Rotation)。

現在，我們將進入一個非常實踐性的環節：如何從無到有地生成 (Generating) 一棵 AVL 樹？

這個問題的本質，其實是一個思想實驗：

如果我們擁有一臺“AVL 插入機”（也就是我們上一講實現的 insert 函數），我們把一堆數字一個一個地扔給它，這臺機器內部會發生什么？最終會得到一個什么樣的產品？

搭建“創世”的舞臺

在開始之前，我們需要三樣東西：

1. 一個起點 (The Starting Point)： 一個空的世界，也就是一棵空樹。在 C/C++ 代碼中，我們用一個 NULL 指針來表示。

// 我們的宇宙之初，只有一個指向虛空的根指針
AVLTreeNode* root = NULL;

2. 一套基本法則 (The Rules)： 這就是我們上一講嘔心瀝血推導出的 insert 函數。它內部封裝了 BST 的插入邏輯、高度 (Height) 的更新、平衡因子 (Balance Factor, BF) 的檢查，以及四種旋轉 (Rotation) 修復機制。

3. 一串生命序列 (The Sequence)： 我們將要注入的數字。為了充分展示樹的演化過程，我們需要一個能觸發各種情況的序列。我們選用這個經典的序列：[10, 20, 30, 40, 50, 25]。

我們的整個“生成”過程，在代碼層面其實非常簡潔，就是一個循環，不斷地調用我們的基本法則 insert 函數。

數據結構：利用旋轉在AVL樹中維持平衡（Inserting in AVL with Rotation）-CSDN博客

// 引入頭文件，以便我們可以打印輸出觀察每一步
#include <iostream>// ... 此處省略我們之前已經定義的 AVLTreeNode 結構體、
// createNode, getHeight, max, leftRotate, rightRotate, insert 等函數 ...// 主程序，也就是我們的“創世”過程
int main() {AVLTreeNode* root = NULL; // 1. 起點：空樹int keys[] = {10, 20, 30, 40, 50, 25}; // 3. 生命序列int n = sizeof(keys) / sizeof(keys[0]);std::cout << "Starting to generate the AVL tree..." << std::endl;std::cout << "------------------------------------" << std::endl;for (int i = 0; i < n; ++i) {std::cout << "\n>>> Inserting " << keys[i] << "..." << std::endl;// 2. 反復調用我們的基本法則root = insert(root, keys[i]);// 為了便于觀察，我們可以在這里加上一個打印樹結構的函數（此處省略其實現）// printTree(root); std::cout << ">>> ... " << keys[i] << " inserted. Tree is now balanced." << std::endl;}std::cout << "\n------------------------------------" << std::endl;std::cout << "Generation complete." << std::endl;return 0;
}

代碼框架已經搭好，現在，讓我們進入核心環節，手動模擬上面這段代碼的執行過程，觀察樹的每一步演化。

---

注入序列，觀察演化

注入 10

• 演化過程： 樹為空，insert 函數直接創建一個新節點作為根。

• 最終形態：樹誕生了，它是平衡的。

(10) {h=0, BF=0}  // h 是 Height(高度), BF 是 Balance Factor(平衡因子)

注入 20

• 演化過程：

  1. 根據 BST 法則, 20 > 10，插入到 10 的右側。

  2. 插入后回溯，更新路徑上的節點。節點 10 的高度 h 更新為 1，其平衡因子 BF 變為 height(left) - height(right) = -1 - 0 = -1。

  3. |BF| <= 1，樹依然平衡。

• 最終形態：

  (10) {h=1, BF=-1}\(20) {h=0, BF=0}

注入 30

• 演化過程：

  1. 根據 BST 法則, 30 > 10 (向右) -> 30 > 20 (向右)，插入到 20 的右側。

  2. 回溯更新：

     • 20 節點：h 更新為 1, BF 更新為 -1。平衡。

     • 10 節點：h 更新為 2, BF 更新為 height(left) - height(right) = -1 - 1 = -2。

  3. 警報！ 節點 10 的 BF 絕對值變為 2，樹失衡 (Unbalanced)！

• 診斷與修復：

  • 失衡節點 A 是 10 (BF=-2)。

  • 失衡是由于在 A 的右 (Right)子樹 (B=20) 的右 (Right)側插入新節點導致的。

  • 這是典型的 RR (右-右) 失衡。

  • 根據我們的法則，需要對失衡節點 10 執行一次 左旋 (Left Rotation)。

• 修復后形態：

  (20) {h=1, BF=0}/  \
(10) (30) {h=0, BF=0}

注入 40

• 演化過程： 40 根據 BST 法則插入為 30 的右孩子。回溯檢查，所有節點的 BF 均在 [-1, 1] 區間內。

• 最終形態： 無需旋轉。

  (20) {h=2, BF=-1}/  \
(10) (30) {h=1, BF=-1}\(40) {h=0, BF=0}

注入 50

• 演化過程：

  1. 50 插入為 40 的右孩子。

  2. 回溯更新，當檢查到 30 節點時，其 h 變為 2，BF 變為 -2。失衡！

• 診斷與修復：

  • 失衡節點 A 是 30 (BF=-2)。

  • 失衡路徑是 右-右 (RR)。

  • 修復操作：對 30 執行 左旋 (Left Rotation)。40 會取代 30 的位置，成為 20 的右孩子。

• 修復后形態：

      (20) {h=2, BF=-1}/  \(10) (40) {h=1, BF=0}/  \(30) (50)

系統再次自我修復，恢復平衡。

注入 25

• 演化過程：

  1. 根據 BST 法則: 25>20 (右) -> 25<40 (左) -> 25<30 (左)。25 插入為 30 的左孩子。

  2. 回溯更新：

     • 30 節點: h 變為 1, BF 變為 1。平衡。

     • 40 節點: h 變為 2, BF 變為 1。平衡。

     • 20 節點: h 變為 3, BF 變為 height(left) - height(right) = 0 - 2 = -2。 失衡！

• 診斷與修復：

  • 失衡節點 A 是 20 (BF=-2)。

  • 失衡發生在 A 的右 (Right)子樹 (根為 40)。

  • 新節點 25 是插入在該子樹的左 (Left)側。

  • 這是一個 RL (右-左) 的“拐角”型失衡。

  • 根據法則，需要兩步操作：

    1. “拉直”拐角： 對 A 的孩子節點 40，執行一次右旋 (Right Rotation)。

    2. 整體修復： 對 A 節點 20，執行一次左旋 (Left Rotation)。

• 修復后最終形態：

      (30)/    \(20)    (40)/  \      \
(10) (25)    (50)

經歷了一次復雜的重構后，系統演化出了一個極為穩定和平衡的最終形態。

---

再次審視

我們完成了整個生成過程。回過頭看，我們得到了什么結論？

• 自組織性 (Self-Organization): 我們從未規劃過最終那棵樹長什么樣。我們只定義了最基本的、局部的交互規則（插入和旋轉）。一個高度平衡的、優美的全局結構，是自發涌現出來的。

• 動態平衡 (Dynamic Equilibrium): AVL 樹不是靜止的。每次有新的元素加入，都會暫時打破它的平衡，然后系統會通過一系列的調整，迅速回歸到一個新的平衡狀態。這是一種動態的、有彈性的穩定。

• 局部決定全局 (Local Actions, Global Consequences): 每次修復操作（旋轉）都只涉及兩到三個節點。然而，就是這樣微小的局部調整，確保了整棵樹的全局屬性——對數級別的高度，從而保證了 O(logn) 的操作效率。

這就是從第一性原理理解“生成 AVL 樹”——它不是一個按圖索驥的建造過程，而是一個遵循簡單規則、不斷演化的創生過程。