認識樹：到處都是的階層結構

從生物分類、Unix 檔案系統與 HTML 認識樹的三大性質。

先讀原文開場，旁邊就是白話

這是一本英文書。左邊放原文、右邊放白話導讀——你既讀得懂，也順手碰了原文。

原文 · 樹與樹的演算法 CHAPTER SIX TREES AND TREE ALGORITHMS 6. 1 Objectives • To understand what a tree data structure is and how it is used. • To see how trees can be used to implement a map data structure. • To implement trees using a list.

白話導讀

從生物分類、Unix 檔案系統與 HTML 認識樹的三大性質。

樹是什麼？生活中的樹狀結構

從生物分類、Unix 檔案系統與 HTML 認識樹的三大性質。

STEP 1

深度探秘

把資料排成有階層的關係

樹不是一條線

我們之前學的堆疊、佇列都是線性結構：資料像排隊一樣一個接一個。但真實世界裡很多關係不是一條線，而是一層分出好幾支的階層關係，這就需要「樹」。

樹這個資料結構有趣的地方是：它的根 (root) 在最上面，葉子 (leaf) 在最下面，跟你窗外那棵樹剛好上下顛倒。

從根開始，你可以沿著一個個節點與箭頭往下走。每到一層就像在問一個問題、依答案選一條路。例如生物分類：先問「這動物是脊索動物還是節肢動物？」選了脊索動物，再問「是不是哺乳類？」一路問下去，最後走到最底層的物種名稱。

樹有三個關鍵性質：

子節點彼此獨立：某節點的孩子改了，不會影響另一個節點的孩子。
每個葉節點唯一：從根到任一葉節點有一條唯一的路徑可以辨認它。
可整段搬移：你可以把一整段子樹搬到別的位置，而不破壞它內部的結構。

💡

關鍵

樹是用來表達階層關係的非線性資料結構，根在上、葉在下。

STEP 2

生活妙喻

電腦裡的資料夾就是一棵樹

你每天都在爬樹

想想你電腦裡的檔案系統。最外層有一個根目錄（在 Unix 裡就是 /），裡面有 etc/、usr/ 這些資料夾，資料夾裡又有子資料夾與檔案——這完完全全就是一棵樹！

從根目錄走到任何一個資料夾，這條路徑唯一指出了它的位置，例如 /etc/httpd。

而「可整段搬移」這個性質也很直覺：你把 etc/ 整個資料夾從根目錄剪下、貼到 usr/ 底下，httpd 的路徑會從 /etc/httpd 變成 /usr/etc/httpd，但 httpd 裡面的內容與子資料夾完全不受影響。搬家換了地址，但家裡的傢俱還是原封不動。

graph TD
  root[根目錄] --> etc[etc]
  root --> usr[usr]
  root --> var[var]
  etc --> httpd[httpd]
  var --> log[log]
  var --> spool[spool]

💡

關鍵

檔案系統的資料夾階層就是一棵樹，搬移子樹不影響其內部內容。

STEP 3

實用超能力

從 HTML 看出網頁的樹

網頁也是一棵樹

你看到的每個網頁，背後的 HTML 標籤也是巢狀的階層。最外層是 <html>，裡面包 <head> 和 <body>，<body> 裡又包 <h1>、<ul>，<ul> 裡再包 <li>。

每一層巢狀，就對應樹的一層。瀏覽器把這棵樹叫做 DOM，靠它來排版與互動。

<html>
  <head>
    <title>simple</title>
  </head>
  <body>
    <h1>A simple web page</h1>
    <ul>
      <li>List item one</li>
      <li>List item two</li>
    </ul>
  </body>
</html>

當你能「看出」資料中的樹狀結構，就能用樹的演算法去處理它：搜尋、走訪、整段搬移都變得有章法可循。

💡

關鍵

凡是有巢狀、階層關係的資料（檔案、HTML、分類），都能用樹來表示與處理。

🔆

生活妙喻：樹的結構 ≈ 公司組織圖

最上面是執行長（根），往下是各部門主管，再往下是組員（葉）。每個人只有一個直屬上司（一條進入的邊），但可以帶很多下屬。

🔆

生活妙喻：子節點獨立性 ≈ 兩個不同家庭都有小孩叫小明

張家的小明和李家的小明同名，但是兩個完全獨立的人。改張家小明的事，不會動到李家小明。

本節字彙

樹 (tree)

用來表達階層關係的資料結構，由節點與連接它們的邊組成，根在最上方。

🧠 想成上下顛倒的真樹：根在天上、葉在地上。

子樹 (subtree)

某個節點連同它底下所有後代，自成一棵小樹。

🧠 樹的任何一根樹枝，連同上面的葉子，都是一棵迷你樹。

下列哪一個是「樹」這種資料結構最貼切的描述？

在 Unix 檔案系統中把 `etc/` 整個資料夾從根目錄搬到 `usr/` 底下，下列敘述何者正確？

為什麼說「從根到每個葉節點的路徑是唯一的」這個性質很有用？

樹的詞彙：節點、邊、根、葉

認識 node、edge、root、path、children、parent、sibling、subtree、leaf、level、height 等術語。

STEP 1

深度探秘

先把零件名稱搞清楚

樹的零件清單

要談樹的演算法，得先有共同語言。以下是核心詞彙：

節點 (node)：樹的基本單位。它有一個名字叫鍵 (key)，還可能附帶額外資料叫酬載 (payload)。
邊 (edge)：連接兩個節點、表示它們有關係。除了根，每個節點恰有一條進入的邊；每個節點可以有多條外出的邊。
根 (root)：唯一沒有進入邊的節點。
路徑 (path)：用邊串起來的一串有序節點。
子節點 (children)：從同一個節點伸出邊所連到的那些節點。
父節點 (parent)：用外出邊連到某些節點的那個節點。
兄弟 (sibling)：同一個父節點下的節點。
子樹 (subtree)：一個父節點連同它所有後代。
葉節點 (leaf)：沒有子節點的節點。

💡

關鍵

節點是基本單位，邊表示關係；除了根，每個節點恰有一條進入的邊。

STEP 2

生活妙喻

家族族譜上的稱謂

樹的詞彙就是族譜稱謂

樹的術語幾乎照搬家族關係：

樹的術語	家族對應
根 (root)	最年長的祖先
父節點 (parent)	上一代
子節點 (children)	下一代
兄弟 (sibling)	同一對父母的孩子
葉節點 (leaf)	還沒有後代的人
子樹 (subtree)	某個人連同他所有後代組成的家族分支

唯一和真實家族不同的是：在樹裡每個人只有「一個」父親（一條進入的邊），不能有兩個父節點。

