算法導(dǎo)論 - 二叉搜索樹(shù)（BST）

二叉搜索樹(shù)

顧名思義，一棵二叉搜索樹(shù)是以一棵二叉樹(shù)來(lái)組織的。如下圖所示，這樣一棵樹(shù)可以使用一個(gè)鏈表數(shù)據(jù)結(jié)構(gòu)來(lái)表示，其中每個(gè)結(jié)點(diǎn)就是一個(gè)對(duì)象，除了key外，每個(gè)結(jié)點(diǎn)還包括屬性left 、right、和p，它們分別指向結(jié)點(diǎn)的左孩子、右孩子和雙親。如果某個(gè)孩子結(jié)點(diǎn)和父結(jié)點(diǎn)不存在，則相應(yīng)屬性的值為nil，根結(jié)點(diǎn)是樹(shù)中唯一父指針為nil的結(jié)點(diǎn)

1.png

二叉搜索樹(shù)中的關(guān)鍵字總是以滿足二叉搜索樹(shù)性質(zhì)的方式來(lái)存儲(chǔ)：

設(shè)x是二叉搜索樹(shù)中的一個(gè)結(jié)點(diǎn)，如果y是x的左子樹(shù)中的一個(gè)結(jié)點(diǎn)，那么y.key \leq x.key。如果y是x的右子樹(shù)中的一個(gè)結(jié)點(diǎn)，那么y.key \geq x.key

如圖（a）中，樹(shù)根的關(guān)鍵字是6，在其左子樹(shù)中有關(guān)鍵字2、5和5，它們均不大于6；而其右子樹(shù)中有關(guān)鍵字7和8，它們均不小于6。所以這個(gè)性質(zhì)在樹(shù)中的每個(gè)結(jié)點(diǎn)都成立。

二叉搜索樹(shù)的性質(zhì)允許我們通過(guò)一個(gè)簡(jiǎn)單的遞歸算法來(lái)按序輸出二叉搜索樹(shù)中的所有關(guān)鍵字，算法是我們熟悉的中序遍歷

typedef struct Node
{
    struct Node *p;
    struct Node *left;
    struct Node *right;
    int key;
} Node;

void InorderTreeWalk(Node *x) // 中序遍歷樹(shù)x
{
    if (x != nullptr) {
        InorderTreeWalk(x->left); // 遞歸左孩子
        cout<<x->key<<endl; // 輸出根節(jié)點(diǎn)關(guān)鍵字
        InorderTreeWalk(x->right); // 遞歸右孩子
    }
}

遍歷一棵有n個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)，需要耗費(fèi)O(n)的時(shí)間，因?yàn)槌醮握{(diào)用后，對(duì)于樹(shù)中的每個(gè)結(jié)點(diǎn)這個(gè)過(guò)程恰好要自己調(diào)用兩次；一次是它的左孩子，另一次是它的右孩子

查詢二叉搜索樹(shù)

2.jpeg

我們經(jīng)常需要查找一個(gè)存儲(chǔ)在二叉搜索樹(shù)中的關(guān)鍵字，下面將討論并且說(shuō)明在任何高度為h的二叉搜索樹(shù)上，如何在O(h)時(shí)間內(nèi)完成每個(gè)操作

查找

使用下面的代碼在一棵二叉搜索樹(shù)中查找一個(gè)具有給定關(guān)鍵字的結(jié)點(diǎn)，輸入一個(gè)指向樹(shù)根的指針和一個(gè)關(guān)鍵字k，如果這個(gè)節(jié)點(diǎn)存在，那么返回關(guān)鍵字為k的指針，否則為nil

Node * TreeSearch(Node *x, int k)
{
    if (x == nullptr || k == x->key) {
        return x;
    }

    if (k < x->key)
    {
        return TreeSearch(x->left, k);
    }
    else
    {
        return TreeSearch(x->right, k);
    }
}

  • 這個(gè)過(guò)程是從樹(shù)根開(kāi)始查找的，并沿著這顆樹(shù)中的一條簡(jiǎn)單路徑向下進(jìn)行。對(duì)于遇到的每個(gè)結(jié)點(diǎn)x，比較關(guān)鍵字k與x.key，如果兩個(gè)關(guān)鍵字相等，查找就終止了，該結(jié)點(diǎn)就是我們需要查找的結(jié)點(diǎn)。

  • 如果k小于x.key，則查找x的左子樹(shù)，因?yàn)槎嫠阉鳂?shù)的性質(zhì)告訴了我們k不可能在右子樹(shù)中。相應(yīng)的，如果k大于x.key，查找在右子樹(shù)進(jìn)行。

  • 從樹(shù)根開(kāi)始遞歸期間遇到的結(jié)點(diǎn)就形成了一條向下的簡(jiǎn)單路徑，所以TreeSearch的運(yùn)行時(shí)間是O(h)，其中h是樹(shù)的高度

