---

트라이(Trie)

---

1. 트라이

• 문자열에서 검색을 빠르게 도와주는 자료구조

• 정수형에서 이진탐색트리를 사용하면 시간복잡도는 O(logN)

• M 길이의 문자열을 이진탐색트리에 적용하면 시간복잡도는 O(M*logN)

• 트라이를 활용하면 O(M)으로 문자열 검색이 가능하다.

2. 구현 코드

static class Trie {
    boolean end;
    boolean pass;
    Trie[] child;

    Trie() {
        end = false;
        pass = false;
        child = new Trie[10];
    }

    public boolean insert(String str, int idx) {

        //끝나는 단어 있으면 false 종료
        if(end) return false;

        //idx가 str만큼 왔을때
        if(idx == str.length()) {
            end = true;
            if(pass) return false; // 더 지나가는 단어 있으면 false 종료
            else return true;
        }
        //아직 안왔을 때
        else {
            int next = str.charAt(idx) - '0';
            if(child[next] == null) {
                child[next] = new Trie();
                pass = true;
            }
            return child[next].insert(str, idx+1);
        }

    }
}