二分木走査

1. 二分木走査
2. 二項木の探索イラスト
3. 二項木探索アルゴリズム
4. 二分木トラバースの実装
5. 二分木走査アルゴリズムの計算複雑性

二分木は非線形データ構造です。各ノードには最大 2つの子があるので、二分木と呼ばれています。これらの子は左の子と右の子と呼ばれています。また、最上位のノードをルートと呼ぶ無向グラフと解釈することもできます。一方向にしか移動できない線形データ構造とは異なり、木はさまざまな方法で移動することができます。深さや幅に沿って探索することで木を探索することができます。最初の方法は深さ優先走査と呼ばれ、2 番目の方法は幅優先走査と呼ばれます。この記事では、深さ優先探索について説明します。

デプスファースト走査には、インオーダー、プレオーダー、ポストオーダーの 3 種類があります。それぞれについて一つずつ解説していきます。

二分木走査

インオーダー走査

この探索では、まず左サブツリー、次にルート、そして最後に右サブツリーを訪れます。すべてのノードはサブツリーに似ています。BST では、順序を変えて探索すると、すべての要素が昇順で返されます。

プレオーダー走査

この探索では、まずルート、左サブツリー、そして最後に右サブツリーを訪れます。すべてのノードはサブツリーに似ています。これは通常、ツリーの複製、すなわちコピーを作成するために使用されます。プレフィックス探索は、式木からプレフィックス式を生成するのにも役立ちます。

ポストオーダー探索

この探索では、まず左のサブツリー、次に右のサブツリー、そして最後にルートを訪れます。すべてのノードはサブツリーに似ています。これは、木を効果的に削除するために使用されます。また、式木から後置式を生成するのにも役立ちます。

二項木の探索イラスト

中間順：(4, 2, 1, 5, 3, 6, 7, 8, 9)

ルートノード 3 で順序走査を呼び出します。再帰的に左をトラバースして、左端のノードであるノード 4 に到達し、それを出力に含めます。これはルートであり、左ノードがないため、右端のノード 2 にアクセスして、走査に含めます。このようにして、ツリー全体をトラバースして、上記の順序を出力として取得します。

先行順： (3, 1, 4, 2, 5, 7, 6, 9, 8)

ルートノード 3 でプレオーダー走査を呼び出して出力に含めます。次に、再帰的に左にトラバースして次のルートノード 1 に到達し、その後に 4 に到達します。4 には左の子がないので、右のノード 2 を訪れます。これでルートノード 4 の下のサブツリーをカバーしたので、ノード 1 にたどり着き、その右のノード 5 に向かって進んでいきます。このようにして、木全体をトラバースして上記の順序を出力します。

後行順： (2, 4, 5, 1, 6, 8, 9, 7, 3)

ルートノード 3 の後置探索を呼び出し、左に再帰的に移動してノード 4 に到達します。4 を探索に含める前に、その右ノード 2 を訪問しなければならません。1 の右ノード 5 は訪問されていないので、まず 5 を出力に含めてから 1 に戻ります。次にルートノード 3 にたどり着き、右のサブツリーを辿っていきます。このようにして、ツリー全体をトラバースして上記の順序を出力として取得します。

二項木探索アルゴリズム

中間順

先行順

後行順

二分木トラバースの実装

#include <iostream>
using namespace std;

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

void inorder(Node* root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
  }
}
void preorder(Node* root) {
  if (root != NULL) {
    cout << root->key << " ";
    preorder(root->left);
    preorder(root->right);
  }
}

void postorder(Node* root) {
  if (root != NULL) {
    postorder(root->left);
    postorder(root->right);
    cout << root->key << " ";
  }
}

int main() {
  Node* root = new Node(3);
  root->left = new Node(1);
  root->right = new Node(7);
  root->left->left = new Node(4);
  root->left->right = new Node(5);
  root->left->left->right = new Node(2);
  root->right->left = new Node(6);
  root->right->right = new Node(9);
  root->right->right->left = new Node(8);
  cout << "The inorder traversal of the tree is : ";
  inorder(root);
  cout << endl;
  cout << "The preorder traversal of the tree is : ";
  preorder(root);
  cout << endl;
  cout << "The postorder traversal of the tree is : ";
  postorder(root);
  cout << endl;
}

二分木走査アルゴリズムの計算複雑性

時間計算量

• 平均ケース

木には n 個のノードがあり、3 種類の探索では、それぞれのノードを訪問しなければならません。順番は違えど n 個のノードを反復処理するので、3 種類の探索の時間的複雑さは O(n) のオーダーです。平均的な時間の複雑さは O(n) です。

• 最良の場合

最良の時間複雑度は O(n) です。これはすべての 3 トラバースに対する平均ケースの時間複雑度と同じです。

• 最悪の場合

最悪の時間複雑度は O(n) です。これはすべての 3 巡回のワーストケース時間複雑度と同じです。

空間計算量

アルゴリズムの空間の複雑さは、再帰呼び出しに必要な余分な空間のために O(n) となります。