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

트라이(Trie)

트라이 구조 예시

• 문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조이다.
• Prefix Tree, Retrieval Tree, Digital Search Tree 라고도 부른다.
• 정렬된 트리구조다.
• 문자열같은 것들을 트라이에 구축을 해둬야하기 때문에 문자열 저장을 위한 메모리가 (많이)필요하지만 탐색이 빠르다.
• 길이가 N개인 문자열 탐색의 시간복잡도는 O(N)이다.
• 대신 사전에 이런 문자열들을 이 트라이 형태로 구축을 해야하는데 구축할 때 드는 생성시 시간복잡도는 트라이에 넣으려는 문자열의 개수가 M개라고 할 때 O(MN)이다. 하지만 한번 구축하면 탐색할 때 굉장히 빠르다는 장점이 있다.
• 동일 위치에서의 공통 부분들은 중복해서 들어가지는 않지만 다른 부분에 대해서는 트라이를 적용시켜줘야 하기 때문에 그래서 여기서 메모리가 필요하다는 것이다. 파란색은 단어의 끝, flag 표시를 그림에 표현한 것이다.
• 이진트리가 아니다.
• 문자열 검색에 특화되어 보통 검색어 자동완성, 사전 찾기, 알고리즘 문제에선 주로 문자열의 '접두어', '~로 시작하는', '접미어', '~로 끝나는' 등의 키워드가 나오는 접두어, 접미어 판별 문제에서 사용된다.

트라이 삽입

트라이 삽입 예시

1. 처음에 들어오는 단어는 아무것도 없기 때문에 그냥 들어간다.(Apple) 해당 단어의 끝 문자임을 표시해줘야 한다.
2. 이후에 들어오는 단어들은 트리에 동일위치에 동일 문자가 있는지를 확인하고 있으면 따라가고 없으면 새로 만든다.
3.  들어오는 단어가 트리 내부에 포함될 경우, 노드를 새로 만들지 않고, 해당 단어의 끝 문자에 표시만 해주면 된다.

트라이 삭제

트라이 삭제 예시

• 삭제 단어가 어떤 단어에 포함되는 경우(삭제 단어 끝 문자 아래에 자식 노드가 존재할 경우) 끝 문자임을 표시했던 flag만 지워주면 된다.
• 포함되지 않는 경우(아래 자식 노드가 없을 경우), 또 다른 flag를 만날 때까지 노드를 지워주면 된다.

트라이 구현(java)

노드 클래스를 만든다. Key, Value 쌍으로 구성된 child 노드와 단어 끝인지 체크할 flag용으로 isTerminal을 만든다.

Key는 알파벳(문자), Value는 다음에 어떤 문자들이 오는지에 대한 정보를 담고있는 자식노드이다.

class Node {
    HashMap<Character, Node> child;
    // 단어 끝인지 체크 용 flag
    boolean isTerminal;

    public Node() {
        this.child = new HashMap<>();
        this.isTerminal = false;
    }
}

class Trie {
    Node root;

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

    public void insert(String str) {
        Node cur = this.root;

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            
            // 현재 노드 기준 c 문자에 해당하는 노드가 없으면 추가
            cur.child.putIfAbsent(c, new Node());
            // 이어서 추가하기 위해 다음 문자 쪽으로 이동
            cur = cur.child.get(c);

            // str 끝이면 flag true 체크 후 return
            if (i == str.length() - 1) {
                cur.isTerminal = true;
                return;
            }
        }
    }

    public boolean search(String str) {
        Node cur = this.root;

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            
            // 해당 단어 있으면 이동, 없으면 false 반환
            if (cur.child.containsKey(c)) {
                cur = cur.child.get(c);
            } else {
                return false;
            }

            // i 가 str 끝에 도달했지만 cur 의 terminal 이 true 아니면
            // 해당 단어가 들어 있는 것은 아니므로 false 반환
            if (i == str.length() - 1) {
                if (!cur.isTerminal) {
                    return false;
                }
            }
        }
        return true;
    }

    public void delete(String str) {
        boolean ret = this.delete(this.root, str, 0);
        if (ret) {
            System.out.println(str + " 삭제 완료");
        } else {
            System.out.println(str + " 단어가 없습니다.");
        }
    }

    public boolean delete(Node node, String str, int idx) {
        char c = str.charAt(idx);

        // 없는 단어인 경우 false 반환
        if (!node.child.containsKey(c)) {
            return false;
        }

        Node cur = node.child.get(c);
        idx++;
        
        // 단어의 가장 끝에 도달 후 삭제 결정
        if (idx == str.length()) {
            // 끝에 도달했지만 terminal true 아닌 경우
            // 해당 단어와 일치하는 것은 아니므로 false 반환
            if (!cur.isTerminal) {
                return false;
            }
            
            // 해당 단어와 일치할 경우 isTerminal false 로 변경
            cur.isTerminal = false;
            // 그 외의 문자 없는 경우 삭제
            if (cur.child.isEmpty()) {
                node.child.remove(c);
            }
        } else {
            if (!this.delete(cur, str, idx)) {
                return false;
            }
            
            // 끝 문자 삭제 후 앞의 문자들에서 파생되는 단어들 없으면 함께 삭제
            if (!cur.isTerminal && cur.child.isEmpty()) {
                node.child.remove(c);
            }
        }
        return true;
    }
}