# 樹的基本性質 Basic Properties of Trees
樹是圖論中一種很常見的圖，在電腦科學中更是不可或缺的一種資料結構。由於其特殊性，相關應用也相當廣泛，是競程不可或缺的題型之一。很多人把樹當作是一門學問獨立出來稱作「樹論」，但嚴格上來說不能這樣稱呼，因為他就是一種特殊結構的圖而已，基本上出了中文競程圈就完全聽不到這種叫法

本文會介紹樹的定義、性質與用途

## 簡介
### 澄清
首先，資工的樹長下圖右邊的樣子 : 根在上、葉在下
||別人覺得你畫這樣有病是正常的 XD||

<center>
<img src="https://hackmd.io/_uploads/rkUYmvlVxl.png" style="margin: 0 auto; display: block; width: 500px">
</center>

### 常見例子
生活中最常遇到的樹通常會有「上對下」的關係，像是祖譜、企業的組織圖等等

<center>
<img src="https://hackmd.io/_uploads/BkJF2lkVxe.png" style="margin: 0 auto; display: block; width: 500px">
</center>

### 電腦中的例子
在儲存檔案資料時，都是使用樹狀結構，因為其特性可以 (比較) 輕鬆找到資料
在資料結構中，只要加入一些特性，就可以更好地儲存/刪除/查詢資料

常見的有 :

- 二元搜尋樹
- 紅黑樹
- B-tree
- Binary Heap
- Binomial Heap
- Fibonacci Heap

還有一些樹，實際上並不存在，但是在抽象的計算機理論中佔有一席之地的樹 :

- Parsing Tree (在 formal language 中，這種樹代表語言產生的「過程」)
- Search Tree (每個節點都代表一個狀態，早期的 AI 很常見)

### 競程會用到的樹
這些不是本篇重點，只稍微提一下名詞 :
- 一般的樹
- 線段樹 (segment tree，用於處理區間問題)
- [Binary Indexed Tree](https://hackmd.io/@ShanC/Fenwick-Tree) (處理區間問題，主要是前綴和)
- [生成樹](https://hackmd.io/@ShanC/minimum-spanning-tree#%E7%94%9F%E6%88%90%E6%A8%B9-Spanning-Tree) (一種很特別的子圖)
- [併查集](https://hackmd.io/@ShanC/dsu) (DSU，一種維護集合的樹狀資料結構)

## 樹的定義與名詞
### 定義
每份資料中，樹的定義都長得有所不同。以下列出幾個常見的定義 :

給定一張 $n$ 節點的圖 $G$ (其中 $n\geq 1$)
A) $G$ 連通且沒有環
B) $G$ 是連通且只有 $n-1$ 條邊
C) $G$ 只有 $n-1$ 條邊且沒有環
D) $G$ 沒有自環且所有點對 $u, v$ 都只存在一條路徑

以上四種定義其實都**互相等價**，證明很簡單，可以自己玩玩看

### 森林 Forest
一張由好幾棵樹組成的圖，每棵樹之間是不連通的。其實把定義 A 當中的「連通」拿掉，就是森林

森林正式的定義 : 無環圖

### 距離 Distance
若一張圖 $G$ 存在 $u, v$ 路徑，則 $d(u, v)$ 為從 $u$ 到 $v$ 的最少的邊數，有時會直接稱為「距離」或是「最短距離」。若 $G$ 則不存在 $u, v$ 路徑，則 $d(u, v)=\infty$ (要看怎麼用)。若 $G$ 為一棵樹，則 $u, v$ 路徑唯一 (根據定義 D)

### 直徑 Diameter
直徑就是所有點對最短距離的最大值 (很饒口沒錯，所以看符號就好)

$max_{u, v\in V(G)} ~d(u, v)$

<center>
<img src="https://hackmd.io/_uploads/r1hwRCyExx.png" style="margin: 0 auto; display: block; width: 500px">
</center>

### 根
一棵樹只會有一個節點作為根，稱作根節點。一棵樹的每個節點都可以是根節點，通常固定下來就不會換 (視情況而定)

### 葉
一棵樹可能有多個葉，稱作葉節點。度數為一 (只有一個鄰居) 的節點，就是葉節點。與根節點不同，一棵樹的葉節點都是固定不變的

有時一個節點可能會同時是根也是葉，視情況而定

<center>
<img src="https://hackmd.io/_uploads/Hkj3k1gVxl.png" style="margin: 0 auto; display: block; width: 500px">
</br>
<p>綠色為葉節點、橘色為根節點</p>
</center>

## 常用的樹的性質

### 深度
與根節點的距離，稱為深度。在很多演算法中，樹的深度決定了複雜度

### 親屬關係
#### 父節點
給定一個節點 $x$，若存在深度比 $x$ 少 $1$ 且與 $x$ 為鄰居的節點，則稱其為 $x$ 的父節點

