HackMD 完整版請點我

樹（Tree）


基本單位為 Node，且只有一個 Node 是 Root（無人指向的 Node），且不存在任何 Cycle。每個 Node 可以指向多個 Child。

二元樹（Binary Tree）

image
當樹中的每個 Node 都只有兩個 Child，即為 Binary Tree。

二元搜尋樹（Binary Search Tree）

image
若一個二元樹中，所有 Node 都滿足 Node.left.value < Node.value < Node.right.value，就稱為二元搜尋樹。二元搜尋樹有良好的排序特質，可以幫助我們找到想要的資料。

進階 - 紅黑樹（Red Black Tree）

紅黑樹是一種進階的 BST（Binary Search Tree），透過將每個節點塗上紅色或黑色，並在新增或刪除資料時進行適當的結構調整（旋轉子樹），可以維持 BST 的高度不會相差太多，進而在搜尋時能有較好的效率。細節太過複雜這邊暫時跳過，之後有時間 or 有興趣再回來講。

image

進階 - AVL 樹（AVL Tree）

image
AVL Tree 是一種 Binary search tree 實做方式，大部分的實做方式與 BST 一樣，差異在於 AVL tree 在過程中會透過計算並調整樹的結構來讓樹維持平衡，而不會導致 BST 過度傾斜(不平衡），與紅黑樹的目標類似。細節太過複雜這邊暫時跳過，之後有時間 or 有興趣再回來講。

延伸閱讀：資料結構與演算法：AVL Tree

Leetcode

Please try to use both recursion and stack/queue to solve problem 102 and 144. (Hint: For 102(Level-Order) you should use Queue, for 144(Pre-Order) you should use Stack)

Applications

Tools

圖（Graph）


圖比樹的限制更少，給定一群節點與相連的邊，即可稱為圖。邊可以分為有向與無向，節點之間的連結並沒有限制，也因此圖並不像樹有 root、parent、siblings、height 等等屬性，且有可能會有 cycle 的出現。

Graph & Tree 的比較


Tree 可以被看成一種特殊的 Graph，就像 Binary Tree 是一種特殊的 Tree 一樣。

Graph 的表示法

image

Graph 的搜尋

image
最常見、也最常使用的搜尋方法有兩種：BFS 與 DFS。兩者的差異在於搜尋的優先順序不同，並且分別可以使用 Queue 與 Stack 來實作。

廣度優先搜尋（Breadth First Search, BFS）

深度優先搜尋（Depth First Search, DFS）

那 DFS 與 BFS 可以應用在 Tree 上嗎？

因為 Tree 也是 Graph 的一種，所以當然可以，而且非常常用！

延伸閱讀：DFS、BFS 與 Pre-Order、In-Order、Post-Order、Level-Order 的關係

Leetcode

在圖中找環（Cycle）

上面的兩個例子中，都使用 visited 來紀錄該節點是否被拜訪過。因此，在無向圖中，若我們下一個要拜訪的節點的 visited 為 True，那我們就可以知道該圖中有環的存在。那在有向圖中呢？以下圖來說：
image
若我們在右邊的有向圖 b 中，用相同的 DFS 來尋找是否有環，假設第一次尋訪的路徑為 (1,2,4,5)，而第二次尋訪退回到 2 並往下尋訪 (3,4)，我們這時候會發現 visited[4] == True，並且判定該圖有環，但實際上是沒有的。那我們該怎麼做呢？

在往下看之前，先自己想想看喔！

答案：使用三個不同的值來表示每個節點不同的尋訪狀態（黑、白、灰）。黑色代表已經完成搜尋，白色代表還沒搜尋過，灰色代表正在這條 path 上搜尋，等搜尋完成後就會改為黑色。因此，若我們搜尋時遇到灰色節點，就可以知道該圖存在 cycle！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Determine if a directed graph is acyclic
# True: Acyclic; False: Cyclic
graph = ... # adjacency list representation
N = len(graph)
visited = [0] * N
def checkNoCycle(node):
    if visited[node] == -1: # gray, currently visiting
        return False
    elif visited[node] == 1: # black, done visiting
        return True
    else: # white, not visited yet (visited[node] == 0)
        visited[node] = -1
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        visited[node] = 1
        # print(node)
        return True

補充：The purpose of grey node in graph depth-first search

連通分量（Connected Components）

image
ConnectedComponent4

補充：Connected Components in an Undirected Graph
補充：Strongly Connected Components
補充：Tarjan 演算法與 Kosaraju 演算法

Leetcode

延伸閱讀：