# [資料結構] CH7. Binary Search Trees

* Binary Search Trees是一個排序過的二元樹，它必須符合以下特性：

1.資料必須能夠定義大於等於小於。
2.左子樹的資料必定小於自己的資料。
3.右子樹的資料必定大於自己的資料。

* 有了這樣的特性，我們便可以用較快的速度搜尋資料，下面就來看看如何搜尋、插入以及刪除吧。

## 搜尋
* 搜尋的概念十分簡單，先檢查自己是不是該資料，如果不是且資料小於自己，往左子樹找；大於的話就往右子樹找。

Node* Search(Data d, Node *n)
{
    //Can not find.
    if(n == NULL)
        return NULL;
        
    if(n->data == d)
        return n;
    else if(n->data < d)
        return Search(d, n->leftNode);
    else
        return Search(d, n->rightNode);
}

## 插入
* 插入也不難，一樣是比大小決定放左邊還是放右邊。

void Insert(Data d, Node *n)
{
    if(n==NULL)
    {
        n = new Node;
        n->data = d;
        n->leftNode = NULL;
        n->rightNode = NULL;
    }
    else
    {
        if(n->data < d)
            Insert(d, n->leftNode);
        else
            Insert(d, n->rightNode);
    }
}

## 刪除
* 刪除就稍微複雜一點了，我們必須確保它依然維持Binary Search Trees的特性。
* 刪除時我們分為幾種狀況來討論：
1.刪除的點在樹葉(也就是沒有子樹)。
2.刪除的點只有一個子樹。
3.刪除的點有兩個子樹。

* 當刪除的點是樹葉時，我們直接刪除即可：

if(n->leftNode == NULL && n->rightNode == NULL)
{
    delete n;
    n = NULL;
}

* 當刪除的點只有一個子樹，我們將該子樹替換成自己：

else if(n->leftNode == NULL)
{
    n->rightNode = n;
}
else if(n->rightNode == NULL)
{
    n->leftNode = n;
}

* 最後一個情形最複雜，我們有兩種做法：
* 將自己刪除後，找左子樹最大來替補自己：

else
{
    Data leftMax;
    leftMax = FindMax(n->leftNode);
    n->data = leftMax;
    Delete(n->leftNode, leftMax);
}

* 或是找右子樹最小替補：

else
{
    Data rightMin;
    rightMin = FindMin(n->rightNode);
    n->data = rightMin;
    Delete(n->rightNode, rightMin);
}

* 最後統整一下，整個刪除應為：

void Delete(Data d, Node* n)
{
    //Can not find.
    if(n == NULL) return;
    
    if(n->data == d)
    {
        if(n->leftNode == NULL && n->rightNode == NULL)
        {
            delete n;
            n = NULL;
        }
        else if(n->leftNode == NULL)
        {
            n->rightNode = n;
        }
        else if(n->rightNode == NULL)
        {
            n->leftNode = n;
        }
        else
        {
            Data leftMax;
            leftMax = FindMax(n->leftNode);
            n->data = leftMax;
            Delete(n->leftNode, leftMax);
        }
    }
    else if(n->data < d)
        Delete(d, n->leftNode);
    else
        Delete(d, n->rightNode);
}

* 更多Code資訊請洽：[BST](https://github.com/Zero871015/BST)

###### tags: `DS` `note`