分岔的階層結構。二元搜尋樹「左小右大」,每次比較就砍掉一半,查找平均 O(log n)。
O(log n)。
根 root —— 最上面的起點,唯一沒有父節點的那個。
父 / 子 parent / child —— 上下相連的關係;葉 leaf 是沒有孩子的末端節點。
子樹 subtree —— 任一節點連同它底下全部,自成一棵小樹(所以樹的定義本身就是遞迴的)。
深度 / 高度 depth / height —— 從根到某節點走幾層叫深度;整棵樹最深幾層叫高度。二元樹就是每個節點最多 2 個孩子。
每個節點最多 2 個孩子 —— 左 left、右 right。
左子樹全部 < 這個節點;右子樹全部 > 這個節點 —— 而且這條規則對每一個節點都成立,不只根。
神奇結果 —— 中序走訪(左→根→右)剛好由小到大排好序!
查找就像二分搜尋 —— 比目標小往右、大往左,每步砍掉半棵子樹。
O(log n) 插入刪除,兩全其美 —— 前提是樹要夠平衡。中序 Inorder(左→根→右) —— 得到「由小到大」的排序結果,BST 專用招。
前序 Preorder(根→左→右) —— 常用來複製整棵樹。
後序 Postorder(左→右→根) —— 常用來刪除 / 釋放整棵樹(先處理完小孩)。
層序 Level-order(一層一層) —— 用佇列做,就是廣度優先 BFS。
O(n)。實務上用自平衡樹(AVL、紅黑樹)自動保持矮胖,穩定 O(log n)。一層資料夾包著子資料夾,一路往下點才找到檔案 —— 就是樹的階層感。
我心裡一個數你來猜,我只回太大或太小,你每次砍一半 —— 這就是 BST 查找。
一個祖先往下分枝,每個人有父母、有子女,末端沒有子女的就是葉。
這棵 BST 由 [8, 3, 10, 1, 6, 14, 4, 7, 13] 依序插入而成。搜尋就像二分搜尋:紫色是正在比較的節點,綠色是走過的路。比目標大就往左、小就往右,每一步都砍掉半棵子樹。選一個目標,按「下一步」。
從定義節點、建 BST、四種走訪,到找極值、算樹高、刪除節點、驗證合法 BST 等經典題。
❌ 以為 BST 一定 O(log n) —— 照排序資料插入會退化成一條鏈 O(n)。要平衡(AVL / 紅黑樹)才穩。
❌ 驗證 BST 只比父子 —— 不夠!要用「容許範圍」確保整個子樹都符合,不是只看直接的左右孩子(範例 10)。
❌ 遞迴忘了 base case —— 樹的遞迴一定要先處理 root is None,不然會 AttributeError。
❌ 插入沒把結果接回去 —— 要 root.left = insert(root.left, v),不能只呼叫不接回傳值。
[5, 3, 8, 2, 4] 依序插入空 BST,畫出來長怎樣?中序走訪會印出什麼?O(n)?畫一下它的形狀。7 會依序經過哪些節點?搜尋 5 呢(它不在)?把答案打到對話裡,我幫你對。