二叉搜索樹(shù)作用、原理和實(shí)現(xiàn)（C和Python）

二叉搜索樹(shù)（Binary Search Tree）是干什么用的？

我知道的主要作用是搜索和動(dòng)態(tài)排序，二叉樹(shù)進(jìn)行插入/查詢/刪除的時(shí)間復(fù)雜度為O(log(n))。但是實(shí)際使用的時(shí)候通常不會(huì)有這么快，因?yàn)槟悴迦腠樞蛩玫膍iddle通常不是那么準(zhǔn)，尤其是在插入數(shù)據(jù)的順序是有序或者基本有序的時(shí)候，這顆二叉樹(shù)會(huì)嚴(yán)重的不平衡，最糟糕的情況下會(huì)下降到和鏈表一樣。而解決這個(gè)問(wèn)題的辦法是平衡二叉樹(shù)，但是今天這篇文章不會(huì)討論它，只會(huì)關(guān)注于基本的二叉搜索樹(shù)。

二叉搜索樹(shù)的基本原理

如果你不想看下面這些話，只想一句話明白搜索二叉樹(shù)怎么實(shí)現(xiàn)：（key比自身小放左面，key比自身大放右邊），如果你看完這句話就明白了，那恭喜你，因?yàn)檫@個(gè)事情本來(lái)就是這么簡(jiǎn)單，我之所以寫(xiě)這篇文章其實(shí)就是想節(jié)省一些不喜歡看長(zhǎng)篇大論的人的寶貴時(shí)間。。。

  1. 簡(jiǎn)單來(lái)說(shuō)搜索二叉樹(shù)的思想和二分插入排序的思想是一致的，就是用一個(gè)數(shù)做middle，然后將數(shù)據(jù)分成兩份，一份是比自己大的，一份是比自己小的。并且在插入和搜索時(shí)遵循相同的規(guī)則，就可以達(dá)到一個(gè)快速查找和排序的目的。
  2. 典型的二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)有3個(gè)部分：（查找鍵、左子節(jié)點(diǎn)指針、右子節(jié)點(diǎn)指針）。不過(guò)使用的時(shí)候通常會(huì)再加上：（數(shù)據(jù)指針、父節(jié)點(diǎn)指針）。
  3. 數(shù)據(jù)指針：通常在有key-value-store的需求時(shí)使用。（在我的示例中簡(jiǎn)化了，數(shù)據(jù)簡(jiǎn)單的用int來(lái)表示）
  4. 父節(jié)點(diǎn)指針：這不是必須的，但是加上這個(gè)指針會(huì)讓你在刪除節(jié)點(diǎn)等操作時(shí)更方便，空間換時(shí)間。
  5. 通常搜索二叉樹(shù)遵循如下原則：
  6. 左子節(jié)點(diǎn)小于自身。 右子節(jié)點(diǎn)大于自身。
  7. 所有子節(jié)點(diǎn)均遵從第一條規(guī)則。

如何實(shí)現(xiàn)一個(gè)二叉搜索樹(shù)

插入：

  1. 插入操作是比較簡(jiǎn)單的，就跟上面說(shuō)的一樣，比自己小就插到左邊，比自己大就插入到右邊，相等就更新自身。
  2. 我是使用遞歸實(shí)現(xiàn)的，因?yàn)槲矣X(jué)得這比較美觀。但這不是必須，而且從效率上來(lái)講可能不用遞歸會(huì)好一些，因?yàn)檫f歸會(huì)帶來(lái)很高的函數(shù)調(diào)用開(kāi)銷以及棧的瘋狂提高。（但是在現(xiàn)代的編譯器中這兩個(gè)問(wèn)題可能不是問(wèn)題，因?yàn)檫@些是可以被尾遞歸優(yōu)化的）
  3. 具體實(shí)現(xiàn)看nAdd函數(shù)。（這是不是一句廢話？如果是請(qǐng)告訴我，我會(huì)嘗試盡量不說(shuō)廢話）

