---
# System prepended metadata

title: 樹與二元樹
tags: [樹與二元樹, 資料結構]

---

[toc]
# 樹與二元樹
## Tree
### Tree 定義
由 $\ge 1$ 個 nodes 所形成之集合，不可以為空，並且滿足
- 至少有一個特殊 node 稱為 root
- 其餘 node 分為 $T_1、T_2、T_3 \ ...\ T_m$ 之互斥集合，即為 root 之子樹

### Tree 表示方式
- **用 linked list**
    | data | link 1 | link 2 | link 3 | ... | link k |
    |--|--|--|--|--|--|
    :::danger
    極度浪費 linking space
    共 $n*k$ 個 link ，有用的只有 $n-1$ 個
    :::
- **Leftmost Child Next Right Sibling**
    - 左子右兄弟 (Tree 化為 Binary Tree)
    - | data | child | sibling |
        |--|--|--|
- **括號法**
    以 父(子子子子子...) 的方法，可以 nested
    
### Tree 其他考題
- node level 值
    - root level 為 1
- forest 是由 $\ge 0$ 棵互斥的 trees 所形成的集合 (forest 可以為空)

## Binary Tree
### Binary Tree 定義
可以為空，若不為空，則滿足
- 有 root 及 左右子樹
- 左右子樹也是 Binary Tree

### Binary Tree 種類
- Skewed Binary Tree
    - Left Skewed Binary Tree
    - Right Skewed Binary Tree
- Full Binary Tree
    - 具有最多 node 數
- Complete Binary Tree
    - 高度 k，總 node 數為 n，滿足 $2^{k-1}-1\lt n \le 2^{k}-1$
    - node 編號要由上而下，由左而右依序增長
    - 一個 Complete Binary Tree 具有 n 個 nodes，若某 node 編號為 i
        - 其左子點編號為 $2i$
        - 其右子點編號為 $2i+1$
        - 其父點編號為 $[\frac{i}{2}]$ (若 $[\frac{i}{2}] \lt 1$ 則無父點)
- Strict Binary Tree
    - Binary Tree 中，任何 non leaf 皆有 2 個子點，即 $n_1 = 0$

### Binary Tree 實作
- 利用 array 
    - 作法 : 若 Binary Tree 高度為 k，則準備一個一維陣列 $A = array[1 ... 2^{k}-1]$，將各個 node 仿照 Full Binary Tree node 的編號，將 node data 填入 A 對應的表格中 
    - 優點 : 
        - 易於存取左右子點及父點
        - 對於 Full Binary Tree 或 Complete Binary Tree 而言，無儲存空間浪費
    - 缺點 : 
        - node 之插入、刪除不便
        - 對於 Skewed Binary Tree 的儲存極為浪費空間(浪費 $2^k-1-k$ 格)
- 利用 link list 表示
    - 作法 : 
        | Lchild | Data | Rchild |
        |---|---|---|
    - 優點 : 
        - node 之插入、刪除較為方便
        - 對於 Skewed Binary Tree 儲存較 array 省空間
    - 缺點 : 
        - 不易存取父點
        - link 之空間浪費約 50% ($2n-(n-1)$)

### Binary Tree 追蹤
-  Preorder

```cpp=
Preorder(BinaryTree T) {
    
    if (T != NULL) {
        
        print(T -> data);
        Preorder(T -> leftChild);
        Preorder(T -> rightChild);
        
    }
    
}
```

- Inorder

```cpp=
Inorder (BinaryTree T) {
    
    if (T != NULL) {
        
        Inorder(T -> leftChild);
        print(T -> data);
        Inorder(T -> rightChild);
        
    }
    
}
```
### Binary Tree 複製

```cpp=
CopyTree(node origin) {
    
    if (origin == NULL)
        return NULL;
    else {
        t = new_node();
        
        t -> data = origin -> data;
        t -> leftChild = CopyTree(origin -> leftChild);
        t -> rightChild = CopyTree(origin -> rightChild);
    }
    
}
```

### Binary Tree 比較

```cpp=
bool answer = false;

Equal(BinaryTree S, BinaryTree T) {
    
    if (S == NULL && T == NULL)
        return true;
    else if (S != NULL && T != NULL) {
        if (S -> data == T -> data) {
            if (Equal(S -> leftChild, T -> leftChild))
                answer = Equal(S -> rightChild, T -> rightChild);
        }
    }
    
    return answer;    
    
}
```

### Binary Tree 數 node

