【入門】データ構造の二分探索木（BST）とは？C++での実装例もわかりやすく解説

二分探索木とは

二分探索木（Binary Search Tree：BST）は、特定の性質を満たす二分木の一種です。この性質のおかげで、木の中から目的の値を効率的に検索できることが大きな特徴です。主な性質は以下のとおりです。

• すべての二分探索木は二分木である
• 左の子ノードには、親（ルート）より小さい値が格納される
• 右の子ノードには、親（ルート）より大きい値が格納される
• 理想的な二分探索木では、同じ値を重複して保持しない

例として、次のような木を考えてみましょう。

この木は上記の性質をすべて満たしているため、正しい二分探索木といえます。ここで注目すべき点として、この木を中順走査（インオーダー走査）で巡回すると、「5, 8, 10, 15, 16, 20, 23」という昇順に並べ替えられた結果が得られます。「左の子 → 親 → 右の子」の順に訪問すると要素が必ずソート済みの順序で取り出せるのは、二分探索木ならではの重要な特性です。

二分探索木への挿入の仕組み

新しい値を挿入するときは、ルートから順に値を比較していきます。挿入したい値が現在のノードより小さければ左側へ、大きければ右側へ進み、空きノードに行き着いた時点でそこに新しいノードを作成します。この規則を守ることで、常にBSTの性質が保たれます。

C++による実装例

それでは、実際にC++で二分探索木を実装したコードを見てみましょう。ノードの生成、挿入、中順走査を行うシンプルなプログラムです。

#include<iostream>
using namespace std;
class node{
    public:
        int h_left, h_right, bf, value;
        node *left, *right;
};
class tree{
    private:
        node *get_node(int key);
    public:
        node *root;
        tree(){
            root = NULL; //最初はルートをNULLに設定
        }
        void inorder_traversal(node *r);
        node *insert_node(node *root, int key);
};
node *tree::get_node(int key){
    node *new_node;
    new_node = new node; //新しいノードを動的に生成
    new_node->h_left = 0; new_node->h_right = 0;
    new_node->bf = 0;
    new_node->value = key; //渡されたキーの値を格納
    new_node->left = NULL; new_node->right = NULL;
    return new_node;
}
void tree::inorder_traversal(node *r){
    if(r != NULL){ //ルートが存在すれば、左→根→右の順で訪問
        inorder_traversal(r->left);
        cout << r->value << " ";
        inorder_traversal(r->right);
    }
}
node *tree::insert_node(node *root, int key){
    if(root == NULL){
        return (get_node(key)); //木が空なら新ノードをルートとして作成
    }
    if(key < root->value){ //キーがルートの値より小さい場合は左へ
        root->left = insert_node(root->left, key);
    }else if(key > root->value){ //キーがルートの値より大きい場合は右へ
        root->right = insert_node(root->right, key);
    }
    return root; //キーが既に存在する場合は再挿入しない
}
main(){
    node *root;
    tree my_tree;
    //木にいくつかのキーを挿入する
    my_tree.root = my_tree.insert_node(my_tree.root, 10);
    my_tree.root = my_tree.insert_node(my_tree.root, 5);
    my_tree.root = my_tree.insert_node(my_tree.root, 16);
    my_tree.root = my_tree.insert_node(my_tree.root, 20);
    my_tree.root = my_tree.insert_node(my_tree.root, 15);
    my_tree.root = my_tree.insert_node(my_tree.root, 8);
    my_tree.root = my_tree.insert_node(my_tree.root, 23);
    cout << "In-Order Traversal: ";
    my_tree.inorder_traversal(my_tree.root);
}

実行結果

In-Order Traversal: 5 8 10 15 16 20 23

まとめ

二分探索木は「左の子 ＜ 親 ＜ 右の子」という規則に従ってデータを配置することで、検索・挿入・削除を平均的にO(log n)の時間計算量で実現できる強力なデータ構造です。ただし、挿入する値の順序によっては木が左右どちらかに偏り、最悪ケースでは性能がO(n)まで落ちる点には注意が必要です。そのような場合には、AVL木や赤黒木といった平衡二分探索木を採用すると効果的です。