二分探索木チェック

  2. チュートリアル
  3. データ構造
  4. 二分探索木チェック
Harshit Jindal 2023年10月12日
Data Structure Binary Tree Binary Search Tree
  1. 二分探索木であるかどうかをチェックするアルゴリズム
  2. 二分探索木であることを確認するアルゴリズムの実装
  3. 複雑性分析
二分探索木チェック

バイナリーツリーは非線形データ構造体です。各ノードには最大 2つの子があるので、バイナリツリーと呼ばれています。これらの子は左の子と右の子と呼ばれています。バイナリツリーが BST になるためには、以下の特性を満たさなければなりません。

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

二分探索木であるかどうかをチェックするアルゴリズム

アルゴリズム 1

このアプローチでは、すべてのノードをサブツリーのルートとみなして、左サブツリーにルートより大きい要素が含まれているかどうか、右サブツリーにルートより小さい要素が含まれているかどうかを調べます。max と min の要素を見つけるには、getMin() と getMax() という 2つの別の関数を使わなければならません。

getMin()

  • temp を root として初期化する。
  • temp が left のとき、以下のようにする。
    • つまり、左に向かって移動して最小の要素を見つける。
  • temp->val をそのサブツリー内の最小値として返します。

getMax()

  • temp を root として初期化する。
  • temp が right を持っている間に、以下のようにします。
    • つまり、右に向かって移動して最大の要素を探す。
  • temp->val をそのサブツリー内の最大値として返します。

isBST(root) とする

  • root が NULL の場合は true を返します。
  • 左サブツリーの最大要素 maxm を見つけるには getMax(root->left) を呼び出します。
  • getMin(root->right) を呼び出して、右サブツリーの最小要素 minm を探します。
  • ルート要素が maxm より小さいか minm より大きい場合は false を返します。
  • isBST(root->left) と isBST(root->right) を呼び出して、すべてのノードを再帰的にチェックします。両方の再帰的呼び出しが真を返した場合、その木は BST であり、そうでなければ真を返し、そうでなければ偽を返します。

上記のアルゴリズムは木が BST であるかどうかを教えてくれますが、非常に遅いです。関数 getMin() と getMax() は最悪の場合の時間的複雑度が O(n) であり、これらは n ノードに対して呼び出されるので、合計時間的複雑度は O(n2) となります。

アルゴリズム 2

このアルゴリズムは前のアルゴリズムを改良したもので、繰り返し計算を行わないようにしています。以前のアプローチでは、ノードごとに getMin() と getMax() を呼び出していました。このアプローチでは、ノードを通過する際に許容される最小値と最大値を追跡することで、上記のアプローチを改良しています。

isBST(root)

  • 2つの変数 min を INT_MIN、max を INT_MAX として初期化します。
  • isBST(root,min,max) を呼び出す。

isBST(root, min, max)

  • root が NULL の場合は true を返します。
  • min > root->data の場合、BST プロパティが違反しているので false を返します。
  • max < root->data の場合、BST プロパティが違反しているので false を返します。
  • 左サブツリーを再帰的にチェックするには、isBST(root->left, min, root->data-1) (min と root->data - 1 を引数に渡すと、左サブツリーの BST の有効範囲が変わります) を、右サブツリーを再帰的にチェックするには、isBST(root->right, root->data+1, max) (root->data + 1 と max を引数に渡すと、右サブツリーの BST の有効範囲が変わります) を呼び出します。
  • 再帰的な呼び出しが両方とも true を返す場合は、木が BST であることを示し、true を返します。

このアルゴリズムの時間的複雑さは O(n) であり、以前の方法よりも大幅に改善されています。

アルゴリズム 3

このアルゴリズムでは、INT_MIN と INT_MAX を l と r の 2つのポインタに置き換えることで、上のアルゴリズムで使用していた INT_MIN と INT_MAX の使用を回避します。

isBST(root)

  • 2つのノード l と r を NULL として初期化します。
  • isBST(root, l, r) を呼び出す。(オーバーロードされた関数呼び出し)

isBST(root, l, r)

  • root が NULL の場合は true を返します。
  • l が NULL でなく l->data >= root->data の場合、BST プロパティが違反しているので false を返します。
  • r が NULL でなく r->data <= root->data の場合、BST プロパティが違反しているので false を返します。
  • 左サブツリーを再帰的にチェックするには、isBST(root->left, left, root) (第 3 引数に root を渡すとサブツリーの最小値の上限が変更されます)を、右サブツリーを再帰的にチェックするには、isBST(root->right, root, right) (第 2 引数に root を渡すとサブツリーの最大値の上限が変更されます)を呼び出します。
  • 再帰的な呼び出しが両方とも true を返す場合、ツリーは BST であり、true を返します。

アルゴリズム 4

二分探索木の順不同探索は、ソートされた順に要素を返します。このプロパティを使用して、バイナリツリーが BST であるかどうかをチェックすることができます。順不同探索のすべての要素が昇順でない場合、与えられた木は二分探索木ではありません。

isBST(root)

  • 変数 prev を INT_MIN として初期化します。prev は、現在のノードが prev よりも大きいかどうか、つまりソートされた順序に従っているかどうかを調べるために使われます。
  • isBST(root, prev) を呼び出す。(オーバーロードされた関数 Call)。

(オーバーロードされた関数 Call)

  • root が NULL の場合は true を返す。
  • isBST(root->left, prev) で左サブツリーを再帰的にチェックする。false を返した場合は false を返します。
  • root->data <= prev. の昇順に違反している場合は false を返します。
  • prev->data を root->data として更新します。
  • isBST(root->right, prev) で右サブツリーを再帰的に調べる。false を返した場合は false を返す。
  • そうでなければ true を返します。

二分探索木であることを確認するアルゴリズムの実装

アルゴリズム 1

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
int getMin(Node* root) {
  while (root->left) {
    root = root->left;
  }

  return root->data;
}
int getMax(Node* root) {
  while (root->right) {
    root = root->right;
  }

  return root->data;
}
bool isBST(Node* root) {
  if (root == NULL) return true;

  if (root->left != NULL && getMax(root->left) > root->data) return false;

  if (root->right != NULL && getMin(root->right) < root->data) return false;

  if (!isBST(root->left) || !isBST(root->right)) return false;

  return true;
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

アルゴリズム 2

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, int min, int max) {
  if (root == NULL) return 1;
  if (root->data < min || root->data > max) return 0;

  return isBST(root->left, min, root->data - 1) &&
         isBST(root->right, root->data + 1, max);
}

bool isBST(Node* root) { return isBST(root, INT_MIN, INT_MAX); }
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

アルゴリズム 3

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, Node* l, Node* r) {
  if (root == NULL) return true;

  if (l != NULL and root->data <= l->data) return false;
  if (r != NULL and root->data >= r->data) return false;

  return isBST(root->left, l, root) && isBST(root->right, root, r);
}
bool isBST(Node* root) {
  Node* l = NULL;
  Node* r = NULL;
  return isBST(root, l, r);
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

アルゴリズム 4

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, int& prev) {
  if (!root) return true;

  if (!isBST(root->left, prev)) return false;

  if (root->data <= prev) return false;
  prev = root->data;

  return isBST(root->right, prev);
}

bool isBST(Node* root) {
  int prev = INT_MIN;
  return isBST(root, prev);
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

複雑性分析

時間計算量

  • 平均ケース

与えられたバイナリツリーが BST であるかどうかを調べるには、すべての n ノードを探索しなければなりません。したがって、時間の複雑さは [Big Theta]: O(n) のオーダーになります。

  • 最良の場合

最良の時間複雑度は O(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