C++で三分木（Ternary Tree）を実装するプログラム

三分木（Ternary Tree）は、各ノードが最大3つの子ノードを持つことのできる木構造データ構造です。子ノードは通常、「左（left）」「中央（mid／equal）」「右（right）」の3つとして表現されます。この木では、子を持つノードが親ノードとなり、子ノード側から親への参照を保持することも可能です。本記事では、文字列を格納するための三分探索木（Ternary Search Tree）をC++で実装し、木全体を走査して登録済みの単語をすべて出力する方法を解説します。

三分探索木の仕組み

ここで扱うのは、文字列の集合を効率的に管理するための三分探索木です。二分探索木（BST）とトライ（Trie）の性質を併せ持っており、各ノードは1文字を格納し、次の3つの子ポインタを持ちます。

• 左の子（l）…現在のノードの文字より「小さい」文字への分岐
• 中央の子（eq）…文字が一致した場合に、次の文字へ進むためのリンク
• 右の子（r）…現在のノードの文字より「大きい」文字への分岐

さらに各ノードには「単語の終端かどうか」を示すフラグ（EndOfString）があり、このフラグが立っているノードまで辿った文字列が、登録済みの単語であることを表します。挿入や検索は単語長Lに対しておよそO(L)で動作し、通常のトライに比べて必要なノード数を大幅に削減できるのが大きな特徴です。

アルゴリズム

1. 挿入（insert）

Begin
    Declare function insert(struct nod** root, char *w)
        if (!(*root)) then
            *root = newnod(*w)
        if ((*w) < (*root)->d) then
            insert(&((*root)->l), w)
        else if ((*w) > (*root)->d) then
            insert(&((*root)->r), w)
        else if (*(w+1)) then
            insert(&((*root)->eq), w+1)
        else
            (*root)->EndOfString = 1
End.

挿入時は、現在の文字がノードの文字より小さければ左の子へ、大きければ右の子へ進みます。文字が一致した場合は、まだ残りの文字があれば中央の子へ進んで次の文字を挿入し、これ以上残りがなければそのノードを「単語の終端」としてマークします。

2. 走査（traverseTTtil）

Begin
    Declare function traverseTTtil(struct nod* root,
                                   char* buffer, int depth)
        if (root) then
            traverseTTtil(root->l, buffer, depth)
            buffer[depth] = root->d
            if (root->EndOfString) then
                buffer[depth+1] = '\0'
                print the value of buffer
            traverseTTtil(root->eq, buffer, depth + 1)
            traverseTTtil(root->r, buffer, depth)
End.

走査は再帰的に行われます。まず左部分木を訪れ、次に現在のノードの文字をバッファに書き込みます。終端フラグが立っていればバッファ末尾にヌル文字を加えて1つの単語として出力し、続いて中央部分木（次の文字）、最後に右部分木を訪れます。この順序で辿ることで、辞書順に近い形ですべての単語を取り出せます。

C++サンプルコード

#include <iostream>
#include <cstdlib>
using namespace std;

struct nod {
    char d;                    // ノードが保持する1文字
    unsigned EndOfString : 1;  // 単語の終端フラグ
    struct nod *l, *eq, *r;
} *t = NULL;

// 新しいノードを作成する関数
struct nod* newnod(char d) {
    t = new nod;
    t->d = d;
    t->EndOfString = 0;
    t->l = t->eq = t->r = NULL;
    return t;
}

// 単語 w を木に挿入する関数
void insert(struct nod** root, char *w) {
    if (!(*root))
        *root = newnod(*w);

    if ((*w) < (*root)->d)
        insert(&((*root)->l), w);
    else if ((*w) > (*root)->d)
        insert(&((*root)->r), w);
    else {
        if (*(w+1))
            insert(&((*root)->eq), w+1);
        else
            (*root)->EndOfString = 1;
    }
}

// 木を走査して単語を出力する補助関数
void traverseTTtil(struct nod* root, char* buffer, int depth) {
    if (root) {
        traverseTTtil(root->l, buffer, depth);
        buffer[depth] = root->d;
        if (root->EndOfString) {
            buffer[depth+1] = '\0';
            cout << buffer << endl;
        }
        traverseTTtil(root->eq, buffer, depth + 1);
        traverseTTtil(root->r, buffer, depth);
    }
}

// 走査用のラッパー関数
void traverseTT(struct nod* root) {
    char buffer[50];
    traverseTTtil(root, buffer, 0);
}

int main() {
    struct nod *root = NULL;

    insert(&root, "mat");
    insert(&root, "bat");
    insert(&root, "hat");
    insert(&root, "rat");

    cout << "Following is traversal of ternary tree\n";
    traverseTT(root);
    return 0;
}

実行結果

Following is traversal of ternary tree
bat
hat
mat
rat

まとめ

このプログラムでは、"mat"、"bat"、"hat"、"rat" の4つの単語を三分探索木に挿入し、木を走査することで辞書順にすべて出力しています。三分探索木はオートコンプリート機能やスペルチェッカーなど、大量の文字列を扱うアプリケーションで特に有効なデータ構造です。挿入・検索ともに単語長に比例した時間で動作するため、大規模な辞書データの管理にも適しています。