[trie] Implement Trie (Prefix Tree)

생전 처음들어보는 단어지만, 혹시나 싶어 이거 딱 한문제만 풀면서 정리해보려 한다.

 

Trie는 일종의 자료구조인데, 검색어 자동완성 같은 모듈에 주로 사용되는 것 같다

루트노드는 자식만 가지고 있고, 자식들은 알파벳으로 구성된 key를 가지고 있으며, value가 다시 그 자식노드를 가리킨다.

그러니까 각 노드가 공통의 접두어를 가리킨다고 보면 될 것같다.

 

이 자료구조는 value, children, end를 가지고 있다.

 

특정 word를 insert하면, root의 자식들에 연쇄적으로 word에서 잘라낸 글자 하나가  insert 되는 형식이다.

 

search하는 방식도 동일하다.