Tree
樹狀結構（Tree）像大自然中的樹木一樣，呈現階層化（Hierarchical）的分支結構，可看作是 Graph 的其中一種形式。
在日常生活中，電腦的「資料夾路徑」或公司的「組織架構圖」，本質上都是一棵樹。
專有名詞
以下是 Tree 常見的專有名詞：
- 節點（Node）：基本單元，包含資料本身以及指向子節點的指標。
- 父節點（Parent）/ 子節點（Child）：上下層有連線關係的節點。上層是父，下層是子。
- 根節點（Root）：最頂端的節點，一棵樹只會有一個根，而這個根沒有父節點。
- 兄弟節點（Siblings）：擁有「同一個父節點」的同層節點。
- 葉節點（Leaf / External Node）：最底層、沒有任何子節點的末端節點。
- 子樹（Subtree）：由某個節點及其所有後代節點所組成的局部樹狀結構。
- 高度（Height）/ 深度（Depth）：
- 深度：從根節點走到該節點的步數（根節點深度為 0）。
- 高度：從該節點走到最深葉節點的最長步數。整棵樹的高度即為根節點的高度。
適用情況
- HTML DOM Tree：
- 網頁的網頁結構在瀏覽器渲染時，就是被解析成一棵 DOM Tree。
- 例如
<html><head/><body><div><div/><body/><html/>，Root 是html，它的子節點有head和body，而body的子節點則有div。
- 檔案系統（File System）：電腦的硬碟路徑（
C:\ > Program Files > Nodejs）就是標準的樹狀階層。 - 字典樹（Trie / Prefix Tree）：
- 搜尋引擎或手機打字的「自動完成 / 關鍵字預測」功能。
- 把英文字母一個一個串成樹狀，輸入 "ap" 就會順著分支找到 "apple", "application"。
- 路由演算法（Routing Protocols）：網路封包在路由器之間傳遞時，會使用生成樹協定（STP）來尋找最短路徑並避免網路無窮迴圈。
常見種類
這邊只介紹刷題最常見的 Tree，其他還有平衡樹和 B Tree 等等，有興趣可以自己搜尋。
- 二元樹（Binary Tree）：最基礎的樹，規定每個節點最多只能有兩個子節點（通常稱為左子節點與右子節點）。
- 二元搜尋樹（Binary Search Tree, BST）：
- 比起 Binary Tree 更多了一個嚴格規定：任何節點的左子樹資料都比自己小，右子樹資料都比自己大。
- 這種結構讓找資料的速度變得非常快。
BST 嚴格遵守左節點比較小，右節點比較大的規則
[ 50 ] <-- 根節點 (Root)
/ \
/ \
[ 30 ] [ 70 ]
/ \ / \
/ \ / \
[ 20 ] [ 40 ][ 60 ] [ 80 ]
Binary Search Tree 的實作
一個 Binary Search Tree 由數個 Node 組成。
class Node {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
Binary Search Tree 的每個 Node 都嚴格遵守左子節點比較小，右子節點比較大的規則。
class BinarySearchTree {
constructor() {
this.root = null; // 根節點，初始化為空值
}
// 1. 插入新值：O(log n)
insert(val) {
const newNode = new Node(val);
// 如果樹是空的，新節點直接成為根節點
if (!this.root) {
this.root = newNode;
return this;
}
let currentNode = this.root;
while (currentNode) {
// 依據 BST 定義，不允許重複的值存在
if (val === currentNode.val) return undefined;
// 值大於目前節點，往右走
if (val > currentNode.val) {
if (!currentNode.right) {
currentNode.right = newNode; // 找到空位，插入並結束
return this;
}
currentNode = currentNode.right; // 右邊有人，繼續往下一層走
}
// 新值小於目前節點，往左走
else {
if (!currentNode.left) {
currentNode.left = newNode; // 找到空位，插入並結束
return this;
}
currentNode = currentNode.left; // 左邊有人，繼續往下一層走
}
}
}
// 2. 尋找特定值：O(log n)
find(val) {
if (!this.root) return false;
let currentNode = this.root;
while (currentNode) {
if (val < currentNode.val) {
currentNode = currentNode.left; // 目標較小，往左搜尋
} else if (val > currentNode.val) {
currentNode = currentNode.right; // 目標較大，往右搜尋
} else {
return currentNode; // 找到了，回傳該節點
}
}
return false; // 找遍了都沒找到
}
// 3. 刪除特定值：O(log n)
remove(val) {
if (val === null || val === undefined) return undefined;
// 透過輔助方法更新根節點（因為根節點也有可能被刪除）
this.root = this.removeHelper(val, this.root);
}
// 刪除的遞迴輔助方法
removeHelper(val, currentNode) {
// 走到盡頭都沒找到，回傳 null
if (!currentNode) return null;
// 尋找階段：根據大小關係繼續往左或往右遞迴找尋
if (val < currentNode.val) {
currentNode.left = this.removeHelper(val, currentNode.left);
return currentNode;
} else if (val > currentNode.val) {
currentNode.right = this.removeHelper(val, currentNode.right);
return currentNode;
}
// 刪除階段：已找到目標節點 (val === currentNode.val)
// 情況 1：目標是「Leaf」（沒有任何子節點），直接刪除
if (!currentNode.left && !currentNode.right) {
return null;
}
// 情況 2：目標「只有右子節點」，直接用右子節點取代自己
else if (!currentNode.left) {
return currentNode.right;
}
// 情況 3：目標「只有左子節點」，直接用左子節點取代自己
else if (!currentNode.right) {
return currentNode.left;
}
// 情況 4：目標「同時有左右子節點」
else {
// 找出右子樹中的「最小值節點」來頂替自己的位置
let minRightChildNode = this.findMinValue(currentNode.right);
currentNode.val = minRightChildNode.val; // 把數值換過去
// 接著在右子樹中，把原本那個用來頂替的節點刪除
currentNode.right = this.removeHelper(minRightChildNode.val, currentNode.right);
return currentNode;
}
}
}
複雜度
| 操作種類 | 平均時間複雜度 | 最差時間複雜度 | 原因說明 |
|---|---|---|---|
| 搜尋資料 (Search) | O(log n) | O(n) | 平均每次都能省掉一半的分支（對數時間）；但若樹嚴重傾斜（歪向一邊），就會退化成像 Linked List 一樣要一筆一筆找。 |
| 新增資料 (Insert) | O(log n) | O(n) | 先搜尋找到對的位置（O(log n)），再放進去（O(1)）。 |
| 刪除資料 (Delete) | O(log n) | O(n) | 找到目標後，還需要處理子節點的接頭問題。 |
遍歷 Tree 的演算法
寫在 Tree Traversal 裡，歡迎前去參考。