```cpp=
CountNodes(BinaryTree T) {
    
    if (T == NULL)
        return 0;
    else {
        int n1 = CountNodes(T -> leftChild);
        int n2 = CountNodes(T -> rightChild);
        return n1+n2+1;
    }
    
}
```

### Binary Tree 樹高

```cpp=
TreeHeight(BinaryTree T) {
    
    if (T == NULL)
        return 0;
    else {
        int n1 = TreeHeight(T -> leftChild);
        int n2 = TreeHeight(T -> rightChild);
        return max(n1, n2)+1;
    }
    
}
```

### Binary Tree 葉子數

```cpp=
TreeLeaves(BinaryTree T) {
    
    if (T == NULL)
        return 0;
    else {
        int n1 = TreeLeaves(T -> leftChild);
        int n2 = TreeLeaves(T -> rightChild);
        if (n1+n2 > 0)
            return n1+n2;
        else
            return 1;
    }
    
}
```

### Binary Tree 交換

```cpp=
SwapTree(BinaryTree T) {
    
    if (T != NULL) {
        SwapTree(T -> leftChild);
        SwapTree(T -> rightChild);
        temp = T -> leftChild;
        T -> leftChild = T -> rightChild;
        T -> rightChild = temp;
    }
    
}
```

### Binary Tree 算算式

```cpp=
struct Node{
    leftChild;
    rightChild;
    data;
    answer;
}

ExprBT(BinaryTree T) {
    
    if (T != NULL) {
        ExprBT(T -> leftChild);
        ExprBT(T -> rightChild);
        switch(data) {
                
            case "+" :
                T -> answer = (T -> leftchild) -> answer + (T -> rightChild) -> answer;
                break;
            case "-" :
                T -> answer = (T -> leftchild) -> answer - (T -> rightChild) -> answer;
                break;
            case "*" :
                T -> answer = (T -> leftchild) -> answer * (T -> rightChild) -> answer;
                break;
            case "/" :
                T -> answer = (T -> leftchild) -> answer / (T -> rightChild) -> answer;
                break;
            case "^" :
                T -> answer = (T -> leftchild) -> answer ^ (T -> rightChild) -> answer;
                break;
            case "operand" :
                T -> answer = int(operand);
                
        }
    }
    
}
```

### Binary Tree 排序
- Heap Sort
- Search Tree
    - Binary Search Tree
    - m-way Search Tree
    - AVL Tree
    - B Tree
    - B+ Tree

### Binary Tree 和其他資料結構轉換 
- Binary Tree 化為 Tree
    步驟為 : 
    1. 逆時針轉 45 度，即右子點均向上拉成為父點之次右兄弟
    2. 補足父、子之 links
    3. 刪除 sibling 間的 link
- Tree 化為 Binary Tree
    步驟為 : 
    1. 建立 sibling 之間的 links
    2. 除了 Leftmost Child 的 link，刪掉其他父與子的 links
    3. 順時針轉 45 度，即保留的 Leftmost Child 當左子點， Next Right Sibling 當右子點
- Forest 化為 Binary Tree
    步驟為 : 
    1. 將 Forest 中每棵 Tree 化為 Binary Tree
    2. 將各個 Binary Tree 之 root 們視為 siling，建立平行 links
    3. 將這些 roots 順時針旋轉 45 度，其餘不變
- Binary Tree 化為 Forest
    步驟為 : 
    1. 將 Binary Tree root 之右子點 link 上所有 node 均向上拉形成 root 之 sibing
    2. 刪除 roots 間的 links，得到多棵 Binary Tree
    3. 每個 Binary Tree 再化為 Tree 

### Binary Tree 其他考題

- Binary Tree 與 Tree 之比較
    | Tree | Binary Tree |
    | -------- | -------- |
    | 不可以為空 | 可以為空 |
    | node degree $\ge 0$ 即可 | $2 \ge$ node degree $\ge 0$ |
    | 子樹之間無次序或左右之分 | 子樹之間有左右之分 |
    
- Binary Tree 三個基本定理
    - 二元樹中第 i level 最多 node 數為 $2^{i-1}$
    - 高度為 k 之 tree 的 node 數最多為 $2^k-1$
    - 給予一個非空的 Binary Tree，若 leaf 個數有 $n_0$ 個，degree-2 的 node 數為 $n_2$ 個，則滿足 $n_0 = n_2 + 1$

- n 個 nodes 可以形成的不同 Binary Tree 個數為 $\frac{1}{n+1}\binom{2n}{n}$

