# 普通Binary Search Tree

## Binary Search Tree定義
介紹Binary Search Tree的文章已經很多，我比較想用較白話的方式，釐清一些新手可能遇到的困惑點；把所有普通型Binary Search Tree的操作一次寫完

一般說的Binary Search Tree只要符合這三點：
1. 對任一節點R，以其左節點為根的子樹(左子樹)的所有節點必小於R
2. 對任一節點R，以其右節點為根的子樹(右子樹)的所有節點必大於R
3. 以子樹中任一子節點為根的子樹也都符合上述定義

符合以上三點而不加上其他特點的，這邊暫且稱為Normal Binary Search Tree；而自平衡二元樹(AVL Tree)或紅黑樹則是BST加上其他特性，也在BST的範疇內，但此篇只討論Normal BST本身

## 走訪 (Traversal)
BST的traversal有三種... (其實有第四種，後面會提到)

Inorder   (左->中->右): D B A E C F
Preorder  (中->左->右): A B D C E F
Postorder (左->右->中): D B E F C A

1. 英文字首In.. Pre.. Post.. 指的是根節點的出現順序
2. 這三種order都可以用stack或遞迴來實作，遞迴的code最少
3. 要用遞迴的觀念來思考，以inorder為例的左->中->右指的是[左子樹]->[根]->[右子樹]；而在處理[左子樹]時，又要先去處理[左子樹的左子樹]，再回到[左子樹的根]，再處理[左子樹的右子樹]...以此類推
4. 在實作上，只不過是「往下遞迴」以及「訪問」的順序排列組合而已 （但沒有先右再左的順序）
5. Traversal順序在應用上是有意義的，像後面提到的「刪除節點」時就會用到in-order
6. Traversing 裡的「訪問」是個抽象動詞，就是一個踩點的概念，如果只是在程式中寫printf或cout，你可能會看不出訪問這個動作在哪，以下用doVisit()來包裝這個動詞，這樣看是不是就比較清楚：

void inorder(TreeNode* root) {
    if (root == NULL)
        return;

    inorder(root->left);
    doVisit(root);
    inorder(root->right);
}
void preorder(TreeNode* root) {
    if (root == NULL)
        return;

    doVisit(root);
    preorder(root->left);        
    preorder(root->right);
}
void postorder(TreeNode* root) {
    if (root == NULL)
        return;

    postorder(root->left);        
    postorder(root->right);
    doVisit(root);
}    

> 而doVisit可以代換成其他實體行為。例如，你可以把doVisit寫成callback function (或delegate)，該callback指向某種實體操作如印出、或是insert節點值到一個list (某些題目會要你輸出list)

#### Level-order traversal
有些文章說到BST的traversal只會提到上面那三種，有的則把第四種並列，也就是level-order，就是BFS (Breadth-First Search)；它當然也是traversal的一種，**只要是從根節點出發能找到所有子節點的方法都是traversal method**

BFS: A B C D E F

如果我們把葉節點左右child指向的NULL當成真正的葉節點，那麼這樣的level-order得出的陣列很適合拿來在程式中表示一棵樹，也適合拿來建樹 (誰的左右子節點為空都知道)

BFS: A B C D NULL E F

> ps. 總不能每次要表示一棵樹都用畫圖的方式吧
> ps. LeetCode通常以此array為一棵樹的input

我們都知道BFS要用Queue來實作，而不是用遞迴：