查找：

  1. 查找操作和插入操作是幾乎一樣。
  2. 實(shí)現(xiàn)請(qǐng)看nSearch.

刪除

  1. 刪除操作就稍微麻煩一些，而且我這段代碼寫(xiě)的很丑，但是我懶得在寫(xiě)了。（如果傳進(jìn)去的是Node**類型，那么刪除時(shí)就會(huì)直觀一些，因?yàn)槟菢泳涂梢灾苯有薷闹骱瘮?shù)棧上的根節(jié)點(diǎn)指針）
  2. 刪除節(jié)點(diǎn)時(shí)分三種情況：
  3. 沒(méi)有子節(jié)點(diǎn)：這個(gè)時(shí)候，直接將父節(jié)點(diǎn)的指針置空就可以了。并刪除自身。
  4. 有一個(gè)子節(jié)點(diǎn)，這個(gè)時(shí)候，需要將父節(jié)點(diǎn)和子節(jié)點(diǎn)互相指向。并刪除自身。
  5. 有兩個(gè)子節(jié)點(diǎn)時(shí)，需要挑選一個(gè)繼承者（后繼節(jié)點(diǎn)），然后將繼承者復(fù)制到要?jiǎng)h除的幾點(diǎn)。然后刪除繼承者原來(lái)在的節(jié)點(diǎn)。
  6. 前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)。
  7. 前驅(qū)節(jié)點(diǎn)：比當(dāng)前節(jié)點(diǎn)小的節(jié)點(diǎn)中最大的節(jié)點(diǎn)。
  8. 后繼節(jié)點(diǎn)：比當(dāng)前節(jié)點(diǎn)大的節(jié)點(diǎn)中最小的節(jié)點(diǎn)。
  9. 至于怎么找到他們你可能已經(jīng)想到了。
    1. 根據(jù)BST的特性，最大的節(jié)點(diǎn)肯定在“樹(shù)的最右邊”，最小的節(jié)點(diǎn)肯定在“樹(shù)的最左邊”。
    2. 查找前驅(qū)節(jié)點(diǎn)：就在當(dāng)前節(jié)點(diǎn)的左子樹(shù)中查找最大的。
    3. 查找后繼節(jié)點(diǎn)：就在當(dāng)前節(jié)點(diǎn)的右子樹(shù)中查找最小的。（實(shí)現(xiàn)請(qǐng)看nSuccessor）
  10. 實(shí)現(xiàn)請(qǐng)看nRemove

遍歷

  1. 前面又說(shuō)BST可以用來(lái)動(dòng)態(tài)排序，一般的排序方式都是一次性的排序，對(duì)于一直有動(dòng)態(tài)插入的數(shù)據(jù)就不是一個(gè)類型的問(wèn)題了。而B(niǎo)ST用來(lái)解決這個(gè)問(wèn)題是很好的，因?yàn)槟阒恍枰行虮闅v就可以得到一個(gè)有序的數(shù)據(jù)。
  2. 實(shí)現(xiàn)請(qǐng)看nWalk。

C實(shí)現(xiàn)（修改后的版本）

#include "StdAfx.h"

struct Node {
    int key;
    int value;
    // Node* parent;
    Node* left;
    Node* right;
};

Node* NewNode(int key, int value) {
    Node* p = (Node*)malloc(sizeof(Node));   // 刪除節(jié)點(diǎn)時(shí)要注意放掉內(nèi)存
    p->key = key;
    p->value = value;
    // p->parent = parent;
    p->left = NULL;
    p->right = NULL;
    return p;
}

Node** nSearch(Node** n, int key) {
    if (*n == NULL) {
        return n;
    }
    else if (key == (*n)->key) {
        return n;
    }
    else if (key < (*n)->key) {
        return nSearch(&(*n)->left, key);
    }
    else {
        return nSearch(&(*n)->right, key);
    }
}

