平衡二叉樹：爲什麼需要平衡？旋轉操作簡單講

我們先從最常見的數據結構之一——二叉搜索樹（BST）說起。二叉搜索樹是一種按特定規則排列的二叉樹：對於任意節點，左子樹的所有節點值都小於它，右子樹的所有節點值都大於它。這種結構在理想情況下，查找、插入、刪除的時間複雜度都是 O(log n)，看起來很高效。

但如果我們插入節點的順序比較“極端”，比如一直往右邊插入（或一直往左邊插入），BST 就會退化成一個鏈表。例如，連續插入 1, 2, 3, 4, 5，最終樹會變成一條長長的右鏈，查找時需要從根節點一路走到葉子，時間複雜度變成 O(n)，這就失去了 BST 的優勢。

什麼是“平衡”？¶

平衡二叉樹（比如 AVL 樹）的核心是 “平衡因子”。每個節點的平衡因子定義爲：左子樹高度 - 右子樹高度。對於平衡二叉樹，每個節點的平衡因子必須是 -1、0 或 1（即左右子樹高度差不超過 1）。

舉個例子：如果一個節點的左子樹高度是 3，右子樹高度是 1，那麼平衡因子是 2，這棵樹就“不平衡”了。

爲什麼需要平衡？¶

想象你在圖書館找書：如果書架是“平衡”的（每一層書的數量差不多），你很快就能找到目標；但如果書架是傾斜的（左邊堆了 100 本，右邊只有 1 本），你可能需要花更多時間爬過去。

樹的高度直接影響操作效率。平衡的樹高度近似爲 log n（比如 n=1000 時，高度約 10），而不平衡的樹可能退化成 O(n) 高度。平衡二叉樹通過調整結構，讓樹的高度始終保持在 log n 級別，從而保證查詢、插入、刪除的高效性。

旋轉操作：如何讓樹“平衡”？¶

當樹不平衡時（平衡因子絕對值 >1），需要通過 旋轉操作 調整結構。旋轉有四種基本類型：LL 型、RR 型、LR 型、RL 型，本質是通過“調整支點”讓樹恢復平衡。

1. LL 型：左左失衡（右旋）¶

場景：節點 A 的左子樹高度比右子樹高 2，且左子樹的左子樹也高。
例子：
插入順序：10, 5, 3, 1（連續插入左子樹），形成樹結構：

    10
   /
  5
 /
3
 /
1

此時，節點 10 的平衡因子爲 2（左高右低），需要右旋。

右旋步驟：
- 以節點 5 爲新根，原來的根 10 變成 5 的右孩子；
- 5 原來的右子樹（如果有的話），變成 10 的左孩子（這裏 5 沒有右子樹，所以 10 的左孩子爲空）。

旋轉後結構：

  5
 / \
3   10
 \
  1  // 注意：3 的右孩子是 1（原 3 的右子樹爲空，這裏 3 原來只有左孩子 1？哦，原結構是 5 的左孩子是 3，3 的左孩子是 1，所以右旋後 3 是 5 的左孩子，10 是 5 的右孩子，3 的右子樹爲空，所以 10 的左孩子爲空。正確結構：

  5
 / \
3   10
 \
  1

（更準確的描述：右旋後，原根節點 10 變成新根 5 的右孩子，原根的左子樹（5 的左子樹）保持不變，原根的右子樹（空）變成 10 的左子樹。）

2. RR 型：右右失衡（左旋）¶

場景：節點 A 的右子樹高度比左子樹高 2，且右子樹的右子樹也高。
例子：
插入順序：1, 3, 5, 7（連續插入右子樹），形成樹結構：

1
 \
  3
   \
    5
     \
      7

此時，節點 1 的平衡因子爲 -2（右高左低），需要左旋。

左旋步驟：
- 以節點 5 爲新根，原來的根 1 變成 5 的左孩子；
- 5 原來的左子樹（如果有的話），變成 1 的右孩子（這裏 5 沒有左子樹，所以 1 的右孩子爲空）。

旋轉後結構：

    5
   / \
  1   7
   \
    3

（原根 1 變成 5 的左孩子，原根的右子樹（3）變成 1 的右孩子。）

3. LR 型：左右失衡（先左旋再右旋）¶

場景：節點 A 的左子樹高度比右子樹高 2，但左子樹的右子樹更高。
例子：
插入順序：10, 5, 7, 3（先插左 5，再插右 7，再插左 3），形成樹結構：

    10
   /
  5
   \
    7
   /
  3

此時，節點 10 的平衡因子爲 2（左高），但左子樹 5 的平衡因子爲 -1（右高），屬於 LR 型。

調整步驟：
1. 先左旋：對左子樹 5 進行左旋，將 7 變成 5 的父節點（即 5 和 7 交換位置）：

      10
     /
    7
   / \
  5   （原 5 的右子樹）
 /
3

2. 再右旋：對根節點 10 進行右旋，將 7 變成新根，10 變成 7 的右孩子：

     7
    / \
   5   10
  /
 3

旋轉後，所有節點的平衡因子均爲 -1、0 或 1，樹恢復平衡。

4. RL 型：右左失衡（先右旋再左旋）¶

場景：節點 A 的右子樹高度比左子樹高 2，但右子樹的左子樹更高。
例子：
插入順序：10, 15, 12, 20（先插右 15，再插左 12，再插右 20），形成樹結構：

    10
     \
      15
     /
    12
     \
      20

此時，節點 10 的平衡因子爲 -2（右高），右子樹 15 的平衡因子爲 1（左高），屬於 RL 型。

調整步驟：
1. 先右旋：對右子樹 15 進行右旋，將 12 變成 15 的父節點：

      10
       \
        12
         \
          15
           \
            20

2. 再左旋：對根節點 10 進行左旋，將 12 變成新根，10 變成 12 的左孩子：

      12
     / \
    10  15
         \
          20

旋轉後樹恢復平衡。

總結¶

平衡二叉樹通過 平衡因子 監控樹的結構，當樹不平衡時，通過 旋轉操作（LL/RR/LR/RL）調整節點位置，讓樹的高度始終保持在 log n 級別，從而保證操作效率。旋轉的本質是“調整支點”，讓樹的左右子樹高度差不超過 1，最終實現“高效查找”。

記住：平衡的核心是“讓樹不傾斜”，旋轉是“扶正傾斜樹”的關鍵動作。

（如果需要更直觀的旋轉效果，可以想象一個“蹺蹺板”：當左邊過重時，右邊的支點需要向上抬，把重的部分調回中間。樹的旋轉就像這樣，通過調整子樹的“位置”讓整體結構平衡。）