트라이란?

트라이(Trie)란?

문자열에 특화된 자료 구조인 트라이(Trie)는 문자열 집합을 표현하는 자료구조이며, 원하는 원소를 찾는 작업을 O(n)에 해결할 수 잇는 자료구조이다.

 

트라이의 단점

공간 복잡도가 치명적인 단점이다.

O(포인터의크기 * 포인터 배열 개수 * 트라이에 존재하는 총 노드 수)

 

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

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

    boolean isLast() {
        return isLast;
    }

    void setisLast(boolean isLast) {
        this.isLast = isLast;
    }
}

public class Trie {
    private TrieNode rootNode;
    Trie() {
        rootNode = new TrieNode();
    }
}

 

 

www.crocus.co.kr/1053

트라이(Trie) 자료구조

 

the-dev.tistory.com/3

[자료구조] Trie(트라이)-2 : 자바로 구현하기