graph TD
  A[根 祖父] --> B[父 爸爸]
  A --> C[父 叔叔]
  B --> D[葉 我]
  B --> E[葉 妹妹]

💡

關鍵

把樹想成族譜，根是祖先、葉是最年輕一代、兄弟是同父節點的孩子。

STEP 3

實用超能力

算出層數與高度

層數與高度怎麼算

還有兩個常被搞混的詞：

層 (level)：節點 $n$ 的層數，是從根到 $n$ 這條路徑上的邊數。根的層數定義為 $0$。
高度 (height)：整棵樹中任一節點的最大層數。

舉例：若 Felis 從根走下來要經過 5 條邊，它的層數就是 $5$。若整棵樹最深的節點層數是 $2$，這棵樹的高度就是 $2$。

為什麼要關心高度？因為很多樹演算法的效率取決於高度。一棵平衡良好的樹高度大約是 $O(\log n)$，搜尋會很快；一棵歪斜的樹高度可能變成 $O(n)$，就退化得跟串列一樣慢。

所以記住：層數從 0 算起、是「邊數」；高度是最深的那個層數。

💡

關鍵

層數是從根到該節點的邊數（根為 0），高度是最大層數，決定演算法效率。

🔆

生活妙喻：邊的進入限制 ≈ 每個人只有一位親生母親

除了最初的祖先（根），每個人都恰好由一條邊從父節點連入，就像每個人都只有一位親生母親。

🔆

生活妙喻：層數 ≈ 捷運從起站算過了幾站

層數是從根走過的邊數，就像從起站算你經過了幾段鐵軌；起站本身是第 0 站。

本節字彙

鍵與酬載 (key / payload)

鍵是節點的名字，酬載是節點額外附帶的資料。

🧠 鍵是門牌號碼，酬載是屋子裡住的東西。

高度 (height)

整棵樹中任一節點的最大層數，反映樹有多深。

🧠 高度＝樹最深的那條路有幾條邊。

葉節點 (leaf node)

沒有任何子節點的節點，位於樹的末端。

🧠 樹枝的最末端，長不出更多枝葉了。

關於「根節點」，下列哪一項是它最關鍵的特徵？

某節點從根走下來經過了 3 條邊，它的層數是多少？

在族譜式的樹中，「兄弟 (sibling)」指的是哪些節點？

兩種定義：節點邊定義與遞迴定義

用節點與邊的定義，以及更實用的遞迴定義來精確描述樹與二元樹。

STEP 1

深度探秘

用節點與邊正式定義樹

定義一：節點與邊

有了詞彙，我們可以正式定義樹。第一種定義用節點與邊：

一棵樹由一組節點與一組連接節點對的邊組成，且滿足：

其中一個節點被指定為根節點。
除了根，每個節點 $n$ 都由一條邊從恰好一個其他節點 $p$ 連入，$p$ 是 $n$ 的父節點。
從根到每個節點都有一條唯一路徑。
如果每個節點最多兩個子節點，我們就說這是一棵二元樹 (binary tree)。

邊上的箭頭指出連接的方向（由父指向子）。這個定義很直觀，但接下來那個遞迴定義，寫程式時會更好用。

💡

關鍵

定義一用節點、邊與唯一路徑描述樹；每節點最多兩子即為二元樹。

STEP 2

生活妙喻

俄羅斯娃娃裡還是娃娃

定義二：遞迴定義

第二種定義用遞迴來描述：

一棵樹要嘛是空的，要嘛由一個根加上零或多個子樹組成，而每個子樹本身也是一棵樹。每個子樹的根，用一條邊連到母樹的根。

這就像俄羅斯娃娃：打開一個娃娃，裡面還是一個娃娃；再打開，裡面還是娃娃……每一層都跟整體長得一樣。

樹也是如此：一棵樹的任何一根樹枝（子樹），自己看起來也是一棵完整的樹。

graph TD
  R[根] --> S1[子樹一也是一棵樹]
  R --> S2[子樹二也是一棵樹]
  R --> S3[子樹三也是一棵樹]

看著上圖，我們知道至少有 4 個節點：根加上三個子樹各自的根。但實際可能更多，要往裡看才知道。

💡

關鍵

遞迴定義：樹是空的，或由根加上若干「本身也是樹」的子樹組成。

STEP 3

實用超能力

遞迴定義讓程式碼變優雅

為什麼遞迴定義這麼好用

遞迴定義的威力在於：只要結構是遞迴的，處理它的演算法也能寫成遞迴，而且通常短得驚人。

例如要走訪整棵樹，你只要寫：

def visit(tree):
    if tree is None:        # 基底情形：空樹什麼都不做
        return
    process(tree)           # 處理根
    visit(tree.left)        # 子樹也是樹，遞迴處理
    visit(tree.right)

注意這段程式幾乎就是定義二的直接翻譯：「空樹就停，否則處理根、再處理每個子樹（它們也是樹）」。

後面我們實作堆積、剖析樹、二元搜尋樹時，會一再看到這種「把遞迴定義直接寫成遞迴函式」的優雅模式。先建立這個直覺，後面學起來會很順。

💡

關鍵

遞迴定義讓樹演算法能直接寫成遞迴：基底處理空樹，遞迴步驟處理各子樹。

🔆

生活妙喻：遞迴定義 ≈ 俄羅斯娃娃

打開娃娃裡面還是娃娃，每一層都和整體同構；樹的每個子樹也都是一棵完整的樹。

🔆

生活妙喻：二元樹 ≈ 只能生兩個孩子的家庭

二元樹規定每個節點最多兩個子節點，就像一個限定最多兩個孩子的家庭。

本節字彙

二元樹 (binary tree)

每個節點最多有兩個子節點（左、右）的樹。

🧠 binary＝二，每個節點最多兩條外出邊。

遞迴定義 (recursive definition)

用自己定義自己的方式：樹由根加上若干個本身也是樹的子樹組成。

🧠 定義裡又出現了『樹』，這就是遞迴。

依照樹的「遞迴定義」，下列哪一個敘述正確？

什麼條件下我們稱一棵樹為「二元樹」？

為什麼遞迴定義在寫樹的演算法時特別好用？

02

親手實作二元樹

用 [根, 左子樹, 右子樹] 的巢狀串列來表示二元樹，並寫出操作函式。

串列的串列表示法

用 [根, 左子樹, 右子樹] 的巢狀串列來表示二元樹，並寫出操作函式。

STEP 1

深度探秘

用三格的串列裝下一棵樹

一個串列，三個位置

第一種實作二元樹的方式叫「串列的串列 (list of lists)」。核心想法很簡單：用一個有三個位置的串列來代表一個節點：

位置 [0]：根節點的值
位置 [1]：左子樹（本身也是一個這種三格串列）
位置 [2]：右子樹（同上）

