二叉搜索树删除
在二叉搜索树：搜索和插入一文中，我们讨论了如何在二叉搜索树中插入一个元素，以及如何在二叉搜索树中搜索一个值。在本文中，我们将讨论如何从二叉搜索树中删除一个节点。
二叉搜索树的删除操作
在二叉搜索树中插入一个节点是比较简单的。但是，在删除一个节点时，我们必须考虑到多种可能性。以下 3 种情况可能发生。
-
要删除的节点没有子节点，它是一个叶子节点。
这是最简单的情况，因为叶子节点没有子节点，因此我们不需要关心任何事情。我们可以用 NULL 替换叶子节点，并释放分配给这个节点的空间。
-
要删除的节点只有一个子节点（左或右子节点）。
在这种情况下，我们存储该节点的子节点，并将该节点从原来的位置删除。然后将子节点插入到被删除节点的原始位置。
-
要删除的节点有两个子节点，左子节点和右子节点。
这是最棘手的情况，因为在这里，我们不能简单地删除或用它的子节点替换。在这种情况下，我们找到节点 minnode 右侧子树中最小的节点。用 minnode 的值代替要删除的节点的值，并对这个节点递归调用 delete。
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 <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 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