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

Gary Huang

Published in

Dublin so code

Apr 29, 2020

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

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

方法：

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

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

在樹中若要從root尋找特定node，一定只存在一條路徑(path)。
每個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則否：

圖三.a：若樹的node只有指向left subtree(左子樹)與right subtree(右子樹)時，又稱為Binary Tree(二元樹)。

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

針對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(樹林)，其定義也很直觀：