Tree

Tree

「樹」。樹是一種很特別的圖。樹的定義是:任兩點之間都相通,並且沒有「環」的圖。「」是指繞圈子的循環路線。

樹的定義對初學者來說或許太過抽象。換個說法吧:一棵樹可想做是由一個點開始,藉由許多條邊不斷地延伸拓展到其他點,而且點和邊都不會重複地被拓展到。

Node

「節點」。進行延伸拓展的點、被延伸拓展到的點,稱作「節點」,也就是說樹上的點都是「節點」。

【註:為了方便,以下仍稱呼「點」。】

Branch

「枝」。延伸拓展所用到的邊稱作「枝」,也就是說樹上的邊都是「枝」。一個點藉由邊往外延伸拓展,稱作「分枝Branching」。

【註:為了方便,以下仍稱呼「邊」。】

Root

「根」。方才提到,一棵樹可想做是由一個點開始分枝──這個點便是「根」。一棵樹上的每一個點都可以作為根。

Leaf

「葉」。在一棵樹上選定根後,由根開始不斷分枝,途中所有無法繼續分枝的點皆是「葉」。

也可以不選定根,這種情況下,只連著一條邊的點都是「葉」。

如果樹上總共只有一個點,那麼此點既是根、也是葉。

Level

「層」。在一棵樹上選定根後,按照拓展的順序(也就是按照每個點離根的距離),可以將樹上的點分層次,使得樹上每一個點都擁有一個層數。如果改變根,那麼分層的結果就會不同。

還有另一種比較少見的分層方式,是設定所有葉在同一層,由葉開始計算層數。

Parent & Child

「父親」與「小孩」。在一棵樹上選定根後,以邊相連的任兩點,靠近樹根者相對地稱作「父親」,靠近樹葉者相對地稱作「小孩」。

一個點的父親,是指與其相鄰的點當中,較此點靠近樹根者,為其父親。父親只會有一個,特例是:樹根沒有父親。

一個點的小孩,是指與其相鄰的點當中,較此點靠近樹葉者,為其小孩。小孩可以是任意多個,特例是:樹葉沒有小孩。

Ancestor & Descendant

「祖先」與「子孫」。在一棵樹上選定根後,一個點的父親、父親的父親、……皆是此點的「祖先」。一個點的小孩、小孩的小孩、……皆是此點的「子孫」。

Directed Tree

在一棵樹上選定樹根後,可以把邊的方向設定成分枝的方向、遠離樹根的方向;也可以把邊的方向設定成朝向樹根的方向,但是這種情況比較少。

Weight

一棵樹可以有權重。當邊擁有權重時,一棵樹的權重等於樹上所有邊的權重總和。

Forest

「森林」。很多棵樹稱作一叢「森林」。只有一棵樹也是「森林」。

樹的特性

1. 樹沒有環。
2. 樹上所有點之間都相連通。
3. 沒有環的圖,就是樹或森林。
   沒有環的圖、連通的圖,就是樹。
4. 任意兩點之間只有唯一一條路徑。
5. 在樹上任意添加一條邊,就會產生環。
6. 在樹上任意刪除一條邊,一顆樹就裂成兩棵樹。
7. 邊數等於點數減一。

UVa 615 599

Tree資料結構

樹是一種圖。圖的資料結構adjacency matrix、adjacency lists可以儲存一棵樹。值得一提的是,一棵樹剛好V個點、V-1條邊,所以adjacency lists的空間複雜度是O(V+E) = O(V)。

順便一提。有根樹(森林),例如DFS Forest、BFS Forest,可以只用一條陣列儲存每個點的父親。

Tree Property

先看個圖片

圖片中省略了點的編號。

parent-child relationship

建立DFS tree或者BFS tree,就可以輕鬆判斷一點是不是另一點的父親。

ancestor-descendant relationship

利用DFS的遍歷順序,就可以輕鬆判斷一點是不是另一點的祖先。

distance

一棵樹、兩點之間的「距離」,就是兩點之間的邊數。

由其中一個點開始進行BFS或DFS即可。

UVa 1599

depth

一棵有根樹、每個點的「深度」,就是根到每個點的距離。

由根開始進行BFS或DFS即可。

遍歷一棵樹與遍歷一張圖,概念上完全相同,實作上則有些微差異:一棵樹,任意兩點之間只有一條路,只要避免走回頭路,就不必記錄每一點是否已經拜訪過。

height

一棵有根樹、每個點的「高度」,就是每個點到下方的葉的最遠距離。

運用Divide and Conquer,移除一棵樹的樹根,形成許多子樹,並分頭處理子樹。

寫成程式碼之後,Divide and Conquer的運作順序,剛好就是DFS的遍歷順序。因此,有人把這樣的程式碼,直接稱為DFS。這用詞並非精準,然而其過程恰是遍歷一張圖,讀取資訊算出答案,故稱之為DFS倒也無妨。

diameter

一張圖的「直徑」,是指最長的最短路徑。

一棵無根樹的「直徑」,恰好是相離最遠的兩個點的距離。

稍微修改一下計算高度的程式碼,就可以順便計算直徑。