例如這棵樹：

my_tree = ['a',                  # 根
            ['b',                # 左子樹
              ['d', [], []],
              ['e', [], []]],
            ['c',                # 右子樹
              ['f', [], []],
              []]]

要取用子樹就用一般的串列索引：my_tree[0] 是根、my_tree[1] 是左子樹、my_tree[2] 是右子樹。空的 [] 代表沒有子樹。一個有值且兩個子樹都空的串列，就是一個葉節點。

💡

關鍵

用 [根, 左子樹, 右子樹] 的三格串列表示節點，子樹本身也是同樣的三格串列。

STEP 2

生活妙喻

結構本身就會遞迴

自我相似的盒子

這個表示法最妙的地方是：結構本身就是遞迴的。代表子樹的那個串列，格式跟代表整棵樹的串列一模一樣——都是「值、左、右」三格。

這就像一個分隔成三格的便當盒：第一格放主菜（根），另外兩格各放一個一模一樣的小便當盒（左、右子樹），打開小盒又是三格……

而且它還能輕鬆推廣到「多元樹」：如果一個節點不只兩個子節點，再多塞幾個子串列進去就行。

graph TD
  a[a 根] --> b[b]
  a --> c[c]
  b --> d[d]
  b --> e[e]
  c --> f[f]

上圖這棵樹，就對應前一頁那個巢狀串列。看圖、看串列，兩者結構完全吻合。

💡

關鍵

子樹串列的格式與整棵樹相同，結構自我相似，而且容易推廣到多元樹。

STEP 3

實用超能力

寫出操作函式

用函式操作這個串列樹

我們不另外定義類別，只寫一些函式把普通串列當樹用。建構與插入左子節點如下：

def binary_tree(r):
    return [r, [], []]

def insert_left(root, new_branch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1, [new_branch, t, []])
    else:
        root.insert(1, [new_branch, [], []])
    return root

關鍵巧思在 insert_left：先把目前的左子樹取出來 t。如果它非空（len(t) > 1），就建立新節點、把舊的左子樹當成新節點的左子，再裝回去——也就是把舊子樹往下推一層。

insert_right 對稱地處理右邊。再加上 get_root_val、set_root_val、get_left_child、get_right_child 這些存取函式，就能完整地建構與走訪這棵串列樹了。

💡

關鍵

insert_left 取出舊左子樹，把它推到新節點底下，再插回位置 1。

🔆

生活妙喻：串列的串列 ≈ 三格便當盒裡再放小便當盒

主格放根的值，另外兩格各放一個格式相同的小便當盒（左右子樹），層層相套。

🔆

生活妙喻：插入時把舊子節點往下推 ≈ 排隊插隊把後面的人往後推

在父與舊左子之間插入新節點時，舊左子被推到新節點下方一層，而不是被丟掉。

本節字彙

串列的串列 (list of lists)

用 [根, 左子樹, 右子樹] 的巢狀串列表示二元樹的方法。

🧠 一個串列裡又裝串列，三格一組。

葉節點的串列形式

形如 [值, [], []]，有值但兩個子樹都是空串列的節點。

🧠 兩格都空空如也，就到末梢了。

在串列的串列表示法中，`my_tree[2]` 代表什麼？

下列哪一個串列表示一個葉節點（值為 'x'）？

`insert_left` 在目前已有左子樹的情況下做了什麼？

節點與參照表示法

用 BinaryTree 類別，以 left_child 與 right_child 參照來表示樹，更貼近物件導向。

STEP 1

深度探秘

每個節點都是一個物件

用類別與參照表示樹

第二種實作方式叫「節點與參照 (nodes and references)」，更貼近物件導向的思維。我們定義一個 BinaryTree 類別，每個節點是一個物件，內含：

key：根節點的值
left_child：對左子節點物件的參照（一開始是 None）
right_child：對右子節點物件的參照

class BinaryTree:
    def __init__(self, root):
        self.key = root
        self.left_child = None
        self.right_child = None

重點是：left_child 與 right_child 會變成指向其他 BinaryTree 實例的參照。當我們插入一個左子節點，就建立另一個 BinaryTree 物件，並讓根的 left_child 指向它。本章接下來都會用這種表示法。

💡

關鍵

每個節點是一個 BinaryTree 物件，left_child/right_child 是指向其他節點物件的參照。

STEP 2

生活妙喻

便利貼上寫著下一張的位置

參照就像便利貼上的指路

想像每個節點是一張便利貼，上面寫著自己的值，還寫著「左邊那張貼在哪裡、右邊那張貼在哪裡」。這個「貼在哪裡」就是參照——它不是子節點本身，而是指向子節點的箭頭。

graph TD
  a[a key] --> b[b left_child]
  a --> c[c right_child]

插入時要分兩種情況：

沒有左子：直接建一個新節點，讓 left_child 指向它。
已有左子：建新節點，把舊的左子接到新節點的 left_child，再讓自己指向新節點——也就是把舊子節點往下推一層，跟串列版的巧思一模一樣。

def insert_left(self, new_node):
    if self.left_child == None:
        self.left_child = BinaryTree(new_node)
    else:
        t = BinaryTree(new_node)
        t.left_child = self.left_child
        self.left_child = t

💡

關鍵

插入分兩種情況：沒有子節點就直接接上，已有子節點就把舊的往下推一層。

STEP 3

實用超能力

子節點也是一棵完整的樹

任一子節點本身也是樹

補上存取方法後，類別就完整了：

def get_left_child(self):
    return self.left_child
def get_right_child(self):
    return self.right_child
def set_root_val(self, obj):
    self.key = obj
def get_root_val(self):
    return self.key

來建一棵小樹試試：

r = BinaryTree('a')
r.insert_left('b')
r.insert_right('c')
print(r.get_left_child().get_root_val())   # b
r.get_right_child().set_root_val('hello')
print(r.get_right_child().get_root_val())  # hello

注意 r.get_left_child() 回傳的本身就是一個 BinaryTree 物件，所以你可以對它再呼叫 get_root_val()、甚至再 insert_left()。

這正呼應了遞迴定義：任一子節點本身也是一棵完整的二元樹。這個性質讓後面的遞迴演算法寫起來特別自然。

💡

關鍵

存取方法回傳的子節點本身是 BinaryTree 物件，可繼續對它操作，呼應遞迴定義。

🔆

生活妙喻：參照 (reference) ≈ 便利貼上寫著下一張貼在哪

left_child 不是子節點本身，而是指向子節點物件的箭頭，就像便利貼上指路的字條。

🔆

生活妙喻：插入時把舊子節點下推 ≈ 在父與子之間塞進一個中間人

