二分探索木

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 を検索対象の要素とします。

BST 検索イラスト

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

二分探索木での挿入

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

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

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

BST 挿入イラスト

これが 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) となります。