UVa 10308 11695 12379

radius(balanced height)

想辦法選定一個樹根,讓樹的高度最小。

樹根位於直徑的中央,能讓樹的高度最小。

演算法請自行參考程式碼,時間複雜度為兩次DFS的時間。

UVa 10459 10939

Kth Ancestor

Kth Ancestor(Level Ancestor)

一棵有根樹,樹上一個點的祖先,通常有許多個。

現在要找到上k輩祖先。往樹根走k步。

演算法(Preprocessing)

建立表格,紀錄每一點的祖先。很容易想到兩種策略:

每個節點做為起點,實施遍歷,找到所有子孫。

每個節點做為起點,走向樹根,找到所有祖先。

建立需時O(V²),查詢需時O(1)。

演算法(Jump Pointer Algorithm)

http://tmtacm.blogspot.tw/2016/01/blog-post_15.html

預先算好每個節點的上一輩祖先、上兩輩祖先、上四輩祖先、上八輩祖先、……,再以二分搜尋找到上k輩祖先。

輩分太高,超出樹根時,可將祖先直接設定成樹根,比較容易實作程式碼。

建立需時O(VlogV),查詢需時O(logV)。

演算法(Ladder Algorithm)

http://tmtacm.blogspot.tw/2016/01/blog-post_15.html

一棵樹分解為數條不重疊路徑:從樹根走到最深的樹葉,形成一條路徑,然後遞迴分解其餘子樹。

預先算好樹上每一點隸屬於哪一條路徑。預先算好每條路徑起點的上一輩祖先、上兩輩祖先、上三輩祖先、……、上高度輩祖先,再以倍增搜尋找到上k輩祖先。

建立需時O(VlogV),查詢需時O(logV)。

演算法(Jump Pointer Algorithm + Ladder Algorithm)

一、找到祖先,輩分是2的次方、略小於k。(若2的次方恰等於k,則演算法結束)。

二、輩分再翻倍,顯然超過k。該祖先高度再翻倍,顯然超過k。該祖先所在路徑保證最深最高,保證其祖先表格含有上k輩祖先。

建立需時O(VlogV),查詢需時O(1)。

演算法(Micro Tree)

Micro Tree沒有實務上的價值,只有理論上的價值。

建立需時O(V),查詢需時O(1)。

演算法(Euler Tour Technique)

https://en.wikipedia.org/wiki/Level_ancestor_problem

建立需時O(V),查詢需時O(1)。

Lowest Common Ancestor

Lowest Common Ancestor

一棵有根樹,樹上兩點的共同祖先當中,離根最遠、深度最深的那一個共同祖先,稱作「最低共同祖先」,常簡稱為LCA。

演算法(Preprocessing)

建立表格,紀錄所有點對的LCA。

知道x與y的LCA,也就知道x的小孩與y的小孩的LCA了。遞迴公式如下:

LCA(x, y) =
 { x                   , if x = y
 { x                   , if x = parent(y)
 { y                   , if y = parent(x)
 { LCA(parent(x), y)   , otherwise
 { LCA(x, parent(y))   , otherwise
LCA(x, y) =
 { x                   , if x = y or x = parent(y)
 { LCA(parent(x), y)   , otherwise

建立需時O(V²),查詢需時O(1)。

UVa 12182

演算法(Tarjan's Algorithm)

用來求出所有點對的LCA。亦得求出部分點對的LCA,必須預先知道是哪些點對,排好順序以利實作。

運用DFS遍歷順序,配合Disjoint-sets Forest,把已經拜訪過的點,依照層級聚合起來,方便找到LCA。

時間複雜度分成三部份討論:

一、DFS:端看樹的資料結構。使用adjacency matrix,時間複雜度是O(V²);使用adjacency lists,時間複雜度是O(V+E)。

二、union:直接考慮p[]的存取次數,總共是O(V)。

三、find:求出所有點對的LCA,每次find最多存取兩次p[],總共是O(V²)。求出部分點對的LCA,p[]的存取次數只降不升,最多是O(V²),最少是O(1)。

總時間複雜度是O(V²)。

宏觀來看,合併連成一線、沒有分枝的邊,以樹根作為起點的單源最短路徑們的長度總和,就是p[]的存取次數上限。

UVa 12238 ICPC 2045

演算法(Jump Pointer Algorithm)

預先算好每個節點的上一輩祖先、上兩輩祖先、上四輩祖先、上八輩祖先、……,再以二分搜尋找到LCA。

輩分太高,超出樹根時,可將祖先直接設定成樹根,比較容易實作程式碼。

建立需時O(VlogV),查詢需時O(logV)。

ICPC 5061

演算法(Heavy-Light Decomposition)

建立需時O(V),查詢需時O(logV)。

請見本站文件「Heavy-Light Decomposition」。

演算法(Euler Tour Technique)

建立需時O(V),查詢需時O(logV)。

請見本站文件「Euler Tour Technique」。

亦得利用「Cartesian Tree」將LCA問題轉換成±1RMQ問題。建立需時O(V),查詢需時O(1)。