已有左子時，新節點成為中間人，舊的左子被掛到新節點底下，整體往下移一層。

本節字彙

參照 (reference)

指向另一個物件的連結；這裡用來讓父節點指向子節點物件。

🧠 不是東西本身，而是指向它的箭頭。

BinaryTree 類別

封裝 key 與左右子節點參照的節點物件，子節點也是同類別實例。

🧠 一個物件＝一個節點，左右各掛一個同類物件。

在節點與參照表示法中，`left_child` 屬性存的是什麼？

對一個「已經有左子節點」的節點呼叫 `insert_left('x')`，結果是什麼？

`r.get_left_child()` 回傳的東西，為什麼可以接著呼叫 `.get_root_val()` 或 `.insert_left()`？

03

優先佇列與二元堆積

認識優先佇列，以及為什麼用二元堆積能比排序串列更有效率。

優先佇列與二元堆積的概念

認識優先佇列，以及為什麼用二元堆積能比排序串列更有效率。

STEP 1

深度探秘

依優先序而非到達順序

不照先來後到，照優先序

之前學的佇列 (queue) 是先進先出 (FIFO)：誰先排隊誰先出。優先佇列 (priority queue) 也是從前端取出，但「誰在前端」不是看誰先到，而是看優先序：

最高優先序的項目永遠在最前面，最低優先序在最後面。
因此 enqueue（加入）一個新項目時，它可能會一路插到最前面。

你可能會想：用排序加串列不就好了？確實可以，但：

在串列中插入是 $O(n)$
對串列排序是 $O(n \log n)$

我們可以做得更好。經典做法是用一種叫二元堆積 (binary heap) 的資料結構，它能讓 enqueue 與 dequeue 都只要 $O(\log n)$。

💡

關鍵

優先佇列依優先序取出；二元堆積讓加入與取出都達到 O(log n)，勝過排序串列。

STEP 2

生活妙喻

醫院急診的檢傷分類

急診室不是先到先看

優先佇列最貼切的比喻是醫院急診的檢傷分類。你不是按掛號順序看診，而是按病情嚴重程度：心臟病發的人就算最後到，也會被立刻推到最前面；輕微感冒的人就算先到，也得等。

這就是優先佇列：到達順序不重要，優先序才決定誰先被處理。

二元堆積有兩種常見變體：

變體	誰在最前面
最小堆積 (min heap)	最小的鍵
最大堆積 (max heap)	最大的鍵

本章我們實作最小堆積（min heap），最大堆積留作練習。要注意：「最小」或「最大」是指鍵值，可以把鍵想成優先序的數字（例如越小越緊急）。

💡

關鍵

優先佇列像急診檢傷：嚴重程度（優先序）決定先後；堆積分 min 與 max 兩種。

STEP 3

實用超能力

看堆積怎麼運作

不管怎麼放進去，最小的先出來

二元堆積的介面長這樣：

BinaryHeap()：建立空堆積
insert(k)：加入一個項目
find_min()：回傳最小鍵的項目，但不移除
del_min()：回傳並移除最小鍵的項目
is_empty()、size()、build_heap(list)

來看一段示範：

bh = BinHeap()
bh.insert(5)
bh.insert(7)
bh.insert(3)
bh.insert(11)
print(bh.del_min())  # 3
print(bh.del_min())  # 5
print(bh.del_min())  # 7
print(bh.del_min())  # 11

注意：不管我們以什麼順序丟進去（5、7、3、11），del_min 每次都取出當前最小的。這正是優先佇列要的行為。下一節我們就來看它內部如何用一個串列就辦到這件事。

二元堆積在下一章的圖演算法（如最短路徑）會非常有用，先打好底子。

💡

關鍵

不論插入順序為何，del_min 每次都取出當前最小鍵，正是優先佇列的核心行為。

🔆

生活妙喻：優先佇列 ≈ 急診室檢傷分類

病人不是按到達順序看診，而是按病情嚴重程度；最緊急的就算最後到也先被處理。

🔆

生活妙喻：二元堆積勝過排序串列 ≈ 與其每次全部重排，不如只調整一條路徑

排序串列每次插入要 O(n) 或排序 O(n log n)；堆積只沿一條路徑調整，達到 O(log n)。

本節字彙

優先佇列 (priority queue)

依項目優先序而非到達順序取出的佇列，最高優先在最前。

🧠 急診排隊，重症先看。

二元堆積 (binary heap)

用來高效實作優先佇列的資料結構，enqueue 與 dequeue 皆 O(log n)。

🧠 形狀像樹，骨子裡只是一個串列。

最小堆積 (min heap)

最小鍵永遠在最前端的堆積；最大堆積則相反。

🧠 min＝小，最小的當老大坐最前面。

優先佇列與普通佇列最關鍵的差別是什麼？

用「排序串列」實作優先佇列，為什麼效率不夠好？

依序執行 `insert(5)`、`insert(7)`、`insert(3)`、`insert(11)` 後，第一次 `del_min()` 回傳什麼？

結構性質與順序性質

完全二元樹可用單一串列表示，並用 2p、2p+1 找子節點；堆積順序性質保證父節點不大於子節點。

STEP 1

深度探秘

完全二元樹與一個串列

結構性質：完全二元樹

要讓堆積有效率，我們利用二元樹的對數特性，但前提是要讓樹平衡。堆積的做法是維持一棵完全二元樹 (complete binary tree)：

每一層都被節點填滿，唯一的例外是最底層，而最底層也要從左到右依序填。

完全二元樹有個迷人的性質：可以只用一個串列來表示，不需要節點與參照，也不需要串列的串列。因為樹是完全的，我們能用簡單的數學在串列中找到父子關係：

父節點在位置 $p$，它的左子在位置 $2p$，右子在位置 $2p+1$。
反過來，某節點在位置 $n$，它的父節點在位置 $n // 2$（整數除法）。

這幾條算式讓我們只用一個串列，就能在堆積裡快速上下移動。

💡

關鍵

完全二元樹每層填滿、底層從左到右填，可用單一串列表示：左子 2p、右子 2p+1、父 n//2。

STEP 2

生活妙喻

整齊的劇院座位編號

像劇院座位一樣有規律

把完全二元樹想成一座從上往下、從左往右坐滿的劇院：第一排坐 1 個（根），第二排坐 2 個，第三排坐 4 個……每排都坐滿才開放下一排，且每排都從左邊開始坐。

因為座位這麼規律，我們只要知道座號（串列位置），就能用算式直接算出父母與子女的座號——完全不必畫箭頭。

graph TD
  p1[位置 1 根] --> p2[位置 2 左子]
  p1 --> p3[位置 3 右子]
  p2 --> p4[位置 4]
  p2 --> p5[位置 5]
  p3 --> p6[位置 6]

