[260127화] 자료구조 트라이에 대해서 설명해주세요.

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

트라이는 문자열을 탐색할 때 단순히 비교하는 것에 비해서 효율적으로 찾을 수 있지만, 각 정점이 지식에 대한 링크를 모두 가지고 있기 때문에 저장 공간을 더욱 많이 사용한다는 특징이 있다. 

주로, 검색어 자동완성이나 사전 찾기 기능을 구현할 때 트라이 구조를 고려할 수 있다. 

 

출처 : 위키백과

 

어떻게 구현? 

루트는 항상 비어있다. 

각 간선은 추가될 문자를 키로 가지고 있다. 

각 정점은 이전 정점의 값과 간선의 키를 더한 값으로 가진다. 

해시 테이블과 연결 리스트를 이용해서 구현할 수 있다. 

 

class Node {
	public String value;
    public Map<String, Node> children;
    
    public Node(String value) {
    	this.value = value;
        this.children = new HashMap<>();
    }
}