void bfs(TreeNode* root) {
    queue<TreeNode*> q;

    q.push(root);

    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();

        // 如果doVisit有把NULL印出來，那就是上述說的那種可以建樹的
        doVisit(node); 

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

## 新增 (Insertion)
雖然Insert字面上有插入在中間的意思，但對一般Binary Search Tree (沒有平衡功能的)而言，insert一個新節點永遠都是往葉節點新增，不會有新節點出現在中間層的情況。即使是同樣一組成員，insert的順序不一樣，整棵樹的長相有可能會不一樣

1. 只改節點在同一階層內的新增順序，則樹的長相不會改變
2. 改變了節點的所在階層，整棵樹會長不一樣

例如這2組insert順序：
50, 30, 80, 22, 45, 62, 93, 40, 48, 70, 42
50, 80, 30, 45, 93, 62, 22, 70, 48, 40, 42

這是原始的樹：

*以下Input僅是代表新增的優先順序
*而不是指任何一種traversal order

Input: [50, 30, 80, 22, 45, 62, 93, 40, 48, 70, 42]

        50
        / \
       /   \
      /     \
     /       \
    /         \
   30         80
  / \         / \
 /   \       /   \
22   45     62   93
     / \     \
    /   \    70
   40   48
    \
    42

改變了同一層內的節點插入順序

Input: [50, 80, 30, 45, 93, 62, 22, 70, 48, 40, 42]

         50
        / \
       /   \
      /     \
     /       \
    /         \
   30         80
  / \         / \
 /   \       /   \
22   45     62   93
     / \     \
    /   \    70
   40   48
    \
    42

建出來的樹完全一樣。以下的順序則改變了節點的所在階層：

Input: [80, 70, 50, 45, 30, 62, 22, 40, 93, 48, 42]

             80
             / \
            /   \
           70   93
          /
         50
        / \
       /   \
      45   62
     / \
    /   \
   30   48
  / \
 /   \
22   40
       \
       42
       
BFS:       80, 70, 93, 50, 45, 62, 30, 48, 22, 40, 42
Inorder:   22, 30, 40, 42, 45, 48, 50, 62, 70, 80, 93
Preorder:  80, 70, 50, 45, 30, 22, 40, 42, 48, 62, 93
Postorder: 22, 42, 40, 30, 48, 45, 62, 50, 70, 93, 80       

Insertion實作如下：

void insertNode(TreeNode* root, TreeNode* node) {
    if (node->val < root->val)               // 比較小，往左子樹放
        if (root->left != NULL) 
            insertNode(root->left, node);    // 左節點非空，往左子樹找位置
        else 
            root->left = node;               // 左節點為空，直接成為左節點    
    else if (node->val > root->val)            // 比較大，往右子樹放
        if (root->right != NULL) 
            insertNode(root->right, node);   // 右節點非空，往右子樹找位置
        else 
            root->right = node;                 // 右節點為空，直接成為右節點                      
    else {
        ; // 如果值相等，則不新增節點，什麼都不做
    }
}

## Deletion (刪除)
刪除一個節點會遭遇到三種情況，前兩種都很簡單，第三種其實也沒多複雜...

1. 要刪除的節點沒有子樹 - 直接刪除即可 (實作上是把父節點指向它的指標改成NULL)
例如要刪除這棵樹的G
2. 要刪除的節點只有左或右其中一邊有子樹 - 把父節點原本指向它的指標改指向子節點 (也就是子樹的根)
例如刪除這棵樹的C
3. 要刪除的節點有左右兩個子樹 - 找Inorder Successor或Inorder Predecessor來接替自己 (二者擇一)

> *注意以上稱的子樹也有可能只是一個節點*

其中successor和predecessor這兩個英文字指的就是順序中下一個、前一個的意思，inorder就是左中右，假設要刪除的節點是N則：
* Inorder Successor: N在inorder順序中的下一個，也就是右子樹中的最小者，會在右子樹最偏左的位置
* Inorder Predecessor: N在inorder順序中的前一個，也就是左子樹中的最大者，會在左子樹最偏右的位置

所以左右兩邊都有子樹的情況，可以用下圖來理解：In-order中最接近80的2個 (65, 70)，剛好都有資格成為新首領，如果是其他order就不是這樣了


此外，successor和predecessor還有這樣的特性：
* Successor已經是最小者，不會有左子樹，但可能有右子樹
* Predecessor已經是最大者，不會有右子樹，但可能有左子樹

> 特別提這個是因為... 這包含了寫程式時需要考慮以及不需要考慮的點

在下例中，要刪除80的節點，其inorder successor是70，inorder predecessor是65，這兩個節點都可以拿來接替它自己

話雖簡單，實作上要擬定一套操作邏輯 (以下假設要刪除的節點為N)：
1. 用遞迴的概念上，我們以輸入根節點、回傳根節點的方式來傳遞，也就是*N = f(N, x)*，其中x是要刪除的key，在這過程中，輸入的N和回傳的N可能會是同一個，也可能會不同一個；例如上面的例子中，當輸入的root是80時，最後得到的會是70或65，而這個回傳節點必須是一個已經處理好順序的整顆子樹。當然也有不輸出值的遞迴實作方式，你可以想看看怎麼做
2. 在找到要刪除的目標節點時，先找到其successor或predecessor，找到後... (以下只以successor為例)
3. 如果Successor有右子樹 (絕對沒有左子樹)，則讓右子樹取代它的位置，也就是successor父節點的left指標指向它的右子樹；反之，如果其右子樹是null，則把父節點的left指標指向null
4. 將N原有的left、right指標設為null，改由successor去指向 (注意successor也有可能是右節點自己，不能指向自己)
5. 如果N有父節點，讓原來指向N的父節點指標改指向successor (實作上，return successor就可以達到這件事)

TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == NULL)
        return root;

    TreeNode* tempR = root->right;
    TreeNode* tempL = root->left;        

    if (root->val == key) {
        if (root->left == NULL && root->right != NULL) {                
            root->right = NULL;
            return tempR;
        }
        else if (root->left != NULL && root->right == NULL) {
            root->left = NULL;
            return tempL;
        }
        else if (root->left != NULL && root->right != NULL) {
            // todo: return the successor
            TreeNode* successor = NULL;

            if (root->right->left == NULL) {
                // The right side maybe the successor itself sometimes
                successor = root->right;                
            }
            else {
                TreeNode* successorFather = findSuccessorFather(tempR);
                successor = successorFather->left;
                successorFather->left = successor->right;                    
            }

            /*  這邊用tempL和tempR代替root->left和root->right
             *  是為了避免中途操作時，發生cyclic的情況
             *  一般只要最後結果沒有回圈即可，但LeetCode會在執行時期檢查回圈發生
             */
            root->left = NULL;     
            root->right = NULL;

            successor->left = tempL;

            if (tempR != successor)
                successor->right = tempR;                

            return successor;
        }
        else {
            return NULL;
        }            
    }

    if (root->left != NULL) {
        root->left = deleteNode(root->left, key);
    }
    if (root->right != NULL) {
        root->right = deleteNode(root->right, key);   
    }            
    return root;
}
/*  因為資料結構中沒有father，所以找Successor的父節點，比較好做後續處理 */
TreeNode* findSuccessorFather(TreeNode* root) {                        
    if (root->left->left == NULL) {
        return root;
    }        
    return findSuccessorFather(root->left);
}