注意：堆積串列的第 0 格放一個沒用到的 0，從位置 1 才開始放真正的資料。這個小技巧讓 $2p$、$2p+1$、$n//2$ 這些整數除法算得乾淨俐落。

💡

關鍵

完全二元樹像從上到下、從左到右坐滿的劇院，座號即串列位置，父子關係可直接算。

STEP 3

實用超能力

堆積順序性質

順序性質：父不大於子

光有形狀還不夠，堆積還要維持堆積順序性質 (heap order property)：

在最小堆積中，對於每個節點 $x$ 及其父節點 $p$，$p$ 的鍵小於或等於 $x$ 的鍵。

換句話說，父節點永遠不會比子節點大。這條規則一路傳遞下去，就保證了整棵樹的最小值一定在根（位置 1）——這就是為什麼 find_min 可以是 $O(1)$，直接看根就好。

注意堆積順序性質只規範父子之間，不規範兄弟之間的大小，也不像二元搜尋樹那樣左小右大。所以同一組資料可以對應多種合法的堆積排列。

把兩件事合起來記：

性質	規範什麼	帶來什麼好處
結構性質	形狀是完全二元樹	高度約 log n、可用串列表示
順序性質	父鍵 ≤ 子鍵	最小值永遠在根

💡

關鍵

堆積順序性質要求父鍵不大於子鍵，於是最小值必在根，find_min 為 O(1)。

🔆

生活妙喻：完全二元樹 ≈ 從上往下、從左往右坐滿的劇院

每排坐滿才開放下一排，且都從左邊開始坐，只有最後一排可能沒坐滿。

🔆

生活妙喻：堆積順序性質 ≈ 金字塔的管理階層

每位主管（父）的『緊急程度數字』都不大於其下屬（子），所以最緊急的（最小值）一定坐在金字塔頂端。

本節字彙

完全二元樹 (complete binary tree)

每層都填滿、僅最底層可能未滿且從左到右填的二元樹。

🧠 從左到右、從上到下坐滿的劇院。

堆積順序性質 (heap order property)

每個父節點的鍵都小於等於其子節點的鍵（最小堆積）。

🧠 父母永遠不比孩子大，最小的當頭。

父子位置公式

位置 p 的左子在 2p、右子在 2p+1、父在 n 整除 2。

🧠 乘 2 往下、除 2 往上。

在堆積的串列表示法中，位置 $p$ 的節點，其左子節點在哪個位置？

某節點在串列位置 7，它的父節點在哪個位置？

「堆積順序性質」（最小堆積）規定的是什麼？

堆積操作：上浮、下沉與建堆

用 perc_up、perc_down 與 build_heap 維持堆積性質，並理解 build_heap 的 O(n)。

STEP 1

深度探秘

插入靠上浮 perc_up

insert：先附加，再上浮

建構子很簡單：堆積就是一個串列，第 0 格放沒用到的 0，再加一個 current_size：

class BinHeap:
    def __init__(self):
        self.heap_list = [0]
        self.current_size = 0

插入時最快的做法是把新項目附加到串列尾端——這保證仍是完全二元樹（結構性質沒破）。壞消息是它可能破壞順序性質。解法是上浮 (percolate up)：把新項目和它的父節點比較，如果比父節點小就交換，一路往上浮到正確位置。

