資料結構筆記：雜湊表、樹與圖

結構：
Dictionary是以「鍵值-資料對」(Key-Value pair)來描述資料的抽象資料形態(Abstract Data Type)。只要在系統輸入Key，便能找到相對應的Value，這就是Dictionary的基本概念。

特性：
搜尋速度是 O(1)，key 不能重複

方法：

1. 新增資料(insert)，O(1)
2. 刪除資料(delete)，O(1)
3. 查詢資料(search)，O(1)

結構：
樹的最根本特徵就是：在樹的結構裡，只有一個root(樹根)，並且不存在cycle。
此特徵將衍生出另外兩項等價的性質：

1. 在樹中若要從root尋找特定node，一定只存在一條路徑(path)。
2. 每個node只會有一個parent。

特色：
BST 搜尋效率與樹高相當，如果是二元平衡樹是 O(log n)，適合搜尋資料。Heaps 適合快速找出最大最小值 O(1)，但儲存資料都需要花時間，尤其平衡樹。

方法：
1. insert : BST 依照左小右大的規則將新 node 插入下方 node 之下，需要先搜尋，O(log n)
2. delete : BST 依照左小右大的規則搜尋 node 以後刪除，可能找不到 node，O(log n)
3. search : BST 依照左小右大的規則搜尋 node，O(log n)

下列四種結構中，a、b可以視為樹，而c、d則否：

配合圖四，以下將介紹在樹中常見的元素。

針對node / vertex：

• degree(分歧度)：一個node擁有的subtree(子樹)的個數。圖四，A的degree為33，F的degree為22，N的degree為00。
• root(樹根)：樹中最上層的node，也是唯一一個其parent為NULL的node。圖四，A即為root。
• leaf：沒有child/subtree的node稱為leaf node。圖四，G、H、J、K、L、M、N皆為leaf node。
• external node：沒有child的node。因此，leaf node與external node同義。
• internal node：至少有一個child的node，稱為internal node。圖四，A、B、C、D、E、F、I皆為internal node。

針對樹：

• parent ←> child：以pointer說明，被指向者(pointed)為child，指向者(point to)為parent。圖四，A為C的parent，C為A的child；E為K的parent，K為E的child。
• siblings：擁有相同parent的node們，互相稱兄道弟。圖四，B、C、D共同的parent為A，那麼B、C、D即為彼此的sibling。
• descendant(子嗣)：圖四中，站在A，所有能夠以「parent指向child」的方式找到的node，皆稱為A的descendant，因此整棵樹除了A以外皆為A的descendant。站在F，能夠以「parent指向child」找到的node有L、M，則稱L、M為F的descendant。
• ancestor(祖先)：圖四中，站在K，所有能夠以「尋找parent」的方式找到的node，皆稱為K的ancestor，因此，E、B、A皆為K的ancestor。
• path(路徑)：由descendant與ancestor關係連結成的edge，例如A-B-E-K、A-C-F-N。
• level：定義root的level為11，其餘node的level為其parent的level加一。
• height of node：某一node與其最長path上之descendant leaf node之間的edge數。例如，F的height為11，D的height為22，leaf node的height為00。
• height of tree：樹的height即為root的height。圖四中，樹的height為A的height，等於33。
• depth：某一node與root之間的edge數。例如，F的depth為22，L的depth為33。

可以想像的是，在樹中的traversal(尋訪)之時間複雜度(time complexity)會與height(樹高)有關。

在圖三(d)中，曾出現Forest(樹林)，其定義也很直觀：

• 由n≥0n≥0棵彼此互斥(disjoint)的Tree(樹)所形成的集合(Set)，即稱為Forest(樹林)。

集合關係

Tree(樹)並沒有限制child/ subtree的個數，理論上可以有多到超過記憶體空間的child node。然而在實務上，較常使用每個node至多只有兩個child的樹，稱為Binary Tree(二元樹)。

從Binary Tree再增加「鍵值(Key)大小規則」，即得到Binary Search Tree(BST，二元搜尋樹)。以BST為基礎，在每個node上添加顏色(紅與黑)用以平衡樹的height，以減短搜尋時間，這種樹稱為Red Black Tree(RBT，紅黑樹)。

常見的平衡樹(balanced tree)還有：AVL tree、2–3–4 tree、Splay tree等等，請參考：Wikipedia：Self-balancing binary search tree。另一個方向，若打破「不能存在cycle」的限制，則從Tree推廣至圖(Graph)。

