二叉搜索树删除

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