2分探索木とは？意味をわかりやすく簡単に解説

公開：2024年9月24日更新：2024年9月24日

2分探索木とは
2分探索木の実装と操作
2分探索木のノード構造設計
挿入操作の実装方法
探索アルゴリズムの効率化

2分探索木とは

2分探索木はデータを効率的に格納・検索するために活用する、ツリー構造を用いたデータ構造です。各ノードが最大2つの子ノードを持っており、左の子ノードは親ノードより小さい値で右の子ノードは大きい値を持つというのが特徴です。

この構造によりデータの挿入・検索・削除の操作が、平均的にO(log n)の時間複雑度で実行できます。2分探索木はソートされたデータを保持しながら、効率的なデータ管理を可能にする点で優れています。

2分探索木はデータベース索引やシンボルテーブルの実装など、さまざまなアプリケーションで広く使用されています。

Python基礎・実践(Django)

企業・法人向けのPython研修では、基礎から応用まで体系的に学べます。

Python研修の詳細

DX社員研修

企業・法人向けのDX研修では、実務に繋がるリスキリングでITレベルを向上させます。

DX研修の詳細

Javaエンジニア育成研修

企業・法人向けのJavaエンジニア育成研修では、Javaの基礎から応用まで確実に習得できます。

Java研修の詳細

新卒・新入社員向け研修

企業・法人に新入社員・新卒社員に向けたプログラミング研修を提供しています。

新入社員研修の詳細

コードキャンプのIT研修を全て見る

2分探索木の実装と操作

2分探索木の実装と操作に関して、以下3つを簡単に解説します。

2分探索木のノード構造設計
挿入操作の実装方法
探索アルゴリズムの効率化

2分探索木のノード構造設計

2分探索木のノード構造はデータ値と、左右の子ノードへのポインタを含むクラスまたは構造体として設計されます。この設計により各ノードが自身の値と子ノードへの参照を保持し、ツリー構造を形成することが可能です。

struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

上記のコードはC++で実装された、二分探索木のノード構造の基本的な例です。データ値（int型）と左右の子ノードへのポインタを持ち、コンストラクタでデータ値を初期化しています。

このノード構造を基に、2分探索木の全体を表現するクラスを作成します。ルートノードへのポインタを保持し、挿入・検索・削除などの操作をメンバ関数として実装するのが一般的なアプローチです。

おすすめのPython研修一覧

Python研修を提供しているおすすめの企業・法人を一覧で掲載しております。

Python研修の一覧を見る

おすすめのDX研修一覧

DX研修を提供しているおすすめの企業・法人を一覧で掲載しております。

DX研修の一覧を見る

おすすめのJava研修一覧

Java研修を提供しているおすすめの企業・法人を一覧で掲載しております。

Java研修の一覧を見る

おすすめのJavaScript研修一覧

JavaScript研修を提供しているおすすめの企業・法人を一覧で掲載しております。

JavaScript研修の一覧を見る

挿入操作の実装方法

2分探索木への要素の挿入はルートから開始し、適切な位置を再帰的に探索することで実装可能。新しい値が現在のノードより小さければ左に、大きければ右に進みます。空のポジションに到達したら新しいノードを作成します。

Node* insert(Node* root, int value) {
    if (root == nullptr) return new Node(value);

    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;
}

この挿入操作はツリーの高さに比例する、時間複雑度O(h)で実行されます。平均的なケースではツリーの高さはlog nに近いため、挿入操作の平均時間複雑度はO(log n)となります。

ただし、連続してソートされた値を挿入するとツリーが一方に偏り、最悪の場合O(n)の時間複雑度になることがあるので注意が必要です。この問題はAVL木や赤黒木などの自己平衡木で解決できます。

探索アルゴリズムの効率化

2分探索木での要素の探索は、ルートから始めて目的の値を見つけるまで左右の子ノードを再帰的に探索するのが特徴です。この操作もツリーの高さに依存し、平均的にはO(log n)の時間複雑度で実行できます。

Node* search(Node* root, int value) {
    if (root == nullptr || root->data == value) return root;

    if (value < root->data)
        return search(root->left, value);

    return search(root->right, value);
}

探索アルゴリズムの効率を上げるには、ツリーのバランスを保つことが重要です。AVL木や赤黒木などの自己平衡木を使用すると、常にO(log n)の時間複雑度を保証できます。

また、頻繁にアクセスされる要素を根に近い位置に移動させる「スプレイ木」という変種もあります。これによりアクセスパターンに応じて、探索効率を動的に改善できるのが魅力です。

※上記コンテンツの内容やソースコードはAIで確認・デバッグしておりますが、間違いやエラー、脆弱性などがある場合は、コメントよりご報告いただけますと幸いです。