Graph 圖簡介

Graph 概念跟演算法十分複雜，目前還無法全懂，暫時先筆記一些能夠理解的內容。

有一間大學的計算機科學學位之必修課程，以及與該課程相關的先修科目設計如表一：

表一：某計算機科學學位之必修課程表

第一眼或許不太容易立即由表格獲得修課順序的資訊，因為表格受限於上至下、左至右的格式，只能逐項列出資訊，不容易表達資料與資料間的「先後關係」。

現在換個方式，將具有先後修課順序的課程以線段與箭號連接，若A是B的先修課程，則箭號由A指向B，即可將表一轉換成圖一：

圖一

由圖一，將資料與資料的「先後關係」以「資料節點」與「線段(箭號)」表示，攻讀這門計算機科學學位的修課流程圖便一目了然。

這樣的想法，不只是將表格轉換成對人類視覺上有意義的「圖」而已，對電腦來說，由於以Graph建立之模型能夠保持資料之間的「關係」，使得各種巧妙的演算法能夠在Graph中完成各種任務。

Graph 的定義

在圖一中，每一門課程被視為「資料節點」，且課程與課程之間有「線段(箭號)」連結：

• vertex：稱每一個「資料節點」為vertex(或是node)，並定義所有的vertex所形成之集合(Set)為V或V(G)；
• edge：稱每一個「線段(箭號)」為edge(實際上是用一對vertex表示edge，例如(Vi,Vj)(Vi,Vj)即為連結Vi與Vj的edge)，並定義所有的edge所形成之集合(Set)為E或E(G)；

則Graph定義為V與E所形成的集合，表示成G(V,E)。

再根據edge是否具有「方向性」，可以將Graph分成「directed graph(有向圖)」與「undirected graph(無向圖)」：

• directed graph(有向圖)：edge的方向性表示資料間的關係，若vertex(A)與vertex(B)之關係是「單向的」，那麼連結vertex(A)與vertex(B)的edge即具有方向性。
• 以圖一中的課程與其先修科目為例，vertex(Data Structures)是vertex(Analysis of Algorithm)的先修課程，相反則否，因此，連結兩個vertex之edge具有方向性，而所有vertex與edge形成之集合即為directed graph；
• undirected graph(無向圖)：edge的方向性表示資料間的關係，若vertex(A)與vertex(B)的關係是「雙向的」，那麼連結vertex(A)與vertex(B)之edge就不具有方向性。
• 如圖二中，如果可以開車從玉山抵達太魯閣，就能夠從太魯閣原路折返回到玉山，因此，這兩個地理位置之間的交通路線便不具有方向性。

再看幾個Graph的範例。
圖三(a)中的G1與G2為undirected graph，圖三(b)中的G3與G4為directed graph。

圖三(a)：undirected graph(無向圖)。

圖三(b)：directed graph(有向圖)。

Graph 的應用

1. Minimum Spanning Tree(MST，最小生成樹)：給定一個connected、weighted的undirected graph，要在這個graph中，找到(1)連結所有vertex，而且(2)edge上的weight總和最小的「Tree」。
   例如，鄉公所要鋪路，先以鄉公所為中心(root)，把所有馬路必須到達的地區視為vertex，則路就是edge，那麼，鋪路的目標便是利用最低成本(weight總和最小)將馬路延伸到所有必須抵達的地區，這就是MST的問題。
2. Shortest Path(最短路徑)：顧名思義，最短路徑即是找到vertex(A)與vertex(B)之間「成本」最小的path，例如以Google Map規劃時間成本最小的路線。例如：Single-Pair Shortest Path：從一個vertex，抵達特定的另一個vertex之最短路徑。
3. Network Flow(網路流)：若現在有一個複雜的水管系統，水從入水口流入，經過許多互相連結、且孔徑不一的水管後，從出水口流出，目標是一次流入最大量的水。
   其中可能遇到的問題如：由於水管的孔徑各不相同，若先流過一條半徑只有2公分的水管，則接在其後的水管的半徑即使再大，水流量仍會被半徑2公分的水管所限制，因此整體流量也就受限制。如何分配水流在水管之間的流法，即是Network Flow要處理的問題。

參考資料：
1. hash table intro : http://alrightchiu.github.io/SecondRound/hash-tableintrojian-jie.html
2. tree intro : http://alrightchiu.github.io/SecondRound/treeshu-introjian-jie.html
3. graph intro : http://alrightchiu.github.io/SecondRound/graph-introjian-jie.html