二叉搜尋樹刪除

Harshit Jindal 2023年1月30日 2021年2月28日
  1. 二叉搜尋樹的刪除操作
  2. BST 刪除圖解
  3. BST 刪除演算法
  4. 二叉搜尋樹刪除實現
  5. 二叉搜尋樹刪除演算法的複雜度
二叉搜尋樹刪除

二叉搜尋樹:搜尋和插入一文中,我們討論瞭如何在二叉搜尋樹中插入一個元素,以及如何在二叉搜尋樹中搜尋一個值。在本文中,我們將討論如何從二叉搜尋樹中刪除一個節點。

二叉搜尋樹的刪除操作

在二叉搜尋樹中插入一個節點是比較簡單的。但是,在刪除一個節點時,我們必須考慮到多種可能性。以下 3 種情況可能發生。

  • 要刪除的節點沒有子節點,它是一個葉子節點。

這是最簡單的情況,因為葉子節點沒有子節點,因此我們不需要關心任何事情。我們可以用 NULL 替換葉子節點,並釋放分配給這個節點的空間。

  • 要刪除的節點只有一個子節點(左或右子節點)。

在這種情況下,我們儲存該節點的子節點,並將該節點從原來的位置刪除。然後將子節點插入到被刪除節點的原始位置。

  • 要刪除的節點有兩個子節點,左子節點和右子節點。

這是最棘手的情況,因為在這裡,我們不能簡單地刪除或用它的子節點替換。在這種情況下,我們找到節點 minnode 右側子樹中最小的節點。用 minnode 的值代替要刪除的節點的值,並對這個節點遞迴呼叫 delete。

BST 刪除圖解

  • 要刪除的節點沒有子節點,它是一個葉子。

    二叉搜尋樹刪除操作
    節點 7 沒有子節點,只需將其從樹中刪除即可,沒有違反 BST 屬性。

  • 要刪除的節點只有一個子節點。

    二叉搜尋樹刪除操作
    節點 15 有一個子節點 7;我們需要在刪除 15 之前處理好它。所以,我們先複製它,然後用 15 代替。

  • 要刪除的節點有兩個子節點。

    二叉搜尋樹刪除操作
    節點 21 有兩個子節點-1527。我們找到右側子樹中最小的元素 23,用 21 代替,然後呼叫遞迴從右側子樹中刪除 23

BST 刪除演算法

  • 如果 root == NULL , 則返回 NULL
  • 如果 root->key<X, 那麼丟棄左邊子樹,在右邊子樹中找到要刪除的元素。

    root->right=deleteNode(root->right,X)

  • Else 如果 root->key>X,則丟棄右側子樹,在左側子樹中找到要刪除的元素。

    root->left=deleteNode(root->left, X)

  • Else 如果 root->key==X,則根據三種情況進行操作。
    • 如果(root->left == NULL 並且 root->right == NULL),刪除 root 並返回 NULL
    • 否則如果(root->right == NULL),複製左邊的子樹,用要刪除的節點代替。
    • 否則如果(root->left == NULL),複製右邊的子樹,用要刪除的節點代替。
    • 否則如果(root->left && root->right ),則在右側子樹 minnode 中找到最小的節點,並將其替換為要刪除的節點。從右子樹中遞迴刪除 minnode
  • 返回指向原 root 的指標。

二叉搜尋樹刪除實現

#include <iostream>
using namespace std;

class Node {
public:
    int key;
    Node *left, *right;
};

Node *newNode(int item) {
    Node *temp = new Node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

void inorder(Node *root) {
    if (root != NULL) {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }
}

void insert(Node* &root, int key)
{
    Node* toinsert = newNode(key);
    Node* curr = root;
    Node* prev = NULL;

    while (curr != NULL) {
        prev = curr;
        if (key < curr->key)
            curr = curr->left;
        else
            curr = curr->right;
    }
    if (prev == NULL) {
        prev = toinsert;
        root = prev;
    }

    else if (key < prev->key){
        prev->left = toinsert;
    }

    else{
        prev->right = toinsert;
    }
}

Node* getmin( Node* root)
{
    Node* curr = root;

    while (curr && curr->left) {
        curr = curr->left;
    }

    return curr;
}

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

    if (key < root->key)
        root->left = deleteNode(root->left, key);

    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        if (root->left == NULL) {
            Node* temp = root->right;
            delete(root);
            return temp;
        }
        else if (root->right == NULL) {
            Node* temp = root->left;
            delete(root);
            return temp;
        }

        Node* temp = getmin(root->right);

        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

int main() {
    Node *root = NULL;
    insert(root, 5);
    insert(root, 3);
    insert(root, 8);
    insert(root, 6);
    insert(root, 4);
    insert(root, 2);
    insert(root, 1);
    insert(root, 7);
    inorder(root);
    cout << "\n";
    deleteNode(root, 5);
    inorder(root);
}

二叉搜尋樹刪除演算法的複雜度

時間複雜度

  • 平均情況

在平均情況下,從 BST 中刪除一個節點的時間複雜度與二叉搜尋樹的高度相當。平均來說,一個 BST 的高度是 O(logn)。當形成的 BST 是一個平衡的 BST 時,就會出現這種情況。因此,時間複雜度 [Big Theta]:O(logn)

  • 最佳情況

最好的情況是當樹是一個平衡的 BST 時。最佳情況下,刪除的時間複雜度為 O(logn)。它和平均情況下的時間複雜度是一樣的。

  • 最壞情況

在最壞的情況下,我們可能需要從根節點到最深的葉子節點,即樹的整個高度 h。如果樹是不平衡的,即它是傾斜的,樹的高度可能會變成 n,因此插入和搜尋操作的最壞情況下的時間複雜性是 O(n)

空間複雜度

由於遞迴呼叫所需的額外空間,演算法的空間複雜度為 O(n)

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相關文章 - Data Structure

相關文章 - Binary Tree

相關文章 - Binary Search Tree