C++でTrie（トライ木）を実装する方法｜挿入・検索・削除のコード例付き

本記事では、C++を使ってTrie（トライ木）を実装する方法を詳しく解説します。Trieは木構造ベースのデータ構造で、大量の文字列データセットの中から特定のキーを効率的に検索・取得するために利用されます。

Trieとはどのようなデータ構造か

Trieは「プレフィックス木（接頭辞木）」とも呼ばれ、文字列を1文字ずつ枝分かれさせながら格納する木構造です。根からあるノードまでの経路が、1つの文字列の接頭辞に対応します。本記事の実装では英大文字（A〜Z）のみを扱うため、各ノードは最大26個の子ポインタを持ちます。辞書検索やオートコンプリート機能など、文字列を高速に処理したい場面で広く活用されています。

主要な関数と擬似コード

insert()：キーの挿入

開始
関数 insert()：
　　キーがまだ存在しない場合、トライにキーを挿入する。
　　キーが既存ノードの接頭辞である場合は、葉ノードとしてマークするだけにする。
終了

deleteNode()：キーの削除

開始
関数 deleteNode()：
　　木が空であれば null を返す。
　　キーの最後の文字を処理している場合、
　　　　削除後、そのノードはもはや文字列の終端ではなくなる。
　　　　指定したキーが他の文字列の接頭辞でなければ、ノードを削除して root = NULL とする。
　　キーが最後の文字でない場合、
　　　　ASCII値をもとに求めた子ノードに対して再帰的に処理を行う。
　　ルートに子が残っておらず、かつ別の単語の終端でもない場合、
　　　　ノードを削除して root = NULL とする。
終了

C++による実装例

#include <bits/stdc++.h>
using namespace std;
const int ALPHA_SIZE = 26;

struct Trie {
    struct Trie *child[ALPHA_SIZE];
    bool endofstring; // ノードが単語の終端を表す場合にtrue
};
struct Trie *createNode(void) { // 新規ノードの作成
    struct Trie *tNode = new Trie;
    tNode->endofstring = false;
    for (int i = 0; i < ALPHA_SIZE; i++)
        tNode->child[i] = NULL;
    return tNode;
}
void insert(struct Trie *root, string key) {
    struct Trie *curr = root;
    for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'A';
        if (!curr->child[index])
            curr->child[index] = createNode();
        curr = curr->child[index];
    }
    curr->endofstring = true; // 最後のノードを葉としてマーク
}
bool search(struct Trie *root, string key) { // キーがトライ内に存在するか確認し、存在すればtrueを返す
    struct Trie *curr = root;
    for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'A';
        if (!curr->child[index])
            return false;
        curr = curr->child[index];
    }
    return (curr != NULL && curr->endofstring);
}
bool isEmpty(Trie* root) { // ルートに子ノードが存在するかどうかを確認
    for (int i = 0; i < ALPHA_SIZE; i++)
        if (root->child[i])
            return false;
    return true;
}
Trie* deletion(Trie* root, string key, int depth = 0) {
    // 木が空の場合はnullを返す
    if (!root)
        return NULL;
    if (depth == key.size()) { // キーの最後の文字を処理している場合、
        if (root->endofstring)
            root->endofstring = false; // 削除後、このノードは文字列の終端ではなくなる
        if (isEmpty(root)) { // 指定したキーが他の文字列の接頭辞でない場合、
            delete (root);
            root = NULL;
        }
        return root;
    }
    // キーが最後の文字でない場合、
    int index = key[depth] - 'A';
    root->child[index] =
    deletion(root->child[index], key, depth + 1); // ASCII値をもとに求めた子ノードに対して再帰的に処理
    if (isEmpty(root) && root->endofstring == false) { // 子が残っておらず、別の単語の終端でもない場合
        delete (root);
        root = NULL;
    }
    return root;
}
int main() {
    string inputs[] = {"HELLOWORLD","HI","BYE", "THE","THENA"}; // 入力キー（大文字のA〜Zのみ）
    int n = sizeof(inputs)/sizeof(inputs[0]);
    struct Trie *root = createNode();
    for (int i = 0; i < n; i++)
        insert(root, inputs[i]);
    search(root, "HELLOWORLD")? cout << "Key is Found\n" :
    cout << "Key is not Found\n";
    search(root, "HE")? cout << "Key is Found\n" :
    cout << "Key is not Found\n";
    deletion(root, "THEN")? cout << "Key is deleted\n" :
    cout << "Key is not Deleted\n";
    return 0;
}

実行結果

Key is Found
Key is not Found
Key is deleted

出力の解説

• "HELLOWORLD"：挿入済みの完全なキーなので「Found」と表示されます。
• "HE"：トライ上には存在しますが、これは他のキーの接頭辞にすぎず、endofstringフラグが立っていないため「not Found」になります。Trieの検索は完全一致で行われる点がポイントです。
• "THEN"：挿入済みのキーなので正常に削除され、「deleted」と表示されます。

まとめ

Trieを使うと、キーの長さをLとしたとき、挿入・検索・削除のいずれもO(L)の時間計算量で実行できます。ハッシュテーブルと比較すると、共通の接頭辞を持つキーを効率よく管理でき、辞書順の走査や前方一致検索にも適しています。大量の文字列を扱うアプリケーションでは、ぜひTrieの導入を検討してみてください。