Day-22 樹(Tree), 二元搜尋樹(Binary Search Tree)

2021 iThome 鐵人賽

DAY 22

自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列第 22 篇

13th鐵人賽自學筆記 algorithm

吳他，惟手熟爾

2021-10-03 10:58:09

4953 瀏覽

分享至

前言

對於大量的資料處理，使用串列的走訪是一種十分沒有效率的方法，其效率會根據串列的長度而不斷線性成長，也就是 $O(N)$ ，而樹(tree)這種資料結構，其大部分的操作時間複雜度平均為 $O(logN)$

樹的定義

樹(tree)可以用幾種方式定義。一般來說最常見也最自然的定義方法是使用遞迴的方式。一顆樹為一些節點的集合。這個集合也可以是一個空集合，如果不是空集合，則一顆樹(tree)是由一個樹根(root)的節點以及0個或是多個非空的子樹(subtree)T1, T2, Tk所組成，這一些子樹(subtree)都被來自樹根(root)的一向量(edge)所連接著。

樹(tree)有樹根(root)，每一個子樹(subtree)也有樹根(root)，而子樹的樹根被樹的樹根所連接。假設樹的樹根為R，子樹的樹根為r，則我們會稱子樹樹根r為樹根R的兒子,子節點(child)，而樹根R為樹根r的父親,父節點(parent)

以下圖作為說明:

從遞迴定義中我們可以觀察到樹的一個性質，一個樹是由N個節點和N - 1條邊所構成的集合，也就是一棵樹會有N個節點和N - 1條邊，我們可以觀察下圖

我們可以觀察到，這棵樹從A到Q，共有16個節點，15條邊，應證我們上方的結論

而我們來說明一下這一棵樹，節點A為樹根(root)。

節點F有一個父親, 父節點A，並且有兒子,子節點K, L, M。在一棵樹中，每一個節點可以有任意多個兒子，也有可能有0個兒子。沒有兒子的節點我們稱為樹葉(left)，觀察上方的樹，我們可以發現B, C, H, I, P, Q, K, L, M, N為樹葉。

具有相同父親的節點稱為兄弟(Sibling)，因此觀察F節點，可以發現K, L, M皆為兄弟，因為F為他們共同的父親。

接下來對於樹的一些名詞進行定義:

樹根(root) : 指的是樹中最上面那個節點，一個樹中只會有一個樹根。
子樹(subtree) : 由一個節點和其後代所構成的集合。
子節點(child node) : 有父節點的節點，基本上除了樹根以外，其餘節點皆為子節點。
葉子(left) : 該節點沒有其他子節點。
節點ni的深度(depth) : 對於節點ni，ni的深度(depth)為從樹根到ni的唯一路徑長。

舉例 : 對於上圖，E的深度即為A到E的路徑長，也就是1 ，P的深度為A到P的路徑長，也就是3。

節點ni的高度(height) : ni節點到一片樹葉(left)的'最長'路徑長。

舉例 : 對於上圖，E的高度為2，原因為我們可以找到P, 或是Q這樣的葉子，他們到E的路徑長為2，且我們沒辦法找到一片葉子他們到E的路徑長大於2，因此E節點高度為2

完美二元樹 : 除了葉節點，其他節點皆有兩個子節點，也就是每一層都填滿，也就是深度為 $k$ 的二元樹，具有 $2^k-1$ 個節點
完全二元樹 : 除了最後一層，其餘層皆為滿的，對於一棵深度為 $k$ 的二元樹，最少有 $2^{k-1}$ 個節點，最多有 $2^{k}-1$ 個節點。

如果我們觀察整棵樹，可以知道這個樹的高度為3，也就是A節點到樹葉的路徑長。而觀察節點F，可以發現節點F的深度為1，也就是A到F的路徑長，F的高度為1，也就是K, L, M這些葉子到F的路徑長。

樹的實作

我們由上面的推論，可以推測出每一個節點需要三個資訊，節點的數據，以及下面兩個子節點的指標。這邊有幾個問題需要解決，首先，每一個節點不一定只有1個或是2個兒子，可能會有很多兒子，因此，把每一個兒子都宣告在節點的結構內是不可行的。

我們的解決方法為一個指標指向兒子，另一個指標指向兒子的兄弟們，透過NextSibling去存取兒子們。


