얼마전 요즘 핫한 모 기업의 전화면접에서 광탈한 후 당시 받았던 질문이 문득 다시 떠올랐다. 사전을 구현해야 한다면 어떤 자료구조로 구현을 할거냐는 질문에 해쉬맵을 쓸거라고 답했고.. 면접관은 그럼 일부만이라도 포함된 단어를 정렬하여 리스팅 할려면 어떤 구조로 짤건지 질문했다. 여기서 나는 머리속이 하얘지면서 아무 생각도 나지 않고 트리(Tree) 밖에 생각이 나지 않아서 트리로 구현하겠다며 아무말 대잔치를 했는데.. 지금 찾아보니 내가 당시 생각했던 알고리즘과 대충 비슷하긴 하다. 발음도 비슷하다. Trie. 문자열 저장과 prefix 검색에 많이 쓰인다. 나무위키에 따르면 트라이라고 읽어도 되고 트리라고 읽어도 된단다.

특징

1. 기본적으로 트리(Tree) 기반의 자료구조다.
2. 자식 노드의 개수는 가변적이다. 즉 배열을 쓰거나?
3. 트리의 높이는 곧 자료구조 내 저장되어 있는 가장 긴 문자열이 될것이다.
4. 각 노드는 한개의 문자만을 표현한다.
5. 한개의 글자씩 노드에 연결되어있기에 N의 길이의 문자열을 검색시 O(N)의 시간복잡도를 가진다. 빠르다.
6. 대신 메모리를 왕창 먹는다. 공간복잡도가 높다.

대충 그림으로 그려보면 이렇게 생겼다.

보통 예제 코드들은 아스키코드, 즉 영어만 처리할 수 있게 만들어 놓은 경우가 많은데 나는 여기에 한글에 대한 처리를 추가했다.

한마디로 한글이라는 단어가 있다면 ㅎㅏㄴㄱㅡㄹ 이렇게 나눠서 처리하는거다. 한글이라는 단어가 Trie 에 포함되어있다면 ㅎ 만 검색해도 한글이 검색결과에 나오게 되는것.

테스트 코드도 넣고 하다보니 블로그에 올리기엔 코드가 꽤 길어져서 따로 git에 올렸다. 링크