## Complexity
### 時間複雜度
* BST的搜尋、新增、刪除的平均時間複雜度都是O(log N)，N為節點數量。因為都是要「找到」某個元素，而二元樹找東西的時間相當於樹的高度，也就是O(log N)

* 雖然BST的的deletion多了「找successor」或「找predecessor 」的時間，但那頂多也是一次O(log N)的行為，並不會增加複雜度的等級

* Traversal 的複雜度是O(N)，因為每個節點都要走過一遍，無法少於這個了

### 空間複雜度
BST的儲存除了節點佔用空間外，並沒有使用額外空間來處理搜尋、新增、插入、走訪 （就算有也不會改變複雜度等級），因此空間複雜度為O(N)

## 與Binary Search的關係
* 二者名稱很像，但一個是資料結構，一個是純演算法，不能直接對比，硬要比的話，就是比較"搜尋"這個操作的時間
* Binary search的搜尋時間保證在O(log N)之內，而BST的搜尋則介於O(log N）~ O（N）之間，要看樹是否平衡。這就是為什麼需要自動平衡樹（AVL Tree）的存在
* Binary search用來搜尋記憶體中連續的資料；BST的資料則是分散的節點；這樣的結構對於元素的新增或刪除較有優勢

## Github
https://github.com/zackjtl/bst_example.git