除了遞歸方式，采用迭代方式是效率更高的方式

Node * InteractiveTreeSearch(Node *x, int k)
{
    while (x != nullptr && k != x->key) {
        if (k < x->key)
        {
            x = x->left;
        }
        else
        {
            x = x->right;
        }
    }
    return x;
}

最大關(guān)鍵字元素和最小關(guān)鍵字元素

通過(guò)從樹(shù)根開(kāi)始沿著left孩子指針直到遇到一個(gè)nil，

  • 最小關(guān)鍵字元素
Node *TreeMinimum(Node *x)
{
    while (x->left != nullptr) {
        x = x->left;
    }
    return x;
}

二叉樹(shù)的性質(zhì)保證了上面查找的正確性。

如果結(jié)點(diǎn)x沒(méi)有左子樹(shù)，那么由于x的右子樹(shù)中的每個(gè)關(guān)鍵字都至少大于或等于x.key，則以x為根的子樹(shù)中的最小關(guān)鍵字是x.key。如果結(jié)點(diǎn)x有左子樹(shù)，那么由于其右子樹(shù)中沒(méi)有關(guān)鍵字小于x.key，且在左子樹(shù)中的每個(gè)關(guān)鍵字不大于x.key，則以x為根的子樹(shù)中的最小關(guān)鍵字一定在以x.left為根的子樹(shù)中

  • 最大關(guān)鍵字元素

最大元素一定是沿著right孩子指針不斷向下查找，直到遇到第一個(gè)空指針；

Node *TreeMaxmum(Node *x)
{
    while (x->right != nullptr) {
        x = x->right;
    }
    return x;
}

這兩個(gè)過(guò)程在一棵高度為h的樹(shù)上均能在O(h)的時(shí)間內(nèi)執(zhí)行完。

后繼和前驅(qū)

給定一棵二叉搜索樹(shù)，有時(shí)候需要按中序遍歷的次序查找它的后繼。如果所有的關(guān)鍵字互不相同，則一個(gè)結(jié)點(diǎn)x的后繼是大于x.key的最小關(guān)鍵字的結(jié)點(diǎn)

后繼

Node *TreeSuccessor(Node *T, int t)
{
    // 查找結(jié)點(diǎn)
    Node *x = TreeSearch(T, t);
    Node *y = nullptr;

    // 右子樹(shù)非空，即查找最小關(guān)鍵字
    if (x->right != nullptr) {
        y = TreeMinimum(x->right);
        return y;
    }

    // 查找結(jié)點(diǎn)的父指針
    y = x->p;
    while (y != nullptr && x == y->right) {
        x = y;
        y = y->p;
    }
    return y;
}

如果結(jié)點(diǎn)x的右子樹(shù)非空，那么x的后繼恰好是x右子樹(shù)中的最左結(jié)點(diǎn)。也可以理解為最小關(guān)鍵字

2.jpeg

