개념정리 - Trie

 

이번 코테는 처음부터 끝까지 Trie 였다.

보자마자 Trie 라는 것을 파악하는 건 성공, but 매끄럽게 코드를 구현하기는 힘들었다.

 

--------

Trie 란?

Trie는 일반적인 Tree자료구조와 같은 모양이지만 저장하는 값이 다른 형태입니다.

 

위와 같은 정수형 자료의 이진트리에서는 검색을 수행할 때 O(logN)의 시간 복잡도를 가지게 된다.

그러나 같은 이진트리 형태 이어도 문자열을 저장하고 있다면 문자열의 길이가 M일 때,

O(M*logN)의 시간 복잡도를 가지게 된다.

이러한 문제를 해결하기 위해 Trie를 사용하는 것이다.

 

Trie는 루트 노드는 비어있고 첫 번째 자식 노드부터 문자열의 첫 단어가 저장된다.

현재 위 그림의 Trie에 저장된 문자는 cap, code, kakao, kai 이다.

 

Trie 자료구조는 문자열의 한 단어씩 자식 노드와 비교해가면서 검색을 진행할 수 있다.

예를 들어 cap을 검색한다면 c자식 노드 -> a자식 노드 -> p자식 노드 순으로 검색이 진행된다.

kakao를 검색한다면 k자식 노드 -> a자식 노드 -> k자식 노드 -> a자식 노드 -> o자식 노드

 

만약에 없는 단어를 검색한다면??

coding을 검색한다면 c자식 노드 -> o자식 노드 -> d자식 노드 -> i값을 가지는 자식 노드는 없으므로 검색 불가

이러한 식으로 찾고자 하는 문자를 탐색하므로 문자열의 길이가 M일 때,

탐색 시간 복잡도는 O(M)을 가지게 되므로 매우 효율적이라고 할 수 있다.

 

 

TrieNode

먼저 트라이의 노드 역할을 할 클래스부터 알아보자 ! 가장 중요한 구성 요소는 두 가지이다.

1. 자식 노드들을 담고있는 Map ( 문자열을 저장한다면 문자가 키, 노드가 밸류 )
2. 본인 노드가 어떠한 입력값의 말단 노드인지를 나타내는 boolean

이 외에도 기본적인 생성자, getter, setter 등 필요한 요소들을 구현해주면 된다.

 

import java.util.*;

class TrieNode {
    private Map<Character, TrieNode> childNodes = new HashMap<>();
    private boolean isLast;

    public Map<Character, TrieNode> getChildNodes() {
        return childNodes;
    }

    public boolean isLast() {
        return isLast;
    }

    public void setLast(boolean last) {
        isLast = last;
    }
}

이제 위의 트라이 노드를 이용하여 트라이 자료 구조를 구현해보자 !

기본적으로 아래의 코드처럼 root 노드를 초기화 해주어야 한다.

Trie

public class Trie {
    private TrieNode rootNode;

    Trie(){
        rootNode = new TrieNode();
    }   
}

1. insert

입력 받은 단어를 문자 순서대로 트리 계층 구조의 자식 노드로 생성하여 넣어준다.

• 이미 자식 노드에 같은 문자가 존재하면 새로 생성해주지 않고 자식 노드로 이동만 한다.
• 단어의 마지막 문자 노드에는 last 체크를 해준다.

void insert(String word){
        TrieNode node = this.rootNode;
        for(int i=0; i<word.length(); i++) node = node.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
        node.setLast(true);

2. contains

특정 단어가 트라이에 존재하는지 확인한다.

• 루트 노드부터 단어의 문자 순서대로 일치하는 자식 노드가 계층별로 있어야 한다.
• 단어의 마지막 문자에 last로 체크가 되어있어야 한다.
  위의 두 조건을 모두 만족하면 true, 그렇지 않으면 false

boolean contains(String word){
        TrieNode node = this.rootNode;
        char cur;
        for(int i=0; i<word.length(); i++){
            cur = word.charAt(i);
            if(!node.getChildNodes().containsKey(cur)) return false;
            node = node.getChildNodes().get(cur);
        }
        return node.isLast();
}

 

3. delete

트라이에 넣었던 단어를 삭제한다.

• 자식 노드는 부모 노드를 모르기 때문에 주어진 단어의 마지막 문자까지 이동하여 거꾸로 문자를 삭제해와야 한다. 이 과정은 재귀로 구현해주었다.
• 당연하게도 다음 문자에 해당하는 자식 노드가 존재해야 한다. 또한 삭제를 시작하는 마지막 노드는 last로 체크되어 있어야 한다. 이 두가지로 존재하지 않는 단어에 대한 삭제 예외를 잡아줄 수 있다.
• 단어 삭제를 의미하기 위해서 기본적으로 마지막 문자 노드의 last 체크를 해제해준 후, 아래의 조건에 맞추어 노드 삭제를 진행한다.
  • 자식 노드가 없어야 한다. 자식 노드가 있다면 다른 단어에도 사용되는 문자이므로 제거하면 안된다.
  • 자식 노드가 없더라도 last가 체크되어 있다면 다른 단어에 포함되는 문자이므로 제거하면 안된다.

void delete(String word){
        delete(this.rootNode, word, 0);
    }
    
    private void delete(TrieNode node, String word, int index){
        if(index == word.length()){
            if(!node.isLast()) throw new Error("not exist");
            node.setLast(false);
            return;
        }
        char cur = word.charAt(index);
        if(!node.getChildNodes().containsKey(cur)) throw new Error("not exist");
        TrieNode child = node.getChildNodes().get(cur);
        delete(node.getChildNodes().get(cur), word, index+1);
        if(child.getChildNodes().isEmpty()) {
            if(!child.isLast()) node.getChildNodes().remove(cur, child);
        }
}

전체 코드

import java.util.*;

class TrieNode {
    private Map<Character, TrieNode> childNodes = new HashMap<>();
    private boolean isLast;

    public Map<Character, TrieNode> getChildNodes() {
        return childNodes;
    }

    public boolean isLast() {
        return isLast;
    }

    public void setLast(boolean last) {
        isLast = last;
    }
}

public class Trie {
    private TrieNode rootNode;

    Trie(){
        rootNode = new TrieNode();
    }

    void insert(String word){
        TrieNode node = this.rootNode;
        for(int i=0; i<word.length(); i++) node = node.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
        node.setLast(true);
    }

    boolean contains(String word){
        TrieNode node = this.rootNode;
        char cur;
        for(int i=0; i<word.length(); i++){
            cur = word.charAt(i);
            if(!node.getChildNodes().containsKey(cur)) return false;
            node = node.getChildNodes().get(cur);
        }
        return node.isLast();
    }

    void delete(String word){
        delete(this.rootNode, word, 0);
    }
    
    private void delete(TrieNode node, String word, int index){
        if(index == word.length()){
            if(!node.isLast()) throw new Error("not exist");
            node.setLast(false);
            return;
        }
        char cur = word.charAt(index);
        if(!node.getChildNodes().containsKey(cur)) throw new Error("not exist");
        TrieNode child = node.getChildNodes().get(cur);
        delete(node.getChildNodes().get(cur), word, index+1);
        if(child.getChildNodes().isEmpty()) {
            if(!child.isLast()) node.getChildNodes().remove(cur, child);
        }
    }
}

https://velog.io/@cgw0519/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4

[자료구조] 트라이

https://codingnojam.tistory.com/40

[Algorithm] Trie를 Java로 구현해보자!