トライ木（プレフィックスツリー）

Q: トライ木の時間計算量はどれくらいですか？

挿入・検索・プレフィックス検索はすべて `O(m)` で実行されます。`m` は単語またはプレフィックスの長さで、格納されている単語数には依存しません。トレードオフはメモリです：共有プレフィックスは一度だけ格納されますが、トライ木は多くの空間を使うことがあります。

Q: トライ木とハッシュテーブルの違いは何ですか？

ハッシュテーブルは完全なキーを平均 `O(1)` で検索できますが、プレフィックス検索には答えられません。トライ木は1回の検索がわずかに遅いものの、プレフィックス検索、順序付き走査、オートコンプリートを自然にサポートします — それがこれらの用途で好まれる理由です。

Q: 二分探索木ではなくトライ木を使うべきなのはどんなときですか？

キーが文字列でプレフィックス検索が必要なときはトライ木を使いましょう：キーの長さに対して1操作あたり `O(m)` で動作しますが、平衡二分探索木は各比較で文字列を走査し、その比較が `log n` 回あるため `O(m log n)` かかります。キーが文字列的でない場合や、メモリのオーバーヘッドがプレフィックス速度より重要な場合は、二分探索木の方が良い選択です。

最終更新 2026年7月1日

トライ木（「トライ」と発音）、またはプレフィックスツリーは、文字列の集合をその文字ごとに格納します。各辺には1文字がラベル付けされ、ルートからのパスがプレフィックスを綴ります。プレフィックスを共有する単語は同じノードを共有するため、「car」「card」「care」はすべて c-a-r のパスを再利用します。上の再生ボタンを押すと、単語が1文字ずつ挿入され、異なる箇所でのみ分岐する様子が見られます。

検索は1文字あたり1ノードをたどるため、長さ m の単語の検索は、トライ木が保持する単語数に関わらず O(m) で済みます。これにより、トライ木はオートコンプリート、スペルチェック、プレフィックス検索に最適です。

時間計算量と空間計算量

操作	計算量	備考
挿入	O(m)	m = 単語の長さ
検索	O(m)	1文字あたり1ステップ
プレフィックス検索	O(m)	プレフィックスのノードまでたどる
空間	O(total chars)	共有プレフィックスは一度だけ格納される

ステップ・バイ・ステップ（挿入）

ステップ	何が起こるか
1	ルートノードから始める。
2	単語の各文字について、一致する子の辺を探す。
3	存在すればそれをたどる（共有プレフィックスを再利用する）。
4	なければ、その文字用の新しい子ノードを作成する。
5	最後の文字の後、そのノードを単語の終端として印を付ける。

具体例で追う

空のトライ木に ["car", "card", "care"] を挿入する場合：

ステップ	構造	アクション
`car` を挿入	`root → c → a → r✓`	一致する子が存在しないので、`c`、`a`、`r` を作成し、`r` を単語の終端として印を付ける。
`card` を挿入	`root → c → a → r✓ → d✓`	既存の `c-a-r` パスを再利用し、新しい子 `d` を1つ作成して単語の終端として印を付ける。
`care` を挿入	`root → c → a → r✓ → {d✓, e✓}`	`c-a-r` を再利用し、`r` から新しい子 `e` で分岐して、`e` を単語の終端として印を付ける。
`care` を検索	`root → c → a → r → e✓`	`c`、`a`、`r`、`e` をたどる。最後のノードが単語の終端として印付けされているので、`care` は存在する。
`ca` を検索	`root → c → a`	パスは存在するが `a` は単語の終端として印付けされていないので、`ca` はプレフィックスであって格納された単語ではない。

トライ木を使うべきとき

使うべき場合	避けるべき場合
文字列の集合に対してプレフィックス検索やオートコンプリートが必要な場合。	完全なキーの検索だけが必要な場合 — ハッシュテーブルの方が速く軽量。
格納する多くの単語が共通のプレフィックスを共有し、ノードが再利用される場合。	キーが長くめったに重ならず、1文字ごとにノードを無駄にする場合。
走査によってキーをソート順で返したい場合。	メモリが逼迫している場合 — ノードごとの子ポインタが大きなオーバーヘッドを加える。
検索コストがデータセットのサイズではなくキーの長さに依存すべき場合。	アルファベットが巨大（例：Unicode全体）で子を密に格納する場合。

Trie (Prefix Tree)のコード

Python, JavaScript, Java, C++, Cによるクリーンで実行可能なTrie (Prefix Tree)の実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。

