자료구조에서 trie, radix trie란?

[그림 1, 2] trie와 radix trie

* Trie

컴퓨터 공학에서 trie, 혹은 prefix tree라 함은, 주로 스트링을 가지는 동적 셋 혹은 연관 배열을 저장하는데 사용되는 정렬된 트리 자료구조를 의미한다. 이진 검색 트리와는 다르게, 트리상에서의 노드들은 그 노드와 연관된 키를 저장하지 않는다. 이 대신, 트리상에서의 위치가 현재의 키를 나타낸다. 특정 노드의 모든 후손들은 그 노드에서와 동일한 prefix를 가지며, 루트 노드는 빈 문자열을 갖는다. 값은 모든 노드에서 존재하는 것이 아니고, 말단 노드(leaves) 혹은 특정 키에 해당하는 내부(inner) 노드에서만 존재한다. prefix tree의 공간사용을 최적화 하 위하여, compact prefix tree가 구상되었다. trie라는 단어는 reTRIEval이라는 단어에서 유래하였다. 이 단어를 만들어낸 Edward Fredkin은 이 단어를 'tree'와 동일하게 발음하지만, 다른 이들은 이것을 'trai'로 발음한다. 

아래 예제에서보자면, 각 노드에서는 키가 나타나져있으며, 값은 그 아래에 위치한다. 각각의 완전한 영어단어는 그에 해당하는 가상의 정수값을 갖는다. trie는 비록 각 끝(edge)의 심볼이 가지의 순서를 통해 암시적으로 나타나지만, 결정 유한 오토머턴의 형태를 띈다. 키들은 각 노드에서 명시적으로 표현될 필요는 없다(예제에서는 tire의 이해를 돕기위해 모두를 명시하였다)

출처 : http://en.wikipedia.org/wiki/Trie

* Radix tree

컴퓨터 공학에서 radix tree, patricia trie, radix trie, compact prefix tree 이 모두는 공간사용이 최적화된 trie 자료구조를 의미하며, 이것의 특징은 만약 특정노드의 자손이 하나밖에 없다면 그 노드는 자식노드와 결합된다는 것이다. 이 결과로서 모든 내부 노드는 적어도 두명이상의 자손을 가지게 된다. 기존의 trie구조와 다르게, 끝(edge)은 개체(들)의 순서로 label될 수 있다. 이것은 작은 셋을 가지는 경우 또는 긴 prefix를 갖는 경우에 유리하게 작용한다. 

출처 : http://en.wikipedia.org/wiki/Compact_prefix_tree

==================

사전 혹은 인터넷 자동완성의 retrieval을 효과적으로 할 수 있는 자료구조이다. (즉, text processing) 예를 들자면 '트리'라는 단어가 있다면, ㅌ->트->트ㄹ->트리 이런 형태로서 진행되는것이다. 노드의 후손들이 동일한 prefix를 가진다는 점에서 longest prefix matching(LPM)에 효과적이다. 좀 더 교과서적인 설명은 "트라이(trie) [출처] 트라이(trie)|작성자 하늘로" 에서 찾아볼 수 있다. 아래에 동영상 강의도 첨부해본다.

Lecture - 18 Tries