📗[CS/DataStructure] 트라이

트라이 정의

• 문자열을 저장하고 검색하는 효과적인 트리 구조의 자료구조
• 각 노드가 문자를 가지며, 루트 노드부터 자식 노드를 따라가며 문자열을 구성
• 루트 노드
  • 루트 노드는 비어 있다
  • 루트 노드의 자식 노드는 각 단어들의 첫 글자를 나타낸다.
• 사용하는 이유?
  • 좀 더 빠르게 문자열을 탐색할 수 있다
• 그러나 각 노드마다 문자, 자식 노드 객체를 저장한다는 점에서 메모리가 많이 필요하다는 단점이 존재

 

구현

• 노드 클래스와 트리 클래스 2개를 갖는다.
• 노드 클래스
  • 각 노드는 child라는 자식 노드의 맵을 가짐
    • Map<문자, Node 객체>
  • 단어의 끝인지를 표시 하는 boolean 타입 변수 필요

• 트리 클래스
  • 트라이의 자료구조를 구현한 클래스
  • insert 메서드 : 단어를 트라이에 삽입
  • search 메서드 : 단어가 트라이에 존재하는지 확인

static class Node{
    // child맵은 자식 노드 정보를 담는 다.
    // 문자를 key, 자식노드 객체 Node를 value로 갖는다.
    Map<Character, Node> child = new TreeMap<>();

    // 문자의 끝인지 나타내는 변수
    boolean isEndOfWord = false;
}

static class Trie{
    Node root;

    Trie() {
        this.root = new Node();
    }

    // 삽입 함수 : 문자열 삽입하기
    public void insert(String word) {

        // 시작 노드는 루트 노드
        Node curNode = this.root;

        char c;
        for (int i = 0; i < word.length(); i++) {
            c = word.charAt(i);

            // 문자열의 단어가 자식 노드 중에 있는가?
            // 없다면, 해당 문자 노드를 생성
            curNode.child.putIfAbsent(c, new Node());

            // 자식 노드로 이동
            curNode = curNode.child.get(c);
        }

        // for문을 돌고 났을 때 가리키는 curNode는 문자열의 끝문자인지? -> isEndOfWord true로
        curNode.isEndOfWord = true;
    }

    // 탐색 함수 : 원하는 문자열이 존재하는가?
    public boolean search(String word) {

        // 시작 노드는 루트 노드
        Node curNode = this.root;

        char c;
        for (int i = 0; i < word.length(); i++) {
            c = word.charAt(i);

            if (curNode.child.containsKey(c)) {
                // c문자가 현재노드의 자식노드에 있다면 -> 이동
                curNode = curNode.child.get(c);
            } else {
                // 없다면 -> 탐색 종료
                return false;
            }
        }

        return curNode.isEndOfWord;
    }
}

 

시간 복잡도

• 제일 긴 문자열 길이 M, 총 문자열 개수 N
  • 생성 : O( M * N )
  • 탐색 : O(M) → 가장 긴 문자열의 길이만큼 탐색한다