Java Trie(트라이)란

 

출처 - 위키

• 트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조이다.

제일 긴 문자열의 길이를 L, 문자열들의 수 M이라 두었을 때, 

생성 시간복잡도 O(L*M)

탐색 시간복잡도 O(L) 이 걸린다.

 

아래는 구현 방법인데, 트라이는 코딩문제 기준으로 해당 문제의 조건에 따라 구현하는 것이 좋다. 무조건 밑을 따라가면 괜히 더 복잡해질 수도 있다. 그러니깐 아래의 구현코드를 보고 정말 제대로 이해를 한 다음에 트라이 기초문제들을 풀고 응용문제도 풀어보면서 감을 잡는게 정말 도움이 된다

• 구현

    class TrieNode{
        private Map<Character, TrieNode> childNodes = new HashMap<>();
        private boolean isLastChar;             //끝이 나는 단어인지 파악 여부를 위함이다. 만약 없다면 DOG 단어를 넣었는데
                                                //DO를 넣었는지 알 수 없기 때문이다.
 
        Map<Character,TrieNode> getChildNodes(){
            return this.childNodes;
        }
 
        boolean isLastChar(){
            return this.isLastChar;
        }
 
        void setIsLastChar(boolean isLastChar) {
            this.isLastChar=isLastChar;
        }
 
    }
 
    class Trie{
        private TrieNode rootNode;
 
        Trie(){
            rootNode=new TrieNode();
        }
 
        void insert(String word) {  //없다면 새 node를 만든다. 마지막 글자에 true 값으로 끝맺음을 나타냄
            TrieNode thisNode=this.rootNode;
            for (int i = 0; i < word.length(); i++) {
                thisNode=thisNode.getChildNodes().computeIfAbsent(word.charAt(i),c->new TrieNode());
            }
            thisNode.setIsLastChar(true);
        }
 
        //노드를 쭉 따라간다. 그리고 마지막에 lastChar로 여부를 가린다. DOG를 넣었는데 DO가 포함되어있냐 물을 때 이것으로 판단할 수 있다.
        boolean contains(String word) { 
            TrieNode thisNode=this.rootNode;
 
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                TrieNode node=thisNode.getChildNodes().get(c);
 
                if(node==null) return false;
 
                thisNode=node;
            }
            return thisNode.isLastChar();
        }
 
        void delete(String word) {
            delete(this.rootNode,word,0);
        }
 
        //삭제하기 위해서는 해당 마지막 위치가 lastChar true인지도 확인해야하고, 노드를 포함하는지도 확인해야 한다. 그리고, DOG를 삭제하고 싶은데
        //DOGGY라는 단어가 있으면 함부로 DOG를 삭제하지 못할 것이다. 이 때에는 lastChar 값만 false로 바꿔주었다.
        void delete(TrieNode thisNode, String word, int index) {
            char c = word.charAt(index);
 
            if(!thisNode.getChildNodes().containsKey(c))
                throw new Error("There is no ["+word+"] in this Trie.");
 
            TrieNode childNode = thisNode.getChildNodes().get(c);
            index++;
 
            if (index == word.length()) {
                if (!childNode.isLastChar())
                    throw new Error("There is no ["+word+"] in this Trie.");
                childNode.setIsLastChar(false);
 
                if (childNode.getChildNodes().isEmpty())
                    thisNode.getChildNodes().remove(c);
            }else{
                delete(childNode, word, index);
                if(!childNode.isLastChar()&&childNode.getChildNodes().isEmpty())
                    thisNode.getChildNodes().remove(c);
            }
        }
    }