typedef struct TreeNode{
    ElementType Element;
    struct *TreeNode FirstChild;
    struct *TreeNode NextSibling;
}TreeNode;

如果我們上面示範的樹，用這個結構進行表達，情況會像是下圖所演示

由左到右的箭頭表示指向兄弟(NextSibling)，下向的箭頭表示指向兒子(FirstChild)。
以節點E舉例:節點E的NextSibling指標指向節點F，NextSibling指標指向節點I。

二元樹(Binary Tree)

二元樹(Binary Tree)是一棵樹，其中每一個節點都不能多於兩個兒子，下圖為由一個樹根，和兩顆子樹所組成的二元樹，TL和TR可能為NULL。

二元樹有一個重要的性質，為平均二元樹的深度比N小的很多，平均深度為 $O(\sqrt N)$ ，而這種特殊的二元樹，我們又把他稱作為二元搜尋樹(Binary Search Tree)，其深度平均為 $O(\log (N))$ ，而深度最大為 $N - 1$ 如下圖所示

左圖即為深度為 $N - 1$ 的情況。

二元樹實作

因為一顆二元樹最多只有兩個兒子，我們可以直接用指標指向他們。節點的宣告很類似循環串列的宣告方式。每個節點就是節點內的值，加上兩個子節點的指標。

typedef sturct TreeNode{
    ElementType Element;
    struct TreeNode* Left;
    struct TreeNode* Right;
}TreeNode;

二元搜尋樹(Binary Search Tree)

二元樹其中一個重要的應用就是用於搜尋節點中特定的數值。要使二元樹成為二元搜尋樹，需要具備一項性質，便是對於樹中每一個節點X，他的左子樹每一個樹值都會小於節點X的樹值，也因此當我們把一堆資料丟入二元搜尋樹時，他會有固定的排列方式。如下圖所示

我們可以看到，只有左邊這棵樹為二元搜尋樹，右邊這棵樹為二元樹，右邊之所以不是二元搜尋樹，原因為在左子樹中，節點7的數值大於節點6的數值，這種情況在二元搜尋樹中是不允許發生的。

二元搜尋樹能夠使用多種對於動態集合的操作，像是SEARCH, INSERT, DELETE等操作，也因此我們可以使用二元搜尋樹實作出優先隊列或是字典序的資料集合。

二元搜尋樹進行各項操作的時間複雜度取決於這棵樹的高度，對於有 $n$ 個節點的完全二元搜尋樹，這些操作最差的執行時間為 $\Theta (lgn)$ ，如果這棵樹剛好是由一條由 $n$ 個節點所構成的線性鏈狀結構，也就是深度為 $N-1$ 的情況，那麼最差即為 $\Theta (n)$ ，不過，一棵二元搜尋樹高度的期望值為 $O(lgn)$ ，因此每一種操作執行時間的期望值皆為 $\Theta (lgn)$ 。

二元搜尋樹(Binary Search Tree)的ADT

以下為二元搜尋樹的ADT，其中，樹提供了三種走訪的方式，分別為中序走訪(inorder), 前序走訪(preorder), 後序走訪(postorder)。

#ifndef _Tree_H

TreeNode* Create_tree(TreeNode*);
TreeNode* MakeEmpty(TreeNode* T);
void In_order(TreeNode*);
void Pre_order(TreeNode*);
void Post_order(TreeNode*);
void Level_order(TreeNode*);
TreeNode* Search_node(ElementType X, TreeNode* T);
TreeNode* FindMin(TreeNode* T);
TreeNode* FineMax(TreeNode* T);
TreeNode* Ineset(ElementType X, TreeNode* T);
TreeNode* Delete(ElementType X, TreeNode* T);
ElementType Retrieve(TreeNode* P);

#endif /*_Tree_H*/

/*Place in the implementation file"*/
typedef sturct TreeNode{
    ElementType Element;
    struct TreeNode* Left;
    struct TreeNode* Right;
}TreeNode;

Create_tree函式實作

TreeNode* Create_tree(TreeNode* root, int value)
{
    root = malloc(sizeof(TreeNode));
    root->left = NULL;
    root->right = NULL;
    root->value = value;
    return root;
}

MakeEmpty函式實作