def perc_up(self, i):
    while i // 2 > 0:
        if self.heap_list[i] < self.heap_list[i // 2]:
            tmp = self.heap_list[i // 2]
            self.heap_list[i // 2] = self.heap_list[i]
            self.heap_list[i] = tmp
        i = i // 2

def insert(self, k):
    self.heap_list.append(k)
    self.current_size += 1
    self.perc_up(self.current_size)

因為只沿著一條路往上，最多走樹的高度層，所以 insert 是 $O(\log n)$。

💡

關鍵

insert 先把新項目附加到尾端（保結構），再用 perc_up 與父節點比較交換往上浮（保順序）。

STEP 2

生活妙喻

刪除最小值靠下沉 perc_down

del_min：搬尾端到根，再下沉

最小值就在根（位置 1），取出很容易；難的是取走後怎麼修復。做法分兩步：

把串列最後一個項目搬到根的位置——這維持了完全二元樹的結構，但很可能破壞順序性質。
用下沉 (percolate down) 把這個新根往下推到正確位置。

下沉時每一步都和較小的那個子節點交換，直到它比兩個子節點都小為止。

def perc_down(self, i):
    while (i * 2) <= self.current_size:
        mc = self.min_child(i)
        if self.heap_list[i] > self.heap_list[mc]:
            tmp = self.heap_list[i]
            self.heap_list[i] = self.heap_list[mc]
            self.heap_list[mc] = tmp
        i = mc

def min_child(self, i):
    if i * 2 + 1 > self.current_size:
        return i * 2
    elif self.heap_list[i*2] < self.heap_list[i*2 + 1]:
        return i * 2
    else:
        return i * 2 + 1

為什麼要跟較小的子交換？因為交上去的那個會變成新父節點，必須比另一個子小，才不會又違反順序性質。這就像公司升職：要升就升兩個下屬中比較資深（鍵較小）的，否則又得重來。

💡

關鍵

del_min 把尾端搬到根，再 perc_down 與較小的子節點逐層交換，直到比兩子都小。

STEP 3

實用超能力

建堆 build_heap 的 O(n) 魔法

從一整串資料一次建好堆積

如果手上已有一整個串列，要怎麼變成堆積？直覺做法是逐一 insert，但那要 $O(n \log n)$。更聰明的是 build_heap：

def build_heap(self, a_list):
    i = len(a_list) // 2
    self.current_size = len(a_list)
    self.heap_list = [0] + a_list[:]
    while i > 0:
        self.perc_down(i)
        i = i - 1

關鍵在於從中間往根節點方向、對每個節點做 perc_down。為什麼從 len // 2 開始？因為超過一半位置的節點全是葉節點，沒有子節點，不需要下沉。

令人驚訝的是，這樣建堆只要 $O(n)$，比逐一插入快！直覺是：$\log n$ 來自樹的高度，但 build_heap 大部分的工作發生在接近底部、樹很矮的地方，所以總成本遠低於 $n \log n$。

之後你會在練習中用 build_heap 寫出一個 $O(n \log n)$ 的排序演算法（堆積排序）。

💡

關鍵

build_heap 從中間位置往根對每個節點 perc_down，葉節點免做，總成本只要 O(n)。

🔆

生活妙喻：上浮 perc_up ≈ 氣泡在水中往上冒

新加入的小項目像氣泡，只要比上面的父節點輕（小）就往上冒，直到浮到合適的深度。

🔆

生活妙喻：下沉 perc_down 選較小的子 ≈ 升職要升較資深的下屬

把根往下換時必須和較小（較資深）的子交換，新父才會比另一個子小，避免再度違反順序。

🔆

生活妙喻：build_heap 的 O(n) ≈ 大部分工作都在矮樹叢進行

底層節點又多又矮，下沉沒幾步；高的工作很少。整體加起來只要 O(n) 而非 O(n log n)。

本節字彙

上浮 (perc_up)

把新加入的項目與父節點比較交換，往上移到正確位置的過程。

🧠 小東西像氣泡往上冒。

下沉 (perc_down)

把根上的項目與較小的子節點交換，往下移到正確位置的過程。

🧠 大東西像石頭往下沉。

建堆 (build_heap)

從一整個串列一次建成堆積，只需 O(n) 時間。

🧠 一次到位，比逐個插入更快。

`insert` 為什麼要先把新項目附加到串列尾端，再做 `perc_up`？

`del_min` 取走根之後，為什麼把「最後一個項目」搬到根的位置？

`perc_down` 時為什麼要和「較小的」那個子節點交換，而不是隨便挑一個？

04

樹的應用與走訪

把完全加括號的運算式變成剖析樹，再遞迴求值。

剖析樹：建立與求值

把完全加括號的運算式變成剖析樹，再遞迴求值。

STEP 1

深度探秘

把運算式變成一棵樹

剖析樹是什麼

剖析樹 (parse tree) 能把真實世界的結構（句子、數學運算式）表示成樹。以數學運算式為例，$((7 + 3) * (5 - 2))$ 可以畫成一棵樹：根是 *，左子樹是 +（7 與 3），右子樹是 -（5 與 2）。

樹的階層自然反映了運算順序：要算頂層的乘法，得先算兩個括號裡的加法與減法。先把左子樹算成 10、右子樹算成 3，再相乘得 30。

建立剖析樹用四條規則，逐一讀取詞元 (token)：

讀到 (：在目前節點新增一個左子，往左子下降。
讀到運算子 + - * /：把目前節點的值設為該運算子，新增一個右子，往右子下降。
讀到數字：把目前節點的值設為該數字，回到父節點。
讀到 )：回到父節點。

💡

關鍵

剖析樹把運算式表示成樹，階層反映運算順序；建立時依四條規則處理括號、運算子、數字。

STEP 2

生活妙喻

用堆疊記住回家的路

麵包屑與堆疊

建樹時我們會一直往子節點下降，但「回到父節點」時怎麼知道父節點是誰？樹介面只給我們往下找子節點的方法，沒有往上找父節點的方法。

解法是用一個堆疊 (stack)：每次要下降到子節點前，先把目前節點 push 進堆疊；要回到父節點時，就從堆疊 pop 出來。

這就像走迷宮時沿路撒麵包屑：往深處走時一路留記號，要回頭時照著麵包屑倒著走回去。

flowchart TD
  A[讀左括號 下降到左子 並把目前節點推入堆疊] --> B[讀數字 設值 從堆疊彈出回到父節點]
  B --> C[讀運算子 設值 新增右子並下降 推入堆疊]
  C --> D[讀右括號 從堆疊彈出回到父節點]

程式碼大致如下（節錄）：

if i == '(':
    current_tree.insert_left('')
    p_stack.push(current_tree)
    current_tree = current_tree.get_left_child()
elif i in ['+', '-', '*', '/']:
    current_tree.set_root_val(i)
    current_tree.insert_right('')
    p_stack.push(current_tree)
    current_tree = current_tree.get_right_child()
elif i == ')':
    current_tree = p_stack.pop()

💡

關鍵

用堆疊追蹤父節點：下降前 push 目前節點，回到父節點時 pop，就像撒麵包屑找回家的路。

STEP 3

實用超能力

遞迴求值剖析樹

建好之後，遞迴求值

樹建好後，我們用遞迴來求值。基底情形是葉節點——在剖析樹裡，葉節點一定是運算元（數字），直接回傳它的值。遞迴步驟則是對左、右子節點各自呼叫 evaluate，再把兩個結果套上父節點的運算子。

運算子用一個字典對應到 Python operator 模組的函式：

import operator

def evaluate(parse_tree):
    opers = {'+': operator.add, '-': operator.sub,
             '*': operator.mul, '/': operator.truediv}
    left = parse_tree.get_left_child()
    right = parse_tree.get_right_child()
    if left and right:
        fn = opers[parse_tree.get_root_val()]
        return fn(evaluate(left), evaluate(right))
    else:
        return parse_tree.get_root_val()

以 $(3 + (4 * 5))$ 為例：左子 evaluate 得 3，右子 evaluate 先算 $4 * 5 = 20$，最後 $3 + 20 = 23$。整個過程就是「先算子樹、再合併到根」，與我們後面要學的後序走訪不謀而合。

💡

關鍵

求值的基底情形是葉節點（直接回傳值），遞迴步驟對左右子求值後套上父節點運算子。

🔆

生活妙喻：用堆疊追蹤父節點 ≈ 走迷宮撒麵包屑

深入時沿路留記號（push），要回頭時照麵包屑倒走回去（pop），就能找到父節點。

🔆

生活妙喻：遞迴求值 ≈ 把一團問題拆成左右兩半各自解決再合併

先算出左子樹與右子樹的答案，再用根上的運算子把兩個小答案合成一個大答案。

本節字彙

剖析樹 (parse tree)

把句子或數學運算式的階層結構表示成樹，葉節點為運算元、內部節點為運算子。

🧠 把運算式拆解成樹，運算順序一目了然。

詞元 (token)

拆解運算式後的最小單位：左括號、右括號、運算子或運算元。

🧠 把字串切成一塊塊有意義的小積木。

建立剖析樹時讀到一個運算子（如 `+`），依規則該怎麼做？

建立剖析樹時為什麼需要一個堆疊？

遞迴 `evaluate` 函式的「基底情形」是什麼？

三種走訪：前序、中序、後序

差別只在於拜訪根節點的時機，用遞迴寫起來非常優雅。

STEP 1

深度探秘

差別只在拜訪根的時機

三種走訪，差在何時看根

走訪 (traversal) 是指拜訪樹裡所有節點的固定模式。三種常見走訪的差別，只在於什麼時候拜訪根節點：

前序 (preorder)：先拜訪根 → 遞迴走左子樹 → 遞迴走右子樹。
中序 (inorder)：遞迴走左子樹 → 拜訪根 → 遞迴走右子樹。
後序 (postorder)：遞迴走左子樹 → 遞迴走右子樹 → 最後拜訪根。

注意三者左、右子樹的順序都一樣（先左後右），唯一移動的是「印出/拜訪根」這一行的位置。寫成程式碼時優雅得驚人，因為都是遞迴：

def preorder(tree):
    if tree:
        print(tree.get_root_val())   # 根放最前
        preorder(tree.get_left_child())
        preorder(tree.get_right_child())

把那行 print 往下挪，就變成中序或後序。

💡

關鍵

前序、中序、後序的唯一差別是拜訪根的時機（最前、中間、最後），左右子樹順序相同。

STEP 2

生活妙喻

前序就像從頭讀一本書

把整本書當成一棵樹

把一本書想成樹：書是根，每一章是子節點，每章下面有節，節下面有小節……

如果你想從頭到尾讀這本書，那順序正好就是前序走訪：先看書名（根），再進第一章，章裡先看 1.1、再看 1.2……讀完第一章才回到書、進第二章。

graph TD
  Book[書] --> C1[第一章]
  Book --> C2[第二章]
  C1 --> S11[第 1.1 節]
  C1 --> S12[第 1.2 節]
  C2 --> S21[第 2.1 節]

前序＝先看自己再往下，正是「先讀標題再讀內容」的閱讀順序。

而把走訪寫成「外部函式」（傳入樹當參數）比寫成「方法」更俐落，因為外部函式的基底情形只要檢查 if tree:（樹是否存在）即可；寫成方法則要在呼叫前先檢查左右子是否存在。所以本章其餘走訪都寫成外部函式。

💡

關鍵

前序走訪等同從頭讀一本書的順序：先看標題（根）再依序深入各章節。

STEP 3

實用超能力

後序求值，中序還原運算式

走訪的真實用途

後序走訪和我們上一節的剖析樹求值幾乎一模一樣：先算左子樹、再算右子樹、最後在根用運算子合併。把 print 改成 return，就成了 postorder_eval：

def postorder_eval(tree):
    opers = {'+': operator.add, '-': operator.sub,
             '*': operator.mul, '/': operator.truediv}
    res1 = res2 = None
    if tree:
        res1 = postorder_eval(tree.get_left_child())
        res2 = postorder_eval(tree.get_right_child())
        if res1 and res2:
            return opers[tree.get_root_val()](res1, res2)
        else:
            return tree.get_root_val()

中序走訪則能把剖析樹還原成運算式。只要在走左子樹前印 (、走右子樹後印 )，就能還原出完全加括號的版本：

def print_exp(tree):
    str_val = ""
    if tree:
        str_val = '(' + print_exp(tree.get_left_child())
        str_val = str_val + str(tree.get_root_val())
        str_val = str_val + print_exp(tree.get_right_child()) + ')'
    return str_val

所以走訪不只是「逛一圈」，而是解決求值、還原、排序等真實問題的骨架。

💡

關鍵

後序走訪天生適合求值剖析樹；中序走訪加上括號能還原原始運算式。

🔆

生活妙喻：前序走訪 ≈ 從頭到尾讀一本書

先看書名與章標題（根），再依序深入每一節，正是先根後子的前序順序。

🔆

生活妙喻：三種走訪的差異 ≈ 同一條路線，只改變拍照打卡的時機

左右子樹的行走順序都一樣，只是『在根拍照』的時機放在出發前、中途或回程，就成了前、中、後序。

本節字彙

前序走訪 (preorder)

先拜訪根，再遞迴走左子樹、右子樹。

🧠 pre＝先，根最先被看到。

中序走訪 (inorder)

先走左子樹，再拜訪根，最後走右子樹。

🧠 in＝中間，根夾在左右之間。

後序走訪 (postorder)

先走左、右子樹，最後才拜訪根，常用於求值剖析樹。

🧠 post＝後，根留到最後處理。

前序、中序、後序三種走訪，彼此唯一的差別是什麼？

若想以「從頭到尾讀一本書」的順序走訪一棵代表書本的樹，該用哪種走訪？

為什麼「後序走訪」特別適合用來求值剖析樹？

05

二元搜尋樹與 Map

二元搜尋樹靠 bst 性質：左子樹的鍵都比父小、右子樹都比父大。

Map ADT 與 BST 性質

二元搜尋樹靠 bst 性質：左子樹的鍵都比父小、右子樹都比父大。

STEP 1

深度探秘

用樹來實作鍵值對照表

Map ADT：鍵對應到值

我們之前看過兩種實作 Map（對照表） 的方式：在串列上做二元搜尋，以及雜湊表。這一章用二元搜尋樹 (binary search tree, BST) 當作第三種方式，把鍵 (key) 對應到值 (value)。Map 的介面和 Python 字典幾乎一樣：

Map()：建立空 Map。
put(key, val)：加入鍵值對；鍵若已存在則更新值。
get(key)：依鍵取值，找不到回 None。
del map[key]：刪除鍵值對。
len()：鍵值對數量。
key in map：判斷鍵是否存在。

和堆積不同，這裡我們不在意節點的確切位置，而是想利用二元樹的結構來做有效率的搜尋。

💡

關鍵

二元搜尋樹是實作 Map ADT 的第三種方式，介面像字典，目標是有效率地依鍵搜尋值。

STEP 2

生活妙喻

左小右大的猜數字遊戲

BST 性質：左小右大

二元搜尋樹的核心是 bst 性質：

對每個節點，左子樹裡的所有鍵都比它小，右子樹裡的所有鍵都比它大。

這就像玩猜數字遊戲：對方說「比 50 小」，你就只往左邊找；說「比 50 大」，就只往右邊找——每問一次，搜尋範圍就砍半。

graph TD
  n70[70] --> n31[31]
  n70 --> n93[93]
  n31 --> n14[14]
  n93 --> n94[94]
  n14 --> n23[23]

上圖是依序插入 70、31、93、94、14、23 後的樹。注意這個性質對每一對父子都成立：往任何節點看，它左邊的子孫都比它小、右邊的都比它大。正因如此，搜尋時可以像翻字典一樣不斷縮小範圍。

💡

關鍵

bst 性質：左子樹全部比父小、右子樹全部比父大，搜尋時每步都能砍半範圍。

STEP 3

實用超能力

插入順序決定樹的形狀

插入順序很重要

建立 BST 時，鍵的插入順序會決定樹長什麼樣子。第一個插入的鍵成為根，之後每個鍵都從根開始比較：比目前節點小就往左、大就往右，直到找到一個空位掛上去。

例如依序插入 70、31、93、94、14、23、73：

70 是第一個，成為根。
31 < 70，成為 70 的左子。
93 > 70，成為 70 的右子。
94 > 70 且 > 93，成為 93 的右子。
14 < 70 且 < 31，成為 31 的左子。
23 < 31 但 > 14，成為 14 的右子。

警告：如果你照排序好的順序插入（例如 1, 2, 3, 4, 5），每個都比前一個大，全部往右掛，樹就退化成一條歪斜的串列！這時搜尋效率會從 $O(\log n)$ 掉到 $O(n)$。

所以同樣一組鍵，插入順序不同，可能得到漂亮平衡的樹，也可能得到糟糕的歪斜樹。

💡

關鍵

插入順序決定 BST 形狀；照排序順序插入會退化成歪斜串列，搜尋掉到 O(n)。

🔆

生活妙喻：bst 性質 ≈ 猜數字遊戲

每次得到『比某數大或小』的提示就往對應方向走，搜尋範圍每步砍半，就像 BST 沿左右子樹下降。

🔆

生活妙喻：插入順序影響形狀 ≈ 排隊入座的先後決定座位分佈

先到的人佔據關鍵位置（根），後面的人只能依規則往左或往右找空位，順序不同分佈就不同。

本節字彙

Map ADT

把鍵對應到值的抽象資料型別，支援 put、get、del、len、in 等操作。

🧠 像 Python 字典：給一把鑰匙，找到對應的東西。

二元搜尋樹 (BST)

滿足『左子樹皆小於、右子樹皆大於父節點』性質的二元樹。

🧠 左小右大，搜尋像翻字典。

bst 性質

對每個節點，左子樹所有鍵 < 該鍵 < 右子樹所有鍵。

🧠 向左找小的，向右找大的。

二元搜尋樹的「bst 性質」是什麼？

為什麼 BST 性質能讓搜尋變有效率？

依序插入 70、31、93，得到的 BST 結構是？

BST 的實作與效能

用 BinarySearchTree 與 TreeNode 兩個類別實作，並理解平衡與否對效能的影響。

STEP 1

深度探秘

兩個類別分工合作

為什麼用兩個類別

實作 BST 時，我們用兩個類別分工：

BinarySearchTree：外層門面，持有一個指向根 TreeNode 的參照，還有 size。
TreeNode：真正的節點，存 key、payload，以及 left_child、right_child、parent 參照。

為什麼要分兩個？因為我們必須能處理「空樹」：剛建立時根是 None。外層方法通常先檢查樹是否為空，若有節點就把工作委派給以根為起點的私有遞迴輔助函式（如 _put、_get）。空樹或要刪除根這種特殊情況，才在外層特別處理。

class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.size = 0

TreeNode 還提供 is_leaf()、has_both_children()、is_left_child() 等許多輔助函式，並且明確記錄 parent——這在實作 del 刪除時特別重要。

💡

關鍵

BinarySearchTree 是門面、TreeNode 是節點；分兩類別才好處理空樹，TreeNode 記 parent 方便刪除。

STEP 2

生活妙喻

put 與 get 像翻電話簿

插入與查找：沿路比較

put 從根開始，把新鍵和目前節點比較：比較小往左、比較大往右，直到遇到一個空位（沒有對應的子節點）就把新節點掛上去。插入時把目前節點當作新節點的 parent 傳進去。

def _put(self, key, val, current_node):
    if key < current_node.key:
        if current_node.has_left_child():
            self._put(key, val, current_node.left_child)
        else:
            current_node.left_child = TreeNode(key, val, parent=current_node)
    else:
        if current_node.has_right_child():
            self._put(key, val, current_node.right_child)
        else:
            current_node.right_child = TreeNode(key, val, parent=current_node)

get 更簡單，用同樣的左右判斷邏輯一路找下去，找到相符的鍵就回傳其 payload，走到底還沒找到就回 None。

這就像翻紙本電話簿：翻到中間看看姓氏，太前面就往後翻、太後面就往前翻，每翻一次範圍就縮小一半。

透過 __setitem__、__getitem__、__contains__ 多載運算子，我們就能寫出 my_tree['Fargo'] = 55446 與 'Fargo' in my_tree 這種像字典的語法。

💡

關鍵

put/get 從根沿左右子下降比較鍵，找到空位掛上或找到相符鍵回傳值，像翻電話簿縮小範圍。

STEP 3

實用超能力

效能取決於是否平衡

BST 的效能：平衡是關鍵

BST 的操作成本，取決於從根走到目標所經過的路徑長度，也就是樹的高度。

情況	樹的形狀	put / get / in 的成本
平衡良好	高度約 $\log n$	$O(\log n)$
最差（歪斜）	高度約 $n$	$O(n)$

當鍵以隨機順序插入時，樹通常相當平衡，操作接近 $O(\log n)$，非常快。但若鍵以排序順序插入，樹會退化成一條斜線，操作退化成 $O(n)$，跟普通串列一樣慢。

flowchart TD
  A[插入順序隨機] --> B[樹大致平衡 高度約 log n] --> C[查找快 O log n]
  D[插入順序已排序] --> E[樹歪斜成串列 高度約 n] --> F[查找慢 O n]

這就是為什麼會發展出 AVL 樹這類「自我平衡」的二元搜尋樹：它們在每次插入後自動旋轉調整，保證高度始終維持在 $O(\log n)$，避免退化。

記住核心觀念：BST 快不快，全看它平不平衡。

💡

關鍵

BST 操作成本等於樹高；平衡時 O(log n)，歪斜時退化 O(n)，AVL 樹靠自動旋轉維持平衡。

🔆

生活妙喻：兩個類別分工 ≈ 公司的櫃檯與內部員工

BinarySearchTree 像櫃檯處理『有沒有人在』這類門面問題，再把實際工作轉給內部員工 TreeNode 的遞迴輔助函式。

🔆

生活妙喻：平衡與效能 ≈ 整齊的書架 vs 全堆一疊的書

平衡的樹像分類整齊的書架，幾步就找到；歪斜的樹像把書全疊成一落，只能從頭一本本翻。

本節字彙

TreeNode

BST 的節點類別，存 key、payload 與 left_child、right_child、parent 參照。

🧠 每個節點都記得自己的父母，方便日後刪除。

私有輔助函式 (_put / _get)

由外層方法委派、以某節點為起點遞迴搜尋的內部函式。

🧠 底線開頭，是門面方法私下找來幫忙的工人。

AVL 樹 (AVL tree)

會在插入後自動旋轉以維持平衡、保證 O(log n) 的二元搜尋樹。

🧠 自我平衡的 BST，永遠不讓自己歪掉。

為什麼 BST 的實作要分成 `BinarySearchTree` 與 `TreeNode` 兩個類別？

`_put` 在插入新節點時，為什麼要把 `current_node` 當作 `parent` 傳給新的 `TreeNode`？

當 BST 大致平衡時，`get`（查找）的時間複雜度大約是多少？