PythonでのTrie (Prefix Tree)のコードPython
1class TrieNode:2    def __init__(self):3        self.children = {}4        self.is_word = False5
6
7class Trie:8    def __init__(self):9        self.root = TrieNode()10
11    def insert(self, word):12        node = self.root13        for ch in word:14            node = node.children.setdefault(ch, TrieNode())15        node.is_word = True16
17    def search(self, word):18        node = self._walk(word)19        return node is not None and node.is_word20
21    def starts_with(self, prefix):22        return self._walk(prefix) is not None23
24    def _walk(self, s):25        node = self.root26        for ch in s:27            if ch not in node.children:28                return None29            node = node.children[ch]30        return node31
32
33trie = Trie()34for word in ["car", "card", "care", "dog"]:35    trie.insert(word)36
37print("search(card):     ", trie.search("card"))38print("search(ca):       ", trie.search("ca"))39print("starts_with(ca):  ", trie.starts_with("ca"))40print("starts_with(do):  ", trie.starts_with("do"))41print("starts_with(cat): ", trie.starts_with("cat"))
このコードをPythonプレイグラウンドで実行

JavaScriptでのTrie (Prefix Tree)のコードJavaScript
1class TrieNode {2    constructor() {3        this.children = {};4        this.isEnd = false;5    }6}7
8class Trie {9    constructor() {10        this.root = new TrieNode();11    }12
13    insert(word) {14        let node = this.root;15        for (const ch of word) {16            if (!node.children[ch]) node.children[ch] = new TrieNode();17            node = node.children[ch];18        }19        node.isEnd = true;20    }21
22    // Walk the prefix; null when a character is missing23    findNode(prefix) {24        let node = this.root;25        for (const ch of prefix) {26            node = node.children[ch];27            if (!node) return null;28        }29        return node;30    }31
32    search(word) {33        const node = this.findNode(word);34        return node !== null && node.isEnd;35    }36
37    startsWith(prefix) {38        return this.findNode(prefix) !== null;39    }40}41
42const trie = new Trie();43for (const word of ["car", "card", "care", "dog"]) trie.insert(word);44console.log("search(\"card\"):", trie.search("card"));45console.log("search(\"ca\"):", trie.search("ca"));46console.log("startsWith(\"ca\"):", trie.startsWith("ca"));
このコードをJavaScriptプレイグラウンドで実行

JavaでのTrie (Prefix Tree)のコードJava
1public class Main {2    static class Node {3        Node[] children = new Node[26];4        boolean isWord;5    }6
7    static Node root = new Node();8
9    static void insert(String word) {10        Node cur = root;11        for (char c : word.toCharArray()) {12            int i = c - 'a';13            if (cur.children[i] == null) cur.children[i] = new Node();14            cur = cur.children[i];15        }16        cur.isWord = true;17    }18
19    // Follow the path for s; null means no word has this prefix20    static Node walk(String s) {21        Node cur = root;22        for (char c : s.toCharArray()) {23            cur = cur.children[c - 'a'];24            if (cur == null) return null;25        }26        return cur;27    }28
29    static boolean search(String word) {30        Node node = walk(word);31        return node != null && node.isWord;32    }33
34    static boolean startsWith(String prefix) {35        return walk(prefix) != null;36    }37
38    public static void main(String[] args) {39        insert("code");40        insert("coder");41        insert("cool");42        System.out.println("search code: " + search("code"));43        System.out.println("search cod: " + search("cod"));44        System.out.println("startsWith cod: " + startsWith("cod"));45        System.out.println("startsWith cat: " + startsWith("cat"));46    }47}
このコードをJavaプレイグラウンドで実行

C++でのTrie (Prefix Tree)のコードC++
1#include <iostream>2#include <string>3#include <unordered_map>4
5struct TrieNode {6    std::unordered_map<char, TrieNode*> children;7    bool isEnd = false;8};9
10struct Trie {11    TrieNode* root = new TrieNode();12
13    void insert(const std::string& word) {14        TrieNode* node = root;15        for (char c : word) {16            if (!node->children.count(c)) node->children[c] = new TrieNode();17            node = node->children[c];18        }19        node->isEnd = true;20    }21
22    // Follow the path for s; nullptr if a link is missing23    TrieNode* walk(const std::string& s) const {24        TrieNode* node = root;25        for (char c : s) {26            auto it = node->children.find(c);27            if (it == node->children.end()) return nullptr;28            node = it->second;29        }30        return node;31    }32
33    bool search(const std::string& word) const {34        TrieNode* node = walk(word);35        return node != nullptr && node->isEnd;36    }37
38    bool startsWith(const std::string& prefix) const {39        return walk(prefix) != nullptr;40    }41};42
43int main() {44    Trie trie;45    for (const std::string& word : {"car", "card", "care", "dog"}) {46        trie.insert(word);47    }48    std::cout << std::boolalpha;49    std::cout << "search(card): " << trie.search("card") << "\n";50    std::cout << "search(ca): " << trie.search("ca") << "\n";51    std::cout << "startsWith(ca): " << trie.startsWith("ca") << "\n";52    std::cout << "startsWith(dot): " << trie.startsWith("dot") << "\n";53    return 0;54}
このコードをC++プレイグラウンドで実行