## Binary Search Tree (BST)
### Binary Search Tree 定義
是一個 Binary Tree，若不為空，則滿足
- 左子樹所有 node 均小於 root
- 右子樹所有 node 均大於 root
- 左右子樹亦是 Binary Search Tree

### Binary Search Tree 排序
步驟為
1. 將 Input Data 建成 Binary Search Tree
2. 對 Binary Search Tree 進行 Inorder 追蹤，得出由小到大的排序

### Binary Search Tree 建立
受到 Input Data 的順序影響，若 Input Data 的順序為
- 小到大 $\rightarrow$ Right Skewed Binary Search Tree
- 大到小 $\rightarrow$ Left Skewed Binary Search Tree

### Binary Search Tree 中刪除某元素 x
步驟為
1. 先 search for x
2. 分成下列 cases
    - case 1 : x 是 leaf，則刪 x
    - case 2 : x 是 degree-1 的 node，則將 x 的父點原先指向 x 的 pointer 指向 x 的子點，再刪 x
    - case 3 : x 是 degree-2 的 node，則以 x 左子樹的最大值或 x 右子樹的最小值取代 x，再回到 case 1 或 case 2
> 平均時間複雜度為 $T(n) = O(logn)$
> 但若為 Skewed Binary Search Tree，則時間複雜度為 $T(n) = O(n)$

### Binary Search Tree 中搜尋某元素 x

```cpp=
Search(BinaryTree T, int x) {
    
    if (T != NULL) {
        switch(CompareValue(T -> data, x)) {
                
            case "=" :
                return true;
            case "<" :
                return Search(T -> rightChild, x);
            case ">" :
                return Search(T -> leftChild, x);
                
        }
    }else
        return false;
    
}
```
> 若為 AVL Tree、Red Black Tree、Full Binary Tree 或 Complete Binary Tree 等高度最小化的樹時，則時間複雜度為 $T(n) = O(logn)$
> 但若為 Skewed Binary Search Tree，則時間複雜度為 $T(n) = O(n)$

### Binary Search Tree 找出第 i 小的元素
| Lsize | Lchild | Data | Rchild |
|--|--|--|--|

Lsize 主要功能為記 node 左子樹的 node 個數
```cpp=
struct node {
    leftChild;
    lsize;
    data;
    rightChild;
}

SearchiSmall(BinaryTree T, int i) {
    
    if (T != NULL) {
        
        int k = (T -> lsize) + 1;
        
        if (i == k)
            return T -> data;
        else if (i < k)
            return SearchiSmall(T, i);
        else
            return SearchiSmall(T, i-k);
    
    }
    
}
```



## Thread Binary Tree
### Thread Binary Tree 定義
Binary Tree 具有 n 個 nodes，以 link list 表示，會有 n+1 條 null links，為了充分利用這些 null links，所以會將這些 null links 視為 Thread Pointer，改成指向其他 node
一般而言，是以 Inorder 順序為規範，Thread Pointer 如下 : 
- 若 x $\rightarrow$ Lchild 為 null，則此 pointer 當作左引線，改指向 Inorder 順序中 x 的前一個 node
- 若 x $\rightarrow$ Rchild 為 null，則此 pointer 當作右引線，改指向 Inorder 順序中 x 的後一個 node

### Thread Binary Tree 實作
| Left Thread | Lchild | Data | Rchild | Right Thread |
| -------- | -------- | -------- |--|--|

Left Thread : 
- true : 表 Lchild 為 Left Thread
- false : 表 Lchild 為 Lchild

Right Thread : 
- true : 表 Rchild 為 Right Thread
- false : 表 Rchild 為 Rchild

會額外加一個 Head node 不存在 Data，Head node 規定如下 : 
- case 1 : 空樹
    | True | Lchild | Data | Rchild | True |
    |--|--|--|--|--|
- case 2 : 非空樹
    | False | Lchild | Data | Rchild | False |
    |--|--|--|--|--|

### Thread Binary Tree 中找 Inorder 順序裡 x 的下一個元素
步驟為 : 
1. 若 x 的 Right Thread 為 true，則 x 的 Rchild 即是
2. 若 x 的 Right Thread 為 flase，則沿著 x 的右子點往左下尋找，直到某個 node 的 Left Thread 是 true 為止，則為該 node

