二叉搜尋樹刪除
在二叉搜尋樹：搜尋和插入一文中，我們討論瞭如何在二叉搜尋樹中插入一個元素，以及如何在二叉搜尋樹中搜尋一個值。在本文中，我們將討論如何從二叉搜尋樹中刪除一個節點。
二叉搜尋樹的刪除操作
在二叉搜尋樹中插入一個節點是比較簡單的。但是，在刪除一個節點時，我們必須考慮到多種可能性。以下 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