trie

IR group의 하얀 눈길님이 적으신 글 중 trie에 대한 설명이 있어서 스크랩 해 왔다.

원문은 여기서 볼 수 있다.



array-based trie
trie란 바이너리 트리의 특이한 경우로 보면 되겠다. 보통 문자열을 처리하기 위해 사용되며, 속도가 빠르고 공간을 적게 차지하기 때문에 검색엔진에서는 사전과 역화일의 인덱스 정보를 저장하는데 주로 사용한다. 여기서 구현할 trie의 구조는 다음과 같다.

예) “추석, 추억, 가을, 가나, 가나다라”을 저장하는 트라이

문자열에서 각 음절을 하나의 depth(자식노드)로 볼 수 있으며 같은 depth의 음절은 바로 앞의 음절이 같을 경우 형제노드로 볼 수 있다.
위 예에서 보면 처음 “추석”이 저장될 때 ‘추’ 가 루트가 되어고 ‘석’이 추의 자식노드로 저장된다. 다음에 “추억”이 저장될 때 ‘추’가 루트에 있으므로 첫음절은 같은 부모노드를 공유하고 ‘억’을 자식노드로 저장한다. 이때 자식노드에 이미 ‘석’이 있고 ‘석’과 ‘억’은 형제노드 관계에 있으므로 ‘석’의 오른쪽 노드에 ‘억’을 저장하게 된다.
다음에 “가을”을 저장할 때 ‘가’는 첫음절이므로 루트노드와 비교를 하고, 이미 ‘추’가 있으므로 ‘추’와 ‘가’는 형제노드가 되며, ‘가’가 더 작은 값이기 때문에 ‘추’의 앞에 ‘가’를 삽입하고 ‘가’의 오른쪽 노드를 ‘추’로 지정해 준다. 그리고 나서 ‘을’을 저장할 때 ‘가’의 자식노드가 되므로 왼쪽 노드를 추가하고 ‘을’을 저장한다.
다음에 “가나”가 입력되면, ‘가’가 루트노드에 존재하므로 ‘을’을 저장할 때 ‘가’와 같은 부모를 갖게 하고 자식노드를 삽입한다. 이때 자식노드에 이미 ‘을’이 있으므로 ‘나’와 ‘을’은 형제관계가 되고 ‘나’를 ‘을’ 앞에 삽입하게 된다.
“가나다라”가 입력되면, 마찬가지 방식으로 trie에 저장되게 된다.