```cpp=
Insuc(node x) {
    
    temp = x -> Rchild;
    
    if (! x -> RightThread) {
        while(! temp -> LeftThread)
            temp = temp -> Lchild;
    }
    
    return temp -> data;
    
}
```

### Thread Binary Tree 中找 Inorder 順序裡 x 的上一個元素
步驟為 : 
1. 若 x 的 Left Thread 為 true，則 x 的 Lchild 即是
2. 若 x 的 Left Thread 為 flase，則沿著 x 的左子點往右下尋找，直到某個 node 的 Right Thread 是 true 為止，則為該 node

```cpp=
Inpre(node x) {
    
    temp = x -> Lchild;
    
    if (! x -> LeftThread) {
        while(! temp -> RightThread)
            temp = temp -> Rchild;
    }
    
    return temp -> data;
    
}
```

### Thread Binary Tree 簡化 Inorder 追蹤
從 Head node 開始，不斷地問 x 的下一個元素，直到又回到 Head 為止

```cpp=
Inorder(node n) {
    
    temp = n;
    
    repeat :
        temp = Insuc(temp);
        if (temp != n)
            print(temp -> data);
    until (temp == n);
    
}
```

### Thread Binary Tree 中在 s 的右子點插入元素 x
分為兩個 case
- case 1 : 若 s 原本無右子點
    步驟為 : 
    1. 將元素 x 的 Right Thread 指向 s 的 Right Thread (Right Thread 為 true)
    2. 將元素 x 的 Left Child 指向 s (Left Thread 為 false)
    3. 將 s 的 Right Child 指向 x
- case 2 : 若 s 原本有右子點
    步驟為 : 
    1. 將元素 x 的 Right Child 指向 s 的Right Child (Right Thread 為 false)
    2. 將元素 x 的 Left Thread 指向 s (Left Thread 為 true)
    3. 將 s 的 Right Child 指向 x
    4. 將 s 的右子樹中最左邊 node 的 Left Thread 指向元素 x

```cpp=
Insert(s, t : nodes of thread binary tree) {
    
    t -> RightThread = s -> RightThread;
    t -> Rchild = s -> Rchild;
    
    s -> RightThread = false;
    s -> Rchild = t;
    
    t -> LeftThread = true;
    t -> Lchild = s;
    
    if (t -> RightThread) {
        temp = Insuc(t);
        temp -> Lchild = t;
    }
    
}
```


## Heap
### Heap 定義
可分為 Max-Heap 及 Min-Heap
- Max-Heap : 
    - 是一個 Complete Binary Tree
    - 所有父點均 $\ge$ 其子點
    - root 具有最大值
- Min-Heap : 
    - 是一個 Complete Binary Tree
    - 所有父點均 $\le$ 其子點
    - root 具有最小值

### Heap 建立
方法有兩種
- Top-Down 法 (慢)
    - 作法 : 依序執行插入某元素 x 的動作，逐步建立 Heap，而在每一中間過程之後，均維持是 Heap 的性質
    - > $T(n) = O(nlogn)$
- Bottom-Up 法 (快)
    - 作法 : 
        - 將 Input Data 以 Complete Binary Tree 方式呈現
        - 從 the last parent 開始，往回各個父點依序調整每棵子樹成為 Heap，直到調到 root 為止
    - code
        ```cpp=
        CreateHeap(Tree T, int n) {

            for i = n/2 to 1 
                Adjust(T, i, n);

        }

        Adjust(Tree T, int i, int n) {

            k = T[i];
            j = 2*i;

            while(j <= n) {

                if (j < n) {
                    if (T[j+1] > T[j])
                        j ++;
                }

                if (T[j] <= k)
                    break;
                else {
                    T[j/2] = T[j];
                    j *= 2;
                }

            }

            T[j/2] = k;

        }
        ```
    - > $T(n) = O(n)$

### Heap 中插入某元素 x (Max-Heap 為例)
步驟為 : 
1. x 先暫置於 the last node 的下一個位置
2. x 往上挑戰父點，直到無父點或挑戰失敗為止
> $T(n) = O(logn)$

### Heap 中刪除某元素 x (Max-Heap 為例)
步驟為 : 
1. 移走 root 的 Data
2. 將 the last node x 刪掉，並將 x 暫置於 root 位置
3. x 自 root 向下調整，直到符合 Heap 為止
> $T(n) = O(logn)$

