# 前言
本篇主要針對 Tree 這個資料結構做基本介紹, 沒有 example code, 無聊沈悶又乏味, 但是看完就會對 Tree 這個資料結構有個大概了解, 當在英文技術文章中出現一些專有名詞時, 也比較不會一臉矇逼。
# Tree 的基本概念
- 在以下的介紹, 一些名詞會以保留英文, 像是 nodes(節點), edges(連結), parent(父母), child(子), siblings(兄弟姐妹), descendent(後代), ancestor(祖先), leaf(樹葉), path(路徑), height(高度), subtree(子樹), level(等級), depth(深度), forest(森林), traverse(遍歷), 等等…
- Tree 是一種很好表現階層的資料結構, 如下圖, 主要由 nodes 以及 edges 所構成
- 下圖中的每個節點, 像是 A, B, C, 稱為 nodes, 抑或 vertices, 而連接 nodes 之間的線, 稱為 edges
- Tree 不像 linked list, 並沒有循環的概念
- 兩個相同 parent 的 nodes 之間不會有 edges 存在
- 除了 top node 之外, 每個 node 都會有一個 parent node
- top node 又稱為 root node, 而每個 tree 都只會有一個 root node
- 每個 node 可以有 0 個或多個 child node
- 下圖中, A 為 root node, 而 B, C, D 為 A 的 child node, 也可以說 A 是 B, C, D 的 parent node
- B, C, D 彼此互為 siblings, 因為他們都是 A 的 child nodes
- 沒有 child nodes 的 node 又稱為 leaf, 如上圖中的 K, L, F, G, M, I, J, leaf 又稱為 external(外部) node 或 terminal(終點) node
- 除了 root 之外, 且至少有一個 child node 的 nodes, 又稱為 internal(內部) node
- 上圖中, 如果從 C node 持續的往下尋找, 可以找到 M node, 因此 M 為 C 的 Descendent
- 上圖中, 如果從 L node 持續的往上追朔, 可以找到 B node, 因此 B 為 L 的 Ancestor
- 一個 node 的 child node 總數量, 又稱為 Degree, 如上圖, A 的 degree 為 3, B 的 degree 為 1, C 的 degree 為 3
- 從一個 node 到另外一個 node 經過的 nodes 與 edges 的順序又稱為 Path, 而 path 的長度為經過的 node 總數量, 如上圖 A - M 會經過的 node 為 A-C-H-M, 所以此 path 的長度為 4
- Level 又被來形容 node 是第幾代的, A 的 level 為 0, B, C, D 的 level 為 1, 以此類推
- node 內用來被搜尋用的 value, 又稱為 Keys
# 不同類型的 Tree
# Binary Tree (二元樹)
Binary tree 算是最基本的 tree 結構, 每個 node 最多只能有兩個 child node, 又稱為 left node 以及 right node, 如下示意圖：
# Binary Search Tree (二元搜尋樹)
Binary search tree 是 binary tree 的一種特別型態, child node 的限制與 binary tree 相同, 不同的是, 每個 node 會以排列過的方式儲存, 排列規則如下：
一個 node 必須比它的 left child node 大或相等, 而比它的 right child node 小, 每個 node 都必須要符合這個規則
因為每個 node 都以特別的順序排列, 因此從 binary search tree 中搜尋特定 node 的演算法又被稱為 binary search algorithm (二元搜尋演算法), 它通常會比 linear search (線性搜尋) 更有效率
如下示意圖:
# Self-balanced Binary Search Tree (平衡樹)
self-balanced binary search tree, 又稱為 height-balance binary search tree, 靠名字有夠長, 是 binary search tree 的一種特殊類型, 差異在於它會自動調整 node 的排列, 以讓它自身的 height 盡可能的小, 請參考 示意圖 如下：
height-balanced binary search tree 的效率會比一般的 BST 還好, 下列列出一些比較熱門的 self-balanced binary search tree 一些不同實作:
- AA tree
- AVL tree
- Red-black tree
- Scapegoat tree
- Splay tree
- 2-3 tree
- Treap
# AVL tree (AVL 樹)
上面有提到, AVL tree 是 self-balancing binary search tree 的一種, 規則是, 每一個 node 的兩個 child subtree(子樹) 的高度差最大為 1, 以下為示意圖：
# Red-black tree (紅黑樹)
紅黑樹是 self-balanced binary search tree 的一種, 但有著一些特別的屬性: 顏色。 每個 node 都額外儲存一些資訊, 紅色或黑色。 就像 AVL tree, red-black tree 也被使用在即時應用上, 因為它的平均以及最差時間複雜度都是 O(log n), 以下為示意圖:
# B-tree (B 樹)
B-tree 是一種 self-balanced, 特別類型的 binary tree, 跟 self-balanced binary search tree 的最大不同之處在於 B-tree 可以擁有不限數量的 child node, 而不是只限兩個。 B-tree 常被用在處理大量的資料中, 主要使用在檔案系統以及資料庫, 其時間複雜度為 O(log n)
# K-way tree (K 元樹)
K-way tree 是一種特別的樹, 其 node 可以有最多 K 個 child node, 又稱為 N-ary tree 或 M-ary tree
可以說, binary tree 是一種 N 為 2 的 N-ary tree
# 複雜度
# 參考資料
PHP 7 Data Structures and Algorithms: Implement linked lists, stacks, and queues using PHP
留言