CでのTrie (Prefix Tree)のコードC
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct TrieNode {6    struct TrieNode* children[26];7    bool isEnd;8} TrieNode;9
10TrieNode* newNode(void) {11    return calloc(1, sizeof(TrieNode));  // zeroed links and isEnd12}13
14void insert(TrieNode* root, const char* word) {15    for (; *word; word++) {16        int i = *word - 'a';17        if (root->children[i] == NULL) root->children[i] = newNode();18        root = root->children[i];19    }20    root->isEnd = true;21}22
23// Follow the path for s; NULL if a link is missing24TrieNode* walk(TrieNode* root, const char* s) {25    for (; *s; s++) {26        root = root->children[*s - 'a'];27        if (root == NULL) return NULL;28    }29    return root;30}31
32bool search(TrieNode* root, const char* word) {33    TrieNode* node = walk(root, word);34    return node != NULL && node->isEnd;35}36
37bool startsWith(TrieNode* root, const char* prefix) {38    return walk(root, prefix) != NULL;39}40
41int main(void) {42    TrieNode* root = newNode();43    const char* words[] = {"car", "card", "care", "dog"};44    for (int i = 0; i < 4; i++) insert(root, words[i]);45    printf("search(card): %s\n", search(root, "card") ? "true" : "false");46    printf("search(ca): %s\n", search(root, "ca") ? "true" : "false");47    printf("startsWith(ca): %s\n", startsWith(root, "ca") ? "true" : "false");48    printf("startsWith(dot): %s\n", startsWith(root, "dot") ? "true" : "false");49    return 0;50}
このコードをCプレイグラウンドで実行

トライ木のよくある質問

トライ木は何に使われますか？

トライ木はプレフィックスベースの機能を支えます：オートコンプリートと検索サジェスト、スペルチェッカー、IPルーティングテーブル、辞書検索などです。「格納されたいずれかの単語がこのプレフィックスで始まるか？」という問い合わせに素早く答える必要がある場面で、トライ木は真価を発揮します。

トライ木の時間計算量はどれくらいですか？

挿入・検索・プレフィックス検索はすべて O(m) で実行されます。m は単語またはプレフィックスの長さで、格納されている単語数には依存しません。トレードオフはメモリです：共有プレフィックスは一度だけ格納されますが、トライ木は多くの空間を使うことがあります。

トライ木とハッシュテーブルの違いは何ですか？

ハッシュテーブルは完全なキーを平均 O(1) で検索できますが、プレフィックス検索には答えられません。トライ木は1回の検索がわずかに遅いものの、プレフィックス検索、順序付き走査、オートコンプリートを自然にサポートします — それがこれらの用途で好まれる理由です。

二分探索木ではなくトライ木を使うべきなのはどんなときですか？

キーが文字列でプレフィックス検索が必要なときはトライ木を使いましょう：キーの長さに対して1操作あたり O(m) で動作しますが、平衡二分探索木は各比較で文字列を走査し、その比較が log n 回あるため O(m log n) かかります。キーが文字列的でない場合や、メモリのオーバーヘッドがプレフィックス速度より重要な場合は、二分探索木の方が良い選択です。

トライ木では単語の終端をどう扱いますか？

各ノードは単語終端フラグを持ち、挿入された完全な単語がそこで終わるときにのみ立てられます。これがないと、格納された単語と単なるプレフィックスを区別できません — 例えば card を挿入した後、car のノードは存在しますが、car も挿入された場合にのみ単語として報告されるべきです。

トライ木はプレフィックスを共有することで常にメモリを節約しますか？

常にではありません。共有が役立つのは多くのキーが重なる場合だけです。長く互いに異なるキーでは、各文字が子ポインタを持つ独自のノードになるため、トライ木はハッシュ集合よりはるかに多くのメモリを使うことがあります。空間が問題なら、圧縮された基数木（radix tree）が単一子のチェーンを統合してそのオーバーヘッドを削減します。