### Heap 中刪除最大元素 (Max-Heap 為例)
```cpp=
DeleteHeap(Tree T, int n) {
    
    item = T[1];
    T[1] = T[n];
    n --;
    Adjust(T, 1, n);
    return item;
    
}

Adjust(Tree T, int i, int n) {
    
    k = T[i];
    j = 2*i;
    
    while(j <= n) {
        
        if (j < n) {
            if (T[j+1] > T[j])
                j ++;
        }
        
        if (T[j] <= k)
            break;
        else {
            T[j/2] = T[j];
            j *= 2;
        }
        
    }
    
    T[j/2] = k;
    
}
```
> $T(n) = O(lgn)$

### Heap 應用
- Heap Sort
- Priority Queue 最適合的 Data Structure
    - | Operation | Time |
        | -------- | -------- |
        | Insert x | $O(logn)$ |
        | Delete max (或 min) | $O(logn)$ |
        | Search max (或 min) | $O(1)$ |
        | Create Heap | $O(n)$ |
        | Merge two Heap into a Heap ($O(2n)$) | $O(n)$ |
        | Increase (Decrease) key of node | $O(logn)$ |
        | Search for x | $O(n)$ |
        | Delete x | $O(logn)$ |


### Heap 其他考題
- Heap 適合用 array 儲存

## Disjoint Set
### Disjoint Set 定義
一組互斥之集合組成

### Disjoint Set 表示方式
每個 set 利用 Tree 結構表示，即從 set 中任取一做為 Tree 的 root，其餘為他的子點
- 用 link list
    - | Data | Parent |
      |--|--|
- 用 array 
    -   | Index | Data | Parent |
        | -------- | -------- | -------- |
        | 1 | 1 | 0 |
        | 2 | 2 | 1 |
        | 3 | 3 | 1 |
        | 4 | 4 | 5 |
        | 5 | 5 | 0 |
        | 6 | 6 | 5 |
        | 7 | 7 | 0 |
        | 8 | 8 | 7 |
        | 9 | 9 | 5 |
        | 10 | 10 | 7 |

### Disjoint Set 應用
- Kruskal's Algorithm 中判斷邊 (u, v) 加入 Spanning Tree 中是否形成 cycle
- 根據等價配對資訊，求出等價集合
- 求 Directed Graph 中的 Connected Component 之方法之一

### Disjoint Set 尋找運作之組合討論
兩個基本操作 : 
union(i, j) $\rightarrow$ 聯集 $set_i$ 與 $set_j$
find(x) $\rightarrow$ 找出 x 元素所在的 set 的 root，傳回那個 root
- [組合一] 任意的 union(i, j) 及 simpleFind(x)
```cpp=
//任意的 union(i, j)
union(i, j) {
    
    j -> parent = i;
    
}
```

```cpp=
// simpleFind(x)
simpleFind(x) {
    
    temp = x;
    
    while(temp -> parent != temp) {
        temp = temp -> parent;
    }
    
    return temp;
    
}
```

> $Union : T(n) = O(1)$
> $Find : T(n) = O(n)$

- [組合二] union_by_height(i, j) 及 simpleFind(x)
樹高較高者作為新樹的 root，另一個 set 作為其子樹
若高度相同，則做任意 union
```cpp=
union_by_height(i, j) {
    
    if (Height(i) >= Height(j)) {
        if (Height(i) == Height(j))
            i ++:
        
        j -> parent = i;   
    }else
        i -> parent = j;
    
}
```
```cpp=
// simpleFind(x)
simpleFind(x) {
    
    temp = x;
    
    while(temp -> parent != temp) {
        temp = temp -> parent;
    }
    
    return temp;
    
}
```

> $Union\_By\_Height : T(n) = O(1)$
> $Find : T(n) = O(lgn)$

- [組合三] union_by_height(i, j) 及 Find_with_path_compression(x)
除了找出 x 所在 set 之 root 外，另外會將 x 的 parent links 上所有 nodes (包含 x，但不包含 root) 的 parent 指標均改成指向 root (即做了路徑壓縮)

```cpp=
union_by_height(i, j) {
    
    if (Height(i) >= Height(j)) {
        if (Height(i) == Height(j))
            i ++:
        
        j -> parent = i;   
    }else
        i -> parent = j;
    
}
```

```cpp=
Find_with_path_compression(x) {
    
    if (x != x -> parent)
        x -> parent = Find_with_path_compression(x -> parent);
    
    return x -> parent;
    
}
```

> $Union\_By\_Height : T(n) = O(1)$
> $Find\_with\_path\_compression : T(n) = O(\alpha(m,n))趨近於O(1)$