void nAdd(Node** r, int key, int value) {
    Node** n = nSearch(r, key);
    if (*n == NULL) {
        *n = NewNode(key, value);
    }
    else {
        (*n)->value = value;
    }
}

int nGet(Node** n, int key) {
    Node** result = nSearch(n, key);
    if ((*result) == NULL) {
        return NULL;
    }
    else {
        return (*result)->value;
    }
}

void nWalk(Node* n) {
    if (n == NULL) {
        return;
    }
    if (n->left != NULL) {
        nWalk(n->left);
    }
    printf("%d\n", n->key);
    if (n->right != NULL) {
        nWalk(n->right);
    }
}

Node** nMin(Node** n) {
    if ((*n)->left == NULL) {
        return n;
    }
    else {
        return nMin(&(*n)->left);
    }
}

Node** nSuccessor(Node** n) {
    if ((*n)->right == NULL) {
        return NULL;
    }
    else {
        return nMin(&(*n)->right);
    }
}

int nRemove(Node** n, int key) {
    Node** d = nSearch(n, key);
    if ((*d) == NULL) {
        return -1; // 要?jiǎng)h除的幾點(diǎn)不存在
    }


    if ((*d)->left != NULL && (*d)->right != NULL) {
        Node** suc = nSuccessor(d);
        (*d)->key = (*suc)->key;
        (*d)->value = (*suc)->value;
        return nRemove(suc, (*suc)->key);
    }
    else {
        // 因?yàn)槭褂枚?jí)指針，不在需要判斷要?jiǎng)h除的節(jié)點(diǎn)本身是處在左邊還是右邊，因?yàn)橹羔樦幸呀?jīng)指向了原始我們要修改的位置。
        Node* d_child;
        if ((*d)->left != NULL) {
            d_child = (*d)->left;
            // d_child->parent = (*d)->parent;
        }
        else if ((*d)->right != NULL) {
            d_child = (*d)->right;
            // d_child->parent = (*d)->parent;
        }
        else {
            d_child = NULL;
        }

        free(*d); 
        // 同樣的，這里也不再需要判斷是不是根節(jié)點(diǎn)
        *d = d_child;
        return 0;
    }
}

int main() {
    int testData[20][2] = {
        {61, 6161},
        {30, 3030},
        {98, 9898},
        {3, 33},
        {36, 3636},
        {30, 3030},
        {6, 66},
        {54, 5454},
        {63, 6363},
        {93, 9393},
        {93, 9393},
        {76, 7676},
        {84, 8484},
        {16, 1616},
        {13, 1313},
        {76, 7676},
        {78, 7878},
        {29, 2929},
        {9, 99},
        {76, 7676}
    };

    Node* root = NULL;
    Node** rootP = &root;

    int i;
    for (i = 0; i < 20; i++) {
        nAdd(rootP, testData[i][0], testData[i][1]);
    }
    nWalk(root);

    for (i = 0; i < 20; i++) {
        nRemove(rootP, testData[i][0]);
    }
    printf("\n\n");
    nWalk(root);

    return 0;
}

C實(shí)現(xiàn)（一開(kāi)始的版本，留在這里為了讓大家對(duì)比看看修改后的）

#include "StdAfx.h"


struct Node {
    int key;
    int value;
    Node* parent;
    Node* left;
    Node* right;
};

Node* NewNode(int key, int value, Node* parent) {
    Node* p = (Node*)malloc(sizeof(Node));
    p->key = key;
    p->value = value;
    p->parent = parent;
    p->left = NULL;
    p->right = NULL;
    // 刪除節(jié)點(diǎn)時(shí)要注意free掉內(nèi)存
    return p;
}

void nAdd(Node* n, int key, int value) {
    if (key == n->key) {
        n->value = value;
    }
    else if (key < n->key) {
        if (n->left == NULL) {
            n->left = NewNode(key, value, n);
        }
        else {
            nAdd(n->left, key, value);
        }
    }
    else {
        if (n->right == NULL) {
            n->right = NewNode(key, value, n);
        }
        else {
            nAdd(n->right, key, value);
        }
    }

}