TreeNode* Make_empty(TreeNode* root)
{
    if(root != NULL)
    {
        make_empty(root->left);
        make_empty(root->right);
        free(root);
    }
    return NULL;
}

In_order函式實作

In_order，中序走訪，命名的理由為輸出的形式為根節點會出現在左節點和右節點之間，也就是依照左節點根節點右節點形式輸出。

void In_order(TreeNode* root)
{
    if(root != NULL)
    {
        inOrder(root->left);
        printf("%d ", root->value);
        inOrder(root->right);
    }
    return;
}

(為了方便說明，上面的樹只是二元樹而已)

In_order = 7,4,8,2,5,1,3,9,6,10

Pre_order函式實作

Pre_order，顧名思義，就是輸出的形式為根結點會出現在左結點和右結點之前，也就根節點左節點右節點。

void Pre_order(TreeNode* root)
{
    if(root != NULL)
    {
        printf("%d ", root->value);
        preOrder(root->left);
        preOrder(root->right);
    }
}

(為了方便說明，上面的樹只是二元樹而已)

Pre_order = 1,2,4,7,8,5,3,6,9,10

Post_order函式實作

Post_order，顧名思義，就是輸出的形式為根結點出現在左結點和右結點之後

void postOrder(TreeNode* root)
{
    if(root != NULL)
    {
        postOrder(root->left);
        postOrder(root->right);
        printf("%d ", root->value);
    }
}

(為了方便說明，上面的樹只是二元樹而已)

Post_order = 7,8,4,5,2,9,10,6,3,1

Level_order函式實作

Level_order，就是依照節點所在的層數，由小到大，由左到右輸出，這裡使用queue，將結點依序推入並輸出

void level_order(TreeNode *root)
{
    queue<TreeNode *> q;
    q.push(root);
    while (!q.empty())
    {
        TreeNode *temp = q.front();
        q.pop();
        printf("%d ", temp->value);

        if (temp->left != NULL)
        {
            q.push(temp->left);
        }
        if (temp->right != NULL)
        {
            q.push(temp->right);
        }
    }
}

Search_node函式實作

給定一個指向樹根的指標，和我們要查詢的數值，如果有節點為該數值，則回傳該節點的指標，否則回傳NULL。

TREE-SEARCH(x,k)
if x == NULL or k == x.key
    return x
if k < x.key
    return TREE-SEARCH(x.left, k)
else
    return TREE-SEARCH(x.right, k)

TreeNode* search_node(TreeNode* root, int value)
{
    if(root == NULL || value == root->value)
    {
        return root;
    }
    if(value < root->value)
    {
        return search_node(root->left, value);
    }
    else
    {
        return search_node(root->right, value);
    }
}

從樹根開始走訪，遇到每一個節點 $x$ ，比較節點的數值，如果相等，則回傳該節點的指標。
如果小於，則查詢 $x$ 的左子樹並繼續尋找，也就是遞迴的概念。
如果大於，則查詢 $x$ 的右子樹並繼續遞迴尋找。
而尋找走過的最簡單路徑，即為樹的高度 $h$ ，因此整個TREE-SEARCH的時間複雜度為 $O(h)$

也可以使用while迴圈來實作，相比於遞迴，效率會來的快上許多

ITERATIVE-TREE-SEARCH(x, k)
while x != NULL and k != x.key
    if k < x.key
        x = x.left
    else x = x.right
return x

min_value_node和max_value_node函式實作

TreeNode* min_value_node(TreeNode* root)
{
    TreeNode* cur_ptr = root;
    while(cur_ptr->left != NULL)
    {
        cur_ptr = cur_ptr->left;
    }
    return cur_ptr;
}

TreeNode* max_value_node(TreeNode* root)
{
    TreeNode* cur_ptr = root;
    while(cur_ptr->right != NULL)
    {
        cur_ptr = cur_ptr->right;
    }
    return cur_ptr;
}

尋找最大值和最小值時間複雜度也是 $O(h)$

Insert函式實作

從樹根開始，使用root指標不斷的向下遍歷整棵樹，找到適當的插入位置，如果要插入的值小於子樹根的值，表示該節點需要向左子樹移動(因為二元搜尋樹的性質)，反之則向右子樹移動，通過遞迴的方式查看每一個子樹。

