[자료구조] 트라이(Trie)

Java에서는 다음과 같이 구현할 수 있다. 물론 인덱스 값을 주었기에, 완전히 동일한 형식으로 char[]를 사용해도 된다.

 

워낙 유명한 내용이라 다른 책이나 블로그와 큰 차별점은 없겠지만 조만간 설명 추가할 예정

 

class Node {
    Node[] ch;
    boolean end;

    Node() {
        ch = new Node[26];
        end = false;
    }

    void insert(String s, int idx) {
        if (idx == s.length()) {
            end = true;
            return;
        }
        int now = s.charAt(idx) - 'a';
        if (ch[now] == null) ch[now] = new Node();
        ch[now].insert(s, idx + 1);
    }

    boolean find(String s, int idx) {
        if (idx == s.length()) {
            if (end) return true;
            else return false;
        }
        int now = s.charAt(idx) - 'a';
        if (ch[now] == null) return false;
        return ch[now].find(s, idx+1);
    }
}

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

        trie.insert("pen", 0);
        trie.insert("apple", 0);
        trie.insert("pineapple", 0);

        if (trie.find("pen", 0)) System.out.println("found pen!");
        if (trie.find("apple", 0)) System.out.println("found apple!");
        if (trie.find("pineapple", 0)) System.out.println("found pineapple!");
        if (trie.find("pine", 0)) System.out.println("found pine!");
        if (trie.find("penpineappleapplepen", 0)) System.out.println("found penpineappleapplepen!");
    }
}