Node* nSearch(Node* n, int key) {
    if (key == n->key) {
        return n;
    }
    else if (key < n->key) {
        if (n->left == NULL) {
            return NULL;
        }
        else {
            return nSearch(n->left, key);
        }
    }
    else {
        if (n->right == NULL) {
            return NULL;
        }
        else {
            return nSearch(n->right, key);
        }
    }
}


int nGet(Node* n, int key) {
    Node* result = nSearch(n, key);
    if (result == NULL) {
        return NULL;
    }
    else {
        return result->value;
    }
}

void nWalk(Node* n) {
    if (n->left != NULL) {
        nWalk(n->left);
    }
    printf("%d\n", n->key);
    if (n->right != NULL) {
        nWalk(n->right);
    }
}

Node* nMin(Node* n) {
    if (n->left == NULL) {
        return n;
    }
    else {
        return nMin(n->left);
    }
}

Node* nSuccessor(Node* n) {
    if (n->right == NULL) {
        return NULL;
    }
    else {
        return nMin(n->right);
    }
}


int nRemove(Node* n, int key) {
    Node* d = nSearch(n, key);
    if (d == NULL) {
        return -1;
    }

    if (d->left != NULL && d->right != NULL) {
        Node* suc = nSuccessor(d);
        d->key = suc->key;
        d->value = suc->value;
        d = suc;
    }
    
    Node* d_child;
    if (d->left != NULL) {
        d_child = d->left;
        d_child->parent = d->parent;
    }
    else if (d->right != NULL) {
        d_child = d->right;
        d_child->parent = d->parent;
    }
    else {
        d_child = NULL;
    }

    if (d->parent != NULL) {
        if (d->parent->left == d) {
            d->parent->left = d_child;
        }
        else {
            d->parent->right = d_child;
        }

        free(d);
    }
    else {
        if (d_child == NULL) {
            // 這是最后一個(gè)節(jié)點(diǎn)，這個(gè)時(shí)候就不能free掉內(nèi)存了，否則main中root將指向野地址
            n->key = 0;
            n->value = 0;
            return -2;
        }
        else {
            // 當(dāng)被刪除的是根節(jié)點(diǎn)的時(shí)候，要把繼承者的數(shù)據(jù)復(fù)制到根節(jié)點(diǎn)上。
            // 因?yàn)樵诖撕瘮?shù)內(nèi)部無(wú)法改變main作用于中root的指向，如果刪除掉根節(jié)點(diǎn)，mian中的root將指向野地址
            *n = *d_child;
            free(d_child);
            return 0;
        }
        
    }
    return 0;
}

int main() {
    int testData[20][2] = {
        {61, 6161},
        {30, 3030},
        {98, 9898},
        {3, 33},
        {36, 3636},
        {30, 3030},
        {6, 66},
        {54, 5454},
        {63, 6363},
        {93, 9393},
        {93, 9393},
        {76, 7676},
        {84, 8484},
        {16, 1616},
        {13, 1313},
        {76, 7676},
        {78, 7878},
        {29, 2929},
        {9, 99},
        {76, 7676}
    };
    Node* root = NewNode(50, 10000, NULL);
    int i;
    for (i = 0; i < 20; i++) {
        nAdd(root, testData[i][0], testData[i][1]);
    }

    nWalk(root);

    nRemove(root, 50);
    for (i = 0; i < 20; i++) {
        nRemove(root, testData[i][0]);
    }
    nWalk(root);
    return 0;
}

Python實(shí)現(xiàn)

