二分探索木の反復的挿入
前回の記事二分探索木では、二分探索木にノードを挿入するための再帰的なアプローチについて説明しました。この記事では、BST にノードを挿入するための反復的アプローチについて説明します。反復挿入アルゴリズムでは余分なスペースを必要としないため、再帰的な方法よりも優れています。
二分探索木反復挿入アルゴリズム
root を BST のルートノード、key を挿入したい要素とします。
-
挿入するノードを作成する -
toinsert. -
2つのポインタを初期化します。(
currはツリーを横断し、prevはその軌跡を維持します)。 -
curr!=NULLのときは、以下のようにする。prevをcurrに更新してcurrの軌跡を維持します。curr->data>keyの場合、currをcurr->leftに設定し、右のサブツリーを破棄します。- if
curr->data<key、currをcurr->rightに設定し、左サブツリーを破棄します。
-
prev==NULLならば、ツリーが空であることを意味します。ノードrootを作成する。 -
それ以外の場合、
prev->data>keyならば、prevの左にtoinsertを挿入し、prev->left=toinsertとします。 -
それ以外の場合、
prev->data<keyならば、toinsertをprevの右に挿入し、prev->right=toinsert。
二分探索木反復挿入の図
-
まず、
rootノードを作成して BST を初期化し、その中に5を挿入します。 -
3は5より小さいので、5の左に挿入します。 -
4は5より小さいが3より大きいので、3の右に挿入され、4の左に挿入されます。 -
2は現在のツリーの中で最も小さい要素なので、一番左の位置に挿入されます。 -
1は現在のツリーの中で最も小さい要素なので、左端に挿入される。 -
6は現在のツリーの中で最大の要素なので、右端の位置に挿入されます。
これが、二分探索木内に要素を挿入する方法です。
二分探索木反復挿入の実装
#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;
}
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);
}
二分探索木反復挿入アルゴリズムの複雑さ
時間計算量
- 平均ケース
平均的なケースでは、BST にノードを挿入する時間の複雑さは 2 値探索木の高さのオーダーです。平均して BST の高さは O(logn) です。これは、形成される BST がバランスのとれた BST である場合に発生する。したがって、時間の複雑さは [Big Theta]: O(logn) のオーダーです。
- 最良の場合
ベストケースは木がバランスのとれた BST である場合です。ベストケースの挿入の時間複雑度は O(logn) のオーダーです。これは平均ケースの時間的複雑さと同じです。
- 最悪の場合
最悪の場合、根元から最深部の葉のノードまで、つまり木の高さ h 全体を辿らなければならないかもしれません。木が不均衡である場合、すなわち、木が歪んでいる場合、木の高さは n になる可能性があり、そのため、挿入と探索の両方の操作の最悪の場合の時間的複雑さは O(n) となります。
空間の複雑さ
反復挿入操作の空間の複雑さは O(1) です。
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