Tree(樹): Intro(簡介)

Posted by Chiu CC on 12 19, 2015


先備知識與注意事項

若熟悉Linked List(連結串列)將會更容易理解樹：Linked list是一維的線性結構(不是往前、就是往後)，樹(與Graph)則推廣成多維的結構。

linkedlist

圖一：A、B、C、D稱為node(節點)，用以代表資料(data)、狀態(state)。
連結各個node之間的連結(link)稱為edge，可能是單方向，或者雙向。

關於Linked list，請參考：

OK Go.

目錄


隨處可見的Tree(樹)

Tree(樹)是用以描述具有階層結構(hierarchical structure)的問題的首選，階層結構意味著明確的先後次序，例如，若要印出ABC三個字母的所有排列組合(permutation)，直覺反射的圖像會是：


fig1.a              fig1.b

圖二：ABC字母排列組合。
視R為樹根(root)，每一個選擇狀態視為node，此即為樹的結構。


圖二的邏輯為：從起點(R)開始，先決定第一個字母，再依序決定第二、第三個字母，並且，在每一次選擇字母時，可能有不止一個可供選擇的字母。最後一共走出六條路徑，得到六種排列組合，而且這六種排列方式只能經由一種唯一的選擇方式(唯一的路徑)產生。
若將起點(R)視為樹根(root)，每一個字母選擇的狀態(例如：A、C、BC、CAB)都視為一個node，這樣的結構便能夠視為一棵樹。

另外如一本書的目錄、族譜、企業的職位關係，甚至是更廣義的「從家門口為起點尋找方圓一公里以內的便利商店」都能夠建立出樹的模型。


那麼，樹最根本的特徵是什麼？

以族譜為例，若定義包龍星是宋世傑的爸爸，那麼包龍星就絕對不能同時又是宋世傑的兒子。

圖三以node與edge描述此關係，並定義箭頭是從父指向子，則：

  • 包龍星指向宋世傑的箭頭表示包為父、宋為子；
  • 宋世傑指向包龍星的箭頭表示宋為父、包為子；

後者的箭頭即違反了最初「包龍星是宋世傑的爸爸」的命題，此即稱為cycle，也就是著名的「雞生蛋」與「蛋生雞」。

cycle

圖三：包龍星若是宋世傑的parent(父)，又同時為其child(子)，即形成cycle。

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

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


還有哪些結構是樹？

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

fig2.a

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

fig2.b

圖三.b：若樹退化成Linked list(連結串列)，仍滿足樹的定義。

fig2.c

圖三.c：在F出現cycle；以及，D有兩個parent node。

fig2.d

圖三.d：一棵樹只能有一個root(樹根)。此圖像又稱為Forest(樹林)。


用以描述一棵樹的元素

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

針對node / vertex：

  • degree(分歧度)：一個node擁有的subtree(子樹)的個數。
    • 圖四，A的degree為\(3\)，F的degree為\(2\)，N的degree為\(0\)。
  • 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。

fig3

圖四：這是一棵普通的樹。

針對樹：

  • 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為\(1\)，其餘node的level為其parent的level加一。
  • height of node：某一node與其最長path上之descendant leaf node之間的edge數。
    • 例如，F的height為\(1\)，D的height為\(2\)，leaf node的height為\(0\)。
  • height of tree：樹的height即為root的height。
    • 圖四中，樹的height為A的height，等於\(3\)。
  • depth：某一node與root之間的edge數。
    • 例如，F的depth為\(2\)，L的depth為\(3\)。

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


定義

以下列出兩種互相等價的Tree(樹)的定義：

A. Tree(樹)是由一個或多個節點所組成的有限集合，並且滿足：

  1. 存在且只有一個稱為root(樹根)的節點；
  2. 其餘的節點可以分割成任意正整數個(包含零個)互斥(disjoint)的集合：\(T_1、...、T_n\)，其中每一個集合也都滿足樹的定義，這些集合又稱為這棵樹的subtree(子樹)。

B. Tree(樹)是由一個或多個nodes/vertices以及edge所組成，而且沒有cycle的集合(set)。

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

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

forest

圖五：Forest(樹林)由多個Tree(樹)所組成，可以用來表示互斥集合(disjoint set)。


程式碼

實務上，要以程式碼實作一棵樹，常用的手法為：先以class TreeNode(或是struct)定義出每顆node能夠指向多少subtree、攜帶哪些資料形態，再以另一個class Tree表示整棵樹，並以root作為樹的存取點：

// C++ code
class Tree;
class TreeNode{
    TreeNode *leftchild;   // 以下表示每一個node有四個pointer指向child
    TreeNode *rightchild;
    TreeNode *whatever;
    TreeNode *works;
    int data1;             // node所攜帶的information
    double data2;
    ...
    friend class Tree;     // 讓class Tree能夠存取TreeNode的private data
};
class Tree{
    TreeNode *root;        // 以root作為存取整棵樹的起點
};


集合關係

Tree(樹)位居承先啟後的重要戰略位置，圖六是常見的與Tree有關的資料結構之集合關係圖：

fig4

圖六：與Tree(樹)相關的資料結構之集合關係。

本篇介紹的Tree(樹)並沒有限制child/ subtree的個數，理論上可以有多到超過記憶體空間的child node。

然而在實務上，較常使用每個node至多只有兩個child的樹，稱為Binary Tree(二元樹)。

從Binary Tree再增加「鍵值(Key)大小規則」，即得到Binary Search Tree(BST，二元搜尋樹)。

以BST為基礎，在每個node上添加顏色(紅與黑)用以平衡樹的height，以減短搜尋時間，這種樹稱為Red Black Tree(RBT，紅黑樹)。

另一個方向，若打破「不能存在cycle」的限制，則從Tree推廣至圖(Graph)。

在接下來的文章將先以縮小集合的方向依序介紹：Binary Tree、BST、RBT，再進入Graph(圖)這個更複雜的主題。


參考資料：


Tree系列文章

Tree(樹): Intro(簡介)
Binary Tree: Intro(簡介)
Binary Tree: Traversal(尋訪)
Binary Tree: 建立一棵Binary Tree
Binary Search Tree: Intro(簡介)
Binary Search Tree: Search(搜尋資料)、Insert(新增資料)
Binary Search Tree: Sort(排序)、Delete(刪除資料)
Red Black Tree: Intro(簡介)
Red Black Tree: Rotation(旋轉)
Red Black Tree: Insert(新增資料)與Fixup(修正)
Red Black Tree: Delete(刪除資料)與Fixup(修正)

回到目錄：

目錄：演算法與資料結構


tags: C++, Intro,