JavaでのTrieデータ構造の実装方法

まず、Trieノードを表すクラスを作成します。各ノードは文字、子ノードへの参照、および単語の終了を示すフラグを持つ必要があります。以下は、Trieノードのクラスの例です。

class TrieNode {
    char ch;
    Map<Character, TrieNode> children;
    boolean isWordEnd;
    public TrieNode(char ch) {
        this.ch = ch;
        this.children = new HashMap<>();
        this.isWordEnd = false;
    }
}

次に、Trieクラスを作成します。Trieクラスは、Trieの基本的な操作（挿入、検索、削除）を実装します。

class Trie {
    private TrieNode root;
    public Trie() {
        this.root = new TrieNode('\0');
    }
    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current.children.putIfAbsent(ch, new TrieNode(ch));
            current = current.children.get(ch);
        }
        current.isWordEnd = true;
    }
    public boolean search(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            if (!current.children.containsKey(ch)) {
                return false;
            }
            current = current.children.get(ch);
        }
        return current.isWordEnd;
    }
    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (char ch : prefix.toCharArray()) {
            if (!current.children.containsKey(ch)) {
                return false;
            }
            current = current.children.get(ch);
        }
        return true;
    }
}

上記の例では、Trieクラスに文字列の挿入（insert）、文字列の検索（search）、接頭辞の存在チェック（startsWith）のメソッドを実装しました。

以下は、Trieクラスの使用例です。

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();

        trie.insert("apple");
        trie.insert("banana");
        trie.insert("orange");

        System.out.println(trie.search("apple"));   // true
        System.out.println(trie.search("grape"));   // false

        System.out.println(trie.startsWith("app"));  // true
        System.out.println(trie.startsWith("ora"));  // false
    }
}

この例では、"apple"、"banana"、"orange"の3つの単語をTrieに挿入し、検索と接頭辞の存在チェックを行っています。

以上が、JavaでのTrieデータ構造の実装方法についてのシンプルな例です。このコードは基本的な操作をカバーしており、必要に応じて拡張することができます。