[자료구조] 트라이

1. 개념

문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조.

각 노드는 문자 혹은 문자열의 한 글자를 나타낸다. 또한, 각 노드는 자식을 가지고 있을 수 있는데, 이는 각 노드의 다음 문자를 나타낸다.

 

2. 특징

• 루트 노드는 항상 공백이다.
• N진 트리의 형식을 가진다. 문자 종류에 따라 N이 결정된다. 알파벳은 26개의 문자로 이루어져 있기 때문에 26진 트리 형태를 갖게 된다. 즉 부모 노드가 자식을 최대 26개까지 가질 수 있다는 것이다.
• 각 문자의 접두사를 공유하기 때문에 검색이 빠르다. 
• 트리 형태로 문자를 저장하기 때문에 삽입과 삭제 연산이 빠르다. 조건을 만족한다면 상수시간 안에도 가능하다.

 

3. 구현

// 트라이에서 사용하는 노드 정의
class tNode{
    tNode[] next = new tNode[26];
    boolean isEnd;
}

// 트라이 구조 만들기
        while(N > 0){
            String str = br.readLine();
            tNode now = root;
            for(int i = 0; i<str.length(); i++){
                char ch = str.charAt(i);
                if(now.next[ch-'a'] == null){ // 다음 위치가 null 이니 거기에 새로운 노드 생성해서 집어넣기
                    now.next[ch-'a'] = new tNode();
                }
                now = now.next[ch-'a']; // 생성해서 집어 넣었다면 그게 현재 위치가 되는 거고, 집어넣지 않았다면 뭔가 있던 곳이 현재 위치가 되는 것
                if(i == str.length()-1){ // 만약 문자열 맨 마지막이라면 끝이라고 표시하기기
                    now.isEnd = true;
                }
            }
            N--;
        }
        
  // 트라이 검색      
  int count = 0;
        while(M > 0){
            String str = br.readLine();
            tNode now = root;
            for(int i = 0; i<str.length(); i++){
                char c = str.charAt(i);
                if(now.next[c-'a'] == null){ // 다음 노드를 찾는데 내가 찾는게 없으면 그 문자열은 없다는 의미이니 종료
                    break;
                }
                now = now.next[c-'a'];
                if(i == str.length() -1 && now.isEnd){ // 현재 살피는 문자열의 마지막이면서 비교 대상도 마지막이면 같다는 것이니 답 증가
                    count++;
                }
            }
            M--;
        }

 

4. 관련 문제

백준 14425

GitHub - Lee-Min-Jung/coding_test_practice