【C言語】第8章第14回：トライ（Trie）構造の基礎

2025年1月17日 a-mun

トライ（Trie）は文字列の効率的な格納と検索を可能にするデータ構造です。本記事では、トライの基礎から実装、応用例までを学びます。

Table of Contents

0. 記事の概要

この記事を読むメリット

効率的な文字列検索：トライを使用することで、文字列検索が高速化します。
アルゴリズム設計力の向上：文字列操作に適したデータ構造の理解が深まります。
実践的なスキル：C言語でのトライの実装方法を学べます。

この記事で学べること

トライの基本構造と操作
トライの実装と応用例
実際のコードによる動作の解説

1. トライの基本

1.1 トライとは？

トライ（Trie）はツリー構造の一種で、文字列の集合を効率的に格納および検索するために使用されます。

応用例：自動補完、スペルチェック、文字列検索
特徴：各ノードが文字を表し、文字列はルートからリーフまでのパスで表現されます。

1.2 トライの操作

挿入：文字列をトライに格納します。
検索：トライ内に文字列が存在するか確認します。
削除：指定した文字列をトライから削除します。

2. トライの実装

2.1 基本構造の定義

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALPHABET_SIZE 26

// トライノードの定義
typedef struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    int isEndOfWord; // 単語の終端を示す
} TrieNode;

// 新しいトライノードを作成
TrieNode* createNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = 0;

    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}

2.2 文字列の挿入

// トライに文字列を挿入
void insert(TrieNode* root, const char* key) {
    TrieNode* current = root;

    for (int i = 0; key[i] != '\0'; i++) {
        int index = key[i] - 'a';
        if (current->children[index] == NULL) {
            current->children[index] = createNode();
        }
        current = current->children[index];
    }
    current->isEndOfWord = 1;
}

2.3 文字列の検索

// トライで文字列を検索
int search(TrieNode* root, const char* key) {
    TrieNode* current = root;

    for (int i = 0; key[i] != '\0'; i++) {
        int index = key[i] - 'a';
        if (current->children[index] == NULL) {
            return 0; // 見つからない
        }
        current = current->children[index];
    }
    return current != NULL && current->isEndOfWord;
}

2.4 トライの表示

// トライの内容を表示（デバッグ用）
void display(TrieNode* root, char* str, int level) {
    if (root->isEndOfWord) {
        str[level] = '\0';
        printf("%s\n", str);
    }

    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (root->children[i] != NULL) {
            str[level] = i + 'a';
            display(root->children[i], str, level + 1);
        }
    }
}

int main() {
    TrieNode* root = createNode();

    insert(root, "hello");
    insert(root, "world");
    insert(root, "trie");

    char buffer[100];
    printf("Words in Trie:\n");
    display(root, buffer, 0);

    printf("\nSearch results:\n");
    printf("Search 'hello': %d\n", search(root, "hello"));
    printf("Search 'trie': %d\n", search(root, "trie"));
    printf("Search 'algorithm': %d\n", search(root, "algorithm"));

    return 0;
}

動作解説

ノードの初期化：各ノードがアルファベットサイズの配列を持つ。
挿入操作：文字列を1文字ずつトライに挿入。
検索操作：文字列がトライに存在するかを確認。
表示操作：トライ内のすべての文字列を再帰的に表示。

3. 練習問題

以下の課題に挑戦して、トライの理解を深めましょう。

トライにおける文字列削除機能を実装してください。
文字列のプレフィックス検索機能を追加してください。
トライ内のすべての単語をアルファベット順に出力するプログラムを作成してください。

4. 練習問題の解答と解説

問2の解答

// プレフィックス検索
int startsWith(TrieNode* root, const char* prefix) {
    TrieNode* current = root;

    for (int i = 0; prefix[i] != '\0'; i++) {
        int index = prefix[i] - 'a';
        if (current->children[index] == NULL) {
            return 0; // 見つからない
        }
        current = current->children[index];
    }
    return 1; // プレフィックスが存在
}

この関数では、指定したプレフィックスがトライ内に存在するかを確認します。

5. まとめ

本記事では、トライ（Trie）の基本構造と操作について学びました。次回は、さらに高度なトライの応用について掘り下げます。