TreeNode* Insert(TreeNode* root, int value)
{
    TreeNode* newPtr = malloc(sizeof(TreeNode));
    newPtr->value = value;
    newPtr->left = NULL;
    newPtr->right = NULL;

    if(root == NULL)
    {
        root = newPtr;
    }
    else if (value < root->value)
    {
        root->left = insert(root->left, value);
    }
    else if(value > root->value)
    {
        root->right = insert(root->right, value);
    }
    return root;
}

或是也可以使用迴圈進行實作，使用root指標不斷的向下遍歷整棵樹，並使用temp_root紀錄root的父節點的指標，while迴圈使得這兩個指標不斷向下遍歷，直到root == NULL，而root所指向的位置像是欲插入節點的位置

TreeNode *insert(TreeNode *root, int value)
{
    TreeNode *newPtr = (TreeNode *)malloc(sizeof(TreeNode));
    newPtr->value = value;
    newPtr->left = NULL;
    newPtr->right = NULL;

    TreeNode *temp_root = NULL;
    while (root != NULL)
    {
        temp_root = root;
        if (newPtr->value < root->value)
        {
            root = root->left;
        }
        else
        {
            root = root->right;
        }
    }
    newPtr->parent = temp_root;
    if (temp_root == NULL)
    {
        root = newPtr;
    }
    else if (newPtr->value < temp_root->value)
    {
        temp_root->left = newPtr;
    }
    else
    {
        temp_root->right = newPtr;
    }
}

在一棵高度為 $h$ 的樹，INSERT的時間複雜度為 $O(h)$

Delete函式實作

從一棵二元搜尋樹 $T$ 中刪除一個節點 $z$ 可以分為三種情況

如果 $z$ 沒有任何子節點，我們只需要將 $z$ 的父節點指向子節點NULL即可。
如果 $z$ 只有一個子節點，則把該子節點放到原本 $z$ 節點的位置，並修改 $z$ 的父節點，使他指向到 $z$ 的子節點。

(a)表示只有右子節點 (b)表示只有左子節點
如果 $z$ 有兩個子節點，我們可以試著尋找出左子樹的最大節點，並將 $z$ 節點的數值設為 $z$ 左子樹中最大節點的數值，這樣做可以讓我們維持二元搜尋樹的性質，之後將 $z$ 指向到新的左子樹。

TreeNode* delete(TreeNode* root, int value)
{
    if(root == NULL)
    {

    }
    else if(value < root->value)
    {
        root->left = delete(root->left, value);
    }
    else if(value > root->value)
    {
        root->right = delete(root->right, value);
    }
    else if(value == root->value)
    {
        if(root->left == NULL && root->right == NULL)
        {
            free(root);
            root = NULL;
        }
        else if(root->left == NULL)
        {
            TreeNode* tempnode = root->right;
            free(root);
            root = tempnode;
        }
        else if(root->right == NULL)
        {
            TreeNode* tempnode = root->left;
            free(root);
            root = tempnode;
        }
        else
        {
            TreeNode* tempnode = max_value_node(root->left);
            root->value = tempnode->value;
            root->left = delete(root->left, tempnode->value);
        }
    }
    return root;
}

前面的過程為透過遞迴的方式尋找我們要刪除的節點，而欲刪除的節點會有上面說的四種情況，分別為沒有子節點，只有右子節點，只有左子節點，和有兩個子節點。

如果樹的高度為 $h$ ，則delete的時間複雜度為 $O(h)$

樹的遍歷和應用

樹有很多種應用，最常見的應用為UNIX, VAX/VMS和DOS等等，許多作業系統中作為目錄結構的表示，我們在windows平台上，在cmd中輸入tree也會列出目錄的樹狀結構，下圖為UNIX檔案系統中常見的目錄表示

上圖即為常見UNIX系統中的檔案目錄結構
這個目錄的樹根為'/'(也被稱做根目錄)，根目錄有5個兒子，分別為etc, bin, home, lib, var。而檔案路徑"/etc/hosts"，這種路徑表示法也被稱為絕對路徑(absolute path)，而hosts這個檔案，是先後通過兩個子節點所取的，而從檔案路徑來看，可以看到有兩個'/'符號，表示通過了兩條邊。
這種檔案系統十分的流行，方便之處在於可以讓使用者有邏輯性的管理檔案，且不同目錄底下的檔案可以使用相同的名稱。