備註 : 除了根節點之外，每個節點的父節點唯一

#### 子節點
給定一個節點 $x$，若存在深度比 $x$ 多 $1$ 且與 $x$ 為鄰居的節點，則稱其為 $x$ 的子節點

#### 祖先
給定一個節點 $x$，則 $x$ 的祖先為 $x$ 到根節點的路徑上所有的節點 (不包含 $x$)

備註 : 根節點是圖中大家的祖先，且沒有父節點

#### 舉例說明

以下圖為例
- $d$ 為根，深度為 $0$，是大家的祖先
- $e$ 是 $b$、$c$ 的父節點
- $b$、$c$ 是 $e$ 的子節點

<center>
<img src="https://hackmd.io/_uploads/B1rbYJlVge.png" style="margin: 0 auto; display: block; width: 400px"></br>
綠色為葉節點、橘色為根節點
</center>

### 樹的子圖
若一個樹的子圖是不連通的，則為森林，反之則為樹

若特別強調某個節點 $x$ 的後代所形成的樹，則稱為 $x$ 的子樹

## 其他樹的性質
### 樹的每一條邊都是 cut-edge
在一張連通圖中，刪除 cut-edge 可以把圖變得不連通

一個 cut-edge 不能存在於任何環之中 (這是定理，玩玩看)。由於樹中不存在環 (根據定義 A)，不存在一條邊屬於任一個環，因此每條邊都是 cut-edge

### 樹加上一條邊就會形成環
根據定義 D，每個點對都存在唯一的路徑。若對點對加上一條邊，路徑就會不唯一，因而形成環

### 樹是一種二分圖
有關二分圖的定義可以看[這篇](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem#%E4%BA%8C%E5%88%86%E5%9C%96-Bipartite-Graph)

一張圖是二分圖若且唯若不存在奇數環 (這是定理可以自己證證看)。由於樹不存在奇數環 (根據定義 A，根本就沒有環)，因此樹是一種二分圖

### 至少兩片葉子
一個兩個節點以上的樹，至少有兩個葉節點

備註 : 這看起來很 trivial，但是在玩 Prüfer Code 時常被忽略

## 雜談
這邊純屬經驗談。總結來說，上面的說明看起來很容易，但那些定義與名詞都是屬於數學的範疇，我們肉眼看著圖很容易就可以找出想要找的點 (比如說祖先、直徑...等等)。實際上，要在電腦跑起來是一件很費力的事情，這要考量到資料量的大小、複雜度分析與對題目的觀察。這也是數學圖論與演算法圖論差異最大的地方

以我自己的經驗來說，一開始學的是演算法視角的圖論。時常要使用各種複雜的資料結構維護一堆東西，既複雜又麻煩。然而，在我接觸數學視角的圖論後，發現很多東西只要「存在」就好，實際找出「實例」的反而比較少，這也大大地簡化對圖論的想像，尤其是樹

若沒有對圖的想像、沒有數學視角的圖論，在接觸演算法時常常會不知道每個陣列在存什麼鬼。因此我認為先講清楚定義是必須的，之後幾篇筆記在樹的單元中，我也會先講定義 (或證明)，才會開始聊關於演算法及解題的事情

其實主要想講關於樹的主題就只有以下 :
- 圖的生成樹 : [Cayley's formula](https://hackmd.io/@ShanC/Cayleys-Formula-Prufer-Code)、[Matrix-tree theorem](https://hackmd.io/@ShanC/Cayleys-Formula-Prufer-Code#%E5%85%8B%E5%B8%8C%E8%8D%B7%E5%A4%AB%E7%9F%A9%E9%99%A3%E6%A8%B9%E5%AE%9A%E7%90%86-Kirchhoffs-Matrix-Tree-Theorem)、[最小生成樹](https://hackmd.io/@ShanC/minimum-spanning-tree)
- 求一些樹的性質 : 最低共同祖先、直徑、中心、重心
- 把樹簡化成好解的樣子 : 樹壓平、輕重鏈剖分、倍增法

還有就是想抱怨一下，不知道為什麼一堆人都講「樹論」。樹什麼時候從圖論獨立出去變成一個理論了?? 人家歐美的任何競程網站也沒在講 "tree theory" 的啊! 到底哪個天才發明這個詞的啊? 真是亂來ㄟ

----

## 參考資料
- D.B.West - Introduction to Graph Theory 2/e
- [台師大演算法筆記 - tree](https://web.ntnu.edu.tw/~algo/Tree.html)
- CSES Competitive Programmer’s Handbook
- [海大競程 - 圖上遍歷 & 樹論](https://hackmd.io/@LeeShoWhaodian/I2CP2024_Tree#/)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/6/20