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