[알고리즘] 트라이(trie)

트라이

트라이(trie)는 탐색 트리의 일종으로, 동적 집합이나 연관 배열을 저장하는 데 사용되는 트리 자료 구조를 뜻한다. 일반적으로 문자열을 저장하고 효율적으로 탐색하기 위해 사용된다.

예) “A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”를 키로 둔 트라이

이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키를 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다.

노드의 모든 하위 노드는 노드에 연관된 문자열을 접두사로 공유한다. 루트는 빈 문자열에 연관된다.

위의 그림 예시에서 to, te 노드가 상위 노드 t를 접두사로 가지고 tea, ted, ten 노드가 te를 접두사로 가지는 것과 같다.

장점

1. 문자열 탐색시 하나씩 비교하며 탐색 하는 것 보다 훨씬 효율적이다. (가장 긴 문자열의 길이가 n이라 할 때 O(n)의 시간 복잡도를 가진다.)

단점

1. 각 노드마다 하위 노드를 배열로 모두 저장하므로 메모리 차지를 많이 한다.
2. 문자열로 장황하게 표시되는 자료의 경우 무의미하게 길게 늘어진 접두사와 노드를 가질 수 있다.

트라이(trie) 구현 - Kotlin

다음은 트라이의 노드를 표현하는 TrieNode 클래스이다.
각 노드에 해당하는 값(v)와 하위 노드들(children)을 프로퍼티로 가진다.

data class TrieNode(
    var v : Int,
    val children : MutableMap<Char,TrieNode> = mutableMapOf()
)

다음은 삽입 함수로 문자열을 트라이에 추가하고 연관된 값을 입력한다.
함수의 구조는 다음과 같다.

1. 현재 문자가 하위 노드에 있는지 확인
   • 있다면 하위 노드로 이동
   • 없다면 그 문자와 연관된 하위 노드 생성
2. 문자열이 끝나지 않았다면 다음 문자로 이동 후 과정 1. 반복

fun insert(word : String, value : Int){
    var node = this
    for (c in word){
        if (node.children.containsKey(c)){
            node = node.children[c]!!
        } else {
            node.children[c] = Trie(0)
            node = node.children[c]!!
        }
    }
    node.v = value
}

다음은 탐색 함수로 문자열(key)에 해당하는 값을 반환한다.

fun find(word : String) : Int {
    var node = this
    for (c in word){
        if (node.children.containsKey(c)){
            node = node.children[c]!!
        } else return 0 //default value
    }
    return node.v
}

---

참조 문헌

1. 위키 백과 - 트라이