如果結(jié)點(diǎn)x的右子樹(shù)為空并有一個(gè)后繼y，那么y就是x的最底層祖先，并且y的左孩子也是x的一個(gè)祖先（比如：上圖中關(guān)鍵字為13的結(jié)點(diǎn)的后繼是關(guān)鍵字為15的結(jié)點(diǎn)）。為了找到y(tǒng)，只需要簡(jiǎn)單地從x開(kāi)始沿樹(shù)而上直到遇到這樣一個(gè)結(jié)點(diǎn)：這個(gè)結(jié)點(diǎn)是它的雙親的左孩子

前驅(qū)

Node *TreePredecessor(Node *T, int t)
{
    // 查找元素t
    Node *x = TreeSearch(T, t);
    Node *y = nullptr;

    // 左子樹(shù)非空
    if (x->left != nullptr)
    {
        return  TreeMaxmum(x->left);
    }

    // 查結(jié)點(diǎn)的父指針
    y = x->p;
    while ( y != nullptr && x == y->left) {
        x = y;
        y = y->p;
    }
    return y;
}

對(duì)于樹(shù)的后繼和前驅(qū)的查找，運(yùn)行時(shí)間為O(h)

插入和刪除

插入和刪除操作會(huì)引起由二叉搜索樹(shù)表示的動(dòng)態(tài)集合的變化。所以一定要修改數(shù)據(jù)結(jié)構(gòu)來(lái)反映這個(gè)變化，但修改要保持二叉搜索樹(shù)性質(zhì)的成立

插入

向一個(gè)二叉搜索樹(shù)中插入一個(gè)x結(jié)點(diǎn)，只需要不斷比較x.key與當(dāng)前結(jié)點(diǎn)z.key的大小，若小于，則肯定是向z的左子樹(shù)插入，否則向z的右子樹(shù)插入，循環(huán)比較，直到遇到當(dāng)前結(jié)點(diǎn)的左/右子樹(shù)為空為止。這時(shí)候已經(jīng)找到了要插入的結(jié)點(diǎn)的父結(jié)點(diǎn)的位置，最后判斷是左子樹(shù)還是右子樹(shù)即可

Node * TreeInsert(Node *root, Node *z)
{
    Node *y = nullptr;
    Node *x = root;

    // 節(jié)點(diǎn)非空，看是左子樹(shù)還是右子樹(shù)插入
    while (x != nullptr) {
        y = x;
        if (z->key < x->key)
        {
            x = x->left;
        }
        else
        {
            x = x->right;
        }
    }

    z->p = y;
    if (y == nullptr) // 建立第一個(gè)節(jié)點(diǎn)
    {
        root = z;
    }
    else if (z->key < y->key) // 小于父結(jié)點(diǎn)即位左子樹(shù)
    {
        y->left = z;
    }
    else // 大于即為右子樹(shù)
    {
        y->right = z;
    }

    return root;
}
3.jpeg

比如：上圖插入結(jié)點(diǎn)，關(guān)鍵字為13，可以對(duì)照代碼和圖形理解

刪除

從一棵二叉搜索樹(shù)T中刪除一個(gè)結(jié)點(diǎn)z，存在3種情況：

1、如果z沒(méi)有孩子結(jié)點(diǎn)，那么只是簡(jiǎn)單地將它刪除，并修改父結(jié)點(diǎn)，用nil作為孩子來(lái)替換z
2、如果z只有一個(gè)孩子，那么將孩子提升到樹(shù)中z的位置，并修改z的父結(jié)點(diǎn)，用z的孩子來(lái)替換z
3、如果z有兩個(gè)孩子，那么找z的后繼y（一定在z的右子樹(shù)中），并讓y占據(jù)樹(shù)中z的位置。z的原來(lái)右子樹(shù)部分成為y的新的右子樹(shù)，并且z的左子樹(shù)成為y的新的左子樹(shù)

對(duì)照?qǐng)D來(lái)理解上面幾種情況

  • 如果z沒(méi)有左孩子（如下圖），那么用其右孩子來(lái)替換z，這個(gè)右孩子可以是nil，也可以不是nil。當(dāng)右孩子是nil的時(shí)候，此時(shí)就是z沒(méi)有孩子結(jié)點(diǎn)的情形。當(dāng)右孩子非nil時(shí)，這就是z僅有一個(gè)孩子的情況，該孩子是其右孩子
