二分探索木：削除
記事二分探索木：検索と挿入では、二分探索木に要素を挿入する方法と、二分探索木内の値を検索する方法について説明しました。今回は、二分探索木からノードを削除する方法について説明します。
二分探索木の削除操作
二分探索木にノードを挿入するのは比較的簡単です。しかし、ノードを削除する際には、複数の可能性に注意しなければなりません。以下の 3つのケースが発生する可能性があります。
-
削除されるノードには子がありません。
リーフノードには子がないので、何も気にする必要はありません。リーフノードを NULL に置き換えて、このノードに割り当てられた領域を解放することができます。
-
削除するノードの子（左または右の子）が 1つしかない場合。
この場合、そのノードの子を格納し、元の位置から削除します。そして、削除されたノードの元の位置に子ノードが挿入されます。
-
削除されるノードは、左子と右子の両方の子を持っています。
ここでは、単純にノードを削除したり、子ノードに置き換えたりすることができないので、これが最も厄介なケースです。この場合、ノード minnode の右サブツリーの中で最も小さいノードを見つけます。削除したいノードの値を minnode の値に置き換えて再帰的に delete を呼び出します。
二分探索木の削除図
-
削除されるノードには子はありません。
ノード7には子がありません; 単純にツリーから削除してください。 -
削除されるノードには子が 1つしかありません。
ノード15には 1つの子7があるので、15を削除する前にその子を処理する必要があります。そのため、まずそれをコピーしてから15に置き換えます。 -
削除するノードは両方の子を持っています。
ノード21には、15と27の 2つの子があります。右サブツリーの中で最も小さい要素23を見つけ、それを21に置き換えてから、再帰を呼び出して右サブツリーから23を削除します。
二分探索木削除アルゴリズム
-
root==NULLの場合はNULLを返します。 -
root->key<Xの場合、左サブツリーを破棄し、右サブツリーから削除する要素を探します。root->right=deleteNode(root->right,X)。 -
それ以外の場合、
root->key>Xならば、右サブツリーを破棄し、左サブツリーで削除する要素を探します。root->left=deleteNode(root->left, X)。 -
それ以外の場合、
root->key==X, 次の 3つのケースに従ってアクションを実行します。- (
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) となります。
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