二叉搜索树删除-ag捕鱼王app官网

在二叉搜索树：搜索和插入一文中，我们讨论了如何在二叉搜索树中插入一个元素，以及如何在二叉搜索树中搜索一个值。在本文中，我们将讨论如何从二叉搜索树中删除一个节点。

二叉搜索树的删除操作

在二叉搜索树中插入一个节点是比较简单的。但是，在删除一个节点时，我们必须考虑到多种可能性。以下 3 种情况可能发生。

• 要删除的节点没有子节点，它是一个叶子节点。

bst 删除图解

• 要删除的节点没有子节点，它是一个叶子。

  
  节点 7 没有子节点，只需将其从树中删除即可，没有违反 bst 属性。

• 要删除的节点只有一个子节点。

  
  节点 15 有一个子节点 7；我们需要在删除 15 之前处理好它。所以，我们先复制它，然后用 15 代替。

• 要删除的节点有两个子节点。

  
  节点 21 有两个子节点-15 和 27。我们找到右侧子树中最小的元素 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 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)。