寫(xiě)到這里其實(shí)有些困了，Python版本的刪除我記得好像是有一些bug，因?yàn)槲艺娴氖菓械冒岩环莶恢庇X(jué)的代碼改對(duì)。而且本質(zhì)上來(lái)講這兩個(gè)刪除函數(shù)都是無(wú)可救藥的crap code, 請(qǐng)?jiān)徫覍⑦@些垃圾發(fā)布上來(lái)，改天我會(huì)盡量重寫(xiě)一份不辣眼睛的版本來(lái)贖罪，請(qǐng)?jiān)彙?/del> C語(yǔ)言重寫(xiě)后的版本我已經(jīng)貼了上來(lái)，大家可以對(duì)比一下原來(lái)的版本，雖然是小修改，但是很滿意很美觀的改動(dòng)。

有"tree"的版本：

# Python code:
class Node(object):
    def __init__(self, key, data, parent=None):
        self.key = key
        self.data = data
        self.parent = parent
        self.left = None
        self.right = None

    def add_child(self, key, data):
        if key == self.key:
            self.data = data
            return
        elif key < self.key:
            if self.left is None:
                self.left = Node(key, data, self)
            else:
                self.left.add_child(key, data)
        else:
            if self.right is None:
                self.right = Node(key, data, self)
            else:
                self.right.add_child(key, data)

    def get(self, key):
        if key == self.key:
            return self
        elif key < self.key:
            if self.left is None:
                return None
            else:
                return self.left.get(key)
        else:
            if self.right is None:
                return None
            else:
                return self.right.get(key)

    def get_data(self, key):
        r = self.get(key)
        if r is None:
            return None
        else:
            return r.data

    def in_order_walk(self):
        if self.left is not None:
            self.left.in_order_walk()
        print(self.key)
        if self.right is not None:
            self.right.in_order_walk()

    def get_max(self):
        if self.right is None:
            return self
        else:
            return self.right.get_max()

    def get_min(self):
        if self.left is None:
            return self
        else:
            return self.left.get_min()

    def predecessor(self):
        if self.left is not None:
            return self.left.get_max()
        else:
            return None

    def successor(self):
        if self.right is not None:
            return self.right.get_min()
        else:
            return None

    def remove(self, key):
        d = self.get(key)

        if not d.left and not d.right:
            if d.parent is None:
                # self = None
                return
            elif d.parent.left == d:
                d.parent.left = None
            else:
                d.parent.right = None
        elif bool(d.left) is not bool(d.right):
            if d.left:
                if d.parent.left == d:
                    d.parent.left = d.left
                    d.left.parent = d.parent
                else:
                    d.parent.right = d.left
                    d.left.parent = d.parent
            else:
                if d.parent.right == d:
                    d.parent.right = d.right
                    d.right.parent = d.parent
                else:
                    d.parent.left = d.right
                    d.right.parent = d.parent
        else:
            successor = d.successor()
            d.key = successor.key
            d.data = successor.data
            successor.remove(successor.key)


class Tree(object):
    def __init__(self, root):
        self.root = root

    def remove(self, key):
        d = self.root.get(key)
        if d.left and d.right:
            successor = d.successor()
            d.key = successor.key
            d.data = successor.data
            d = successor
        else:
            pass

        if d.left:
            d_child = d.left
            d_child.parent = d.parent
        elif d.right:
            d_child = d.right
            d_child.parent = d.parent
        else:
            d_child = None

        if d.parent:
            if d.parent.left == d:
                d.parent.left = d_child
            else:
                d.parent.right = d_child
        else:
            self.root = None

    def in_order_walk(self):
        if self.root:
            self.root.in_order_walk()
        else:
            print(None)

    def __getattr__(self, item):
        return getattr(self.root, item)


def main():
    data_list = [
        [20, 2222],
        [30, 3333],
        [40, 4444],
        [50, 5555],
        [60, 6666],
        [70, 7777],
        [80, 8888],
        [90, 9999],
    ]
    middle = data_list[5]
    tree = Tree(Node(middle[0], middle[1]))
    for i in data_list:
        tree.root.add_child(i[0], i[1])
    tree.add_child(1, 111)
    tree.remove(70)
    tree.in_order_walk()


if __name__ == '__main__':
    main()
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容