屏幕快照 2018-12-12 上午9.16.42.png
  • 如果z僅有一個(gè)孩子且為左孩子（如下圖），那么用其左孩子替換z
屏幕快照 2018-12-12 上午9.16.50.png
  • z既有左孩子也有右孩子。如果y是z的右孩子（如下圖）,那么用y替換z，并僅留下y的右孩子
屏幕快照 2018-12-12 上午9.17.03.png
  • 如果y位于z的右子樹(shù)中但并不是z的右孩子（如下圖）,這種情況下，先用y的右孩子替換y，然后再用y替換z
屏幕快照 2018-12-12 上午9.17.19.png

在二叉搜索樹(shù)內(nèi)移動(dòng)子樹(shù)，它是用另一棵子樹(shù)替換一棵子樹(shù)并成為其雙親的孩子結(jié)點(diǎn)

移動(dòng)子樹(shù)

void Transplant(Node **T, Node *u, Node *v) // 用結(jié)點(diǎn)v替換結(jié)點(diǎn)u
{
    if (u->p ==  nullptr) // 父結(jié)點(diǎn)不存在,那么u為根結(jié)點(diǎn)
    {
        *T = v;
    }
    else if (u == u->p->left) // u為左孩子,那么將v作為左孩子
    {
        u->p->left = v;
    }
    else // u為右孩子,那么將v作為右孩子
    {
        u->p->right = v;
    }

    if (v != nullptr) // v不為nil，那么更新父結(jié)點(diǎn)
    {
        v->p = u->p;
    }
}

刪除結(jié)點(diǎn)

Node * TreeDelete(Node *T, int k)
{
    Node *z = TreeSearch(T, k); // 查找結(jié)點(diǎn)z
    Node *y = nullptr;

    if (z->left == nullptr) // 結(jié)點(diǎn)z沒(méi)有左孩子
    {
        Transplant(&T, z, z->right);
    }
    else if (z->right == nullptr) // 結(jié)點(diǎn)z沒(méi)有右孩子
    {
        Transplant(&T, z, z->left);
    }
    else // 結(jié)點(diǎn)z有兩個(gè)孩子
    {
        y = TreeMinimum(z->right); // 找右子樹(shù)的最小結(jié)點(diǎn)

        if (y->p != z) { // y的父結(jié)點(diǎn)不是z
            Transplant(&T, y, y->right);
            y->right = z->right;
            y->right->p = y;
        }

        Transplant(&T, z, y);
        y->left = z->left;
        y->left->p = y;
    }
    return T;
}

簡(jiǎn)單使用

// 創(chuàng)建搜索二叉樹(shù)
Node * TreeEstablish(int *a, int length)
{
    Node *root = nullptr;
    for (int i=0 ; i < length; i++) {
        Node *node = (Node *)malloc(sizeof(Node));
        node->key = a[i];
        node->p = nullptr;
        node->left = nullptr;
        node->right = nullptr;
        root = TreeInsert(root, node);
    }
    return root;
}

int main(int argc, const char * argv[]) {
    int a[] = {2,3,4,6,15,7,18,17,20,13,9};
    int length = sizeof(a)/sizeof(a[0]);

    Node *T;
    T = TreeEstablish(a, length); // 建立二叉搜索樹(shù)
    InorderTreeWalk(T);  // 中序遍歷打印
    cout<<"6 successor is "<<TreeSuccessor(T, 6)->key<<endl; // 后繼查找
    cout<<"18 predecessor is "<<TreePredecessor(T, 18)->key<<endl; // 前驅(qū)查找
    T = TreeDelete(T, 2); // 刪除結(jié)點(diǎn)
    TreeInorderPrint(T); // 刪除結(jié)點(diǎn)之后的二叉搜索樹(shù)
    return 0;
}

參考

《算法導(dǎo)論》

最后編輯于 ：
?著作權(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)容