二分探索木

Harshit Jindal 2023年10月12日
  1. 二分探索木の検索操作
  2. BST 検索アルゴリズム
  3. BST 検索イラスト
  4. 二分探索木での挿入
  5. 二分探索木の挿入アルゴリズム
  6. BST 挿入イラスト
  7. 二分探索木の検索と挿入の実装
  8. BST 挿入と検索アルゴリズムの計算複雑性
二分探索木

二分探索木(BST)は、順序付きノードベースの二分木データ構造です。ノードは、値と 2つの子ノード(二分木は最大 2つの子ノードを持ちます)を左右に持ちます。ルートノードを除いて、すべてのノードは親ノードのみが参照できます。BST は以下のような性質を持っています。

  • 左サブツリーのすべてのノードはルートノードよりも小さい。
  • 右サブツリーのすべてのノードはルートノードよりも大きい。
  • 左と右のサブツリーも二分探索木でなければなりません。

二値探索木の例

左側の木は BST の性質をすべて満たしています。一方、右側の木は、左のサブツリーのノードがすべて小さく、右のサブツリーのノードがすべて大きくなっており、BST のように見えます。しかし、左サブツリーのノード 1 は、ノード 4 よりは小さいが、ルートノード 3 よりは大きくないので、BST の性質を満たしていません。したがって、これは BST ではありません。

これは順序付きのデータ構造なので、入力された要素は常にソートされた形で整理されます。BST に格納されているデータをソートされた順序で取得するために、順序内探索を使用することができます。二分探索と同じように、O(logn) でデータを検索することができることから、その名がついた。

二分探索木の検索操作

BST では、ルートの右側にあるすべての要素が大きいことがわかっています。したがって、探している対象の要素がルートよりも小さい場合、右サブツリー全体を無視することができます。同様に、要素がルートよりも大きい場合は、左サブツリーを無視することができます。ツリーを使い切るか、サブツリーのルートとして目的の要素を見つけるまで、同様の方法で移動します。BST がバランスされている場合(すべてのノードについて、左サブツリーと右サブツリーの高さの差が 1 よりも小さい場合、ツリーはバランスされたツリーと呼ばれます)、BST 内の探索は二分探索と似たように実行されますが、バランスされていないツリーの場合、すべてのノードが同じ側に存在し、探索は線形探索と似たように実行されるかもしれません。

BST 検索アルゴリズム

root を BST のルートノード、X を検索対象の要素とします。

  • root == NULL の場合は NULL を返す。
  • X == root->data の場合は root を返します。
  • もし X < root->data ならば、リターン search(root->left)
  • X > root->data の場合、search(root->right) を返す。

BST 検索イラスト

二分探索ステップ

上記の BST があって、要素 X = 25 を求めたいとします。

  • 根元の要素を X と比較すると、41 > 25 となるので、右半分を捨てて左サブツリーに移動する。
  • 左サブツリーのルートは 23 < 25 なので、その左サブツリーを破棄して右に移動します。
  • 新しいルート 28 < 25 なので、左に向かって移動し、要素 X25 に等しいことを見つけてノードを返します。

二分探索木での挿入

二分探索木の内部に要素を挿入するアルゴリズムは、要素を挿入する前にその正しい位置を見つけなければならないので、BST 内部の要素を検索するのとよく似ています。挿入機能と検索機能の唯一の違いは、検索の場合は目的の値を含むノードを返すのに対し、挿入の場合はそのノードの適切な位置に新しいノードを作成することです。

二分探索木の挿入アルゴリズム

root を BST のルートノード、X を挿入したい要素とします。

  • root == NULL の場合は、data = X で新たに形成されたノードを返す。
  • if (X < root->data), root->left = insert(root->left, X).
  • else if (X > root->data) , root->right = insert(root->right, X).
  • 元の root へのポインタを返します。

BST 挿入イラスト

BST インサートイラスト

  • まず、root ノードを作成して BST を初期化し、その中に 5 を挿入します。
  • 35 より小さいので、5 の左に挿入します。
  • 45 より小さいが 3 より大きいので、3 の右に挿入され、4 の左に挿入されます。
  • 2 は現在のツリーの中で最も小さい要素なので、一番左の位置に挿入されます。
  • 1 は現在のツリーの中で最も小さい要素なので、左端に挿入される。
  • 6 は現在のツリーの中で最大の要素なので、右端の位置に挿入されます。

これが BST 内に要素を挿入する方法です。

二分探索木の検索と挿入の実装

#include <iostream>
using namespace std;

class Node {
 public:
  int key;
  Node *left, *right;
};

Node *newNode(int item) {
  Node *temp = (Node *)malloc(sizeof(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);
  }
}

Node *insert(Node *root, int key) {
  if (root == NULL) return newNode(key);
  if (key < root->key)
    root->left = insert(root->left, key);
  else
    root->right = insert(root->right, key);

  return root;
}

Node *search(Node *root, int key) {
  if (root == NULL || root->key == key) return root;

  if (root->key < key) return search(root->right, key);

  return search(root->left, key);
}
int main() {
  Node *root = NULL;
  root = insert(root, 5);
  root = insert(root, 3);
  root = insert(root, 8);
  root = insert(root, 6);
  root = insert(root, 4);
  root = insert(root, 2);
  root = insert(root, 1);
  root = insert(root, 7);
  cout << search(root, 5)->key << endl;
}

BST 挿入と検索アルゴリズムの計算複雑性

時間計算量

  • 平均ケース

平均的なケースでは, BST のノード挿入や要素検索の時間的複雑さは 2 値探索木の高さのオーダーである. 平均して BST の高さは O(logn) です。これは、形成される BST がバランスのとれた BST である場合に発生します。したがって、時間の複雑さは [Big Theta]: O(logn) のオーダーです。

  • 最良の場合

ベストケースは木がバランスのとれた BST である場合です。挿入と探索の最良の時間複雑度は O(logn) のオーダーです。これは平均ケースの時間的複雑さと同じです。

  • 最悪の場合

最悪の場合、根元から最深部の葉のノードまで、つまり木の高さ h 全体を辿らなければならないかもしれません。木が不均衡である場合、すなわち、木が歪んでいる場合、木の高さは n になる可能性があり、そのため、挿入と探索の両方の操作の最悪の場合の時間的複雑さは O(n) となります。

空間計算量

挿入操作と検索操作の空間的複雑さは、再帰的な呼び出しのために必要な空間があるため、O(n) となります。

著者: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

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

関連記事 - Data Structure

関連記事 - Binary Tree

関連記事 - Binary Search Tree