트라이(Trie) 자료구조

1. 트라이 자료구조란?

문자열의 집합을 표현하는 트리 자료구조.

원하는 원소를 찾기 위해 자주 이용되는 이진 검색들은 원소를 찾는데 O(logN)의 시간이 걸린다.

문자열의 길이가 길수록 더욱 오래 걸리게 되고, 원하는 문자열을 찾는데 O(MlogN)의 시간이 걸리게 될 것이다.

이는 반복수행하게 된다면 더더욱 오래 걸리게 된다.

 

이를 해결한 것이 문자열 특화 자료구조, 트라이(Trie)이다.

문자열을 빠르게 탐색할 수 있는 자료구조

 

트라이 자료구조의 시간복잡도는 다음과 같다.

제일 긴 문자열을 L, 총 문자열의 수를 M이라고 할 때 생성시 시간 복잡도는 O(M*L)이다.

탐색시 시간복잡도는 O(L)이다.

 

 

2. 작동 원리

 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리이다.

한 문자열에서 다음에 나오는 문자가 현재 문자의 자식 노드가 되고, 빨간색 노드는 문자열의 끝이다.

트라이의 중요한 속성 중 하나는 루트에서 내려가는 경로에서 만나는 글자들을 모으면 찾고자 하는 문자열의 접두사를 얻을 수 있다는 것이다.

 

"rebro"를 찾는다고 했을 때,

r -> re -> reb -> rebr -> rebro로 각 노드는 접두사를 저장할 필요 없이 문자 하나만 저장해도 충분하게 된다.

 

 

3. 장단점

장점은 문자열을 빠르게 찾을 수 있다는 점.

단점은 필요한 메모리의 크기가 너무 크다는 점이다. 문자열이 모두 영문의 대소문자로만 되어 있다고 해도 자식 노드를 가리키는 포인터는 26가지나 된다. 최악의 경우 집합에 포함되는 문자열의 길이 총합만큼의 노드가 필요하게 되므로, 총 메모리는 O(포인터 크기 * 포인터 배열 개수 * 총 노드의 개수)가 된다.

 

즉, 1000자리 문자열이 1000개만 들어와도, 100만 개의 노드가 필요하고 포인터의 크기가 8byte면 200mb의 메모리가 필요하다.

 

이 단점을 해결하기 위해 보통 map이나 vector를 이용해 필요한 노드만 메모리에 할당하는 방식을 사용한다. 코딩테스트 문제에선 문제에 따라 메모리 제한이 빡빡하기에 최적화가 어렵고 사용을 못하는 경우도 더러 있다.

문제를 잘 읽고 트라이를 사용할 수 있는 문제인지 파악하는 것도 중요하다.

 

 

4. 구현

class TrieNode<Key>(var key: Key?, var parent: TrieNode<Key>?) {
	val children: HashMap<Key, TrieNode<Key>> = HashMap()
	var isTerminating = false
}

TrieNode data class를 만든다.

기본 노드와의 차이점으로는

 

1. TrieNode는 key를 파라미터로 가지고 있다.

Key에 데이터를 가지고 있기 때문이고, key는 없어도 되는 값이다.

왜냐하면 Trie의 루트 노드는 키를 비워놓는게 원칙이기 때문.

 

2. TrieNode는 문자와 자식 노드를 맵 형태로 가지고 있다.

 

3. val child 바이너리 트리에서는 2개의 자식만 가지고 있으나, Trie 자료구조에서는 여러 개의 자식을 가진다. 이를 Map에 저장한다.

 

4. terminal = collection의 끝을 나타낸다.

 

class Trie<Key> {
	private val root = TrieNode<Key>(key = null, parent = null)
}

 

Trie Class를 구현한다. 루트를 포함하고 있다.

 

삽입 함수

fun insert(list: List<Key>) {
    var current = root
    list.forEach { element->
    	if(current.children[element] == null) {
        	current.children[element] = TrieNode(element, current)
        }
        current = current.children[element]!!
    }
    current.isTerminating = true
}

 

Extension 사용시

fun Trie<Char>.insert(string: String) {
	insert(string.toList())
}

 

포함여부 함수

fun contains(list: List<Key>): Boolean{
	var current = root
    
    list.forEach{ element ->
    	val child = current.children[element]?: return false
        current = child    
    }
    
    return current.isTerminating
}

 

Extension 사용시

fun Trie<Char>.contains(string: String): Boolean {
	return contains(string.toList())
}

 

제거 함수

fun remove(collection: CollectionType) {
    var current = root
    
    collection.forEach {
    	val child = current.children[it]? : return
        current = child
    }
    if (!current.isTerminating) return
    current.isTerminating = false
   
    val parent = current.parent
    while(current.children.isEmpty() && !current.isTerminating) {
    	parent.let{
            it.children[current.key] = null
            current = it
        }
    }
}

 

Extension 사용시

fun Trie<Char>.remove(string: String) {
	remove(string.toList())
}

 

접두사 함수

fun collections(prefix: List<Key>): <List<Key>> {
    val current = root
    
    prefix.forEach { element->
    	val child = current.children[element]?: return emptyList()
        current = child
    
    }
    return collections(prefix, current)
}

private fun collections(prefix: List<Key>, node: TrieNode<Key>?): List<List<Key>>{
    val results = mutableListOf<List<Key>>()
    
    if(node?.isTerminating == true) {
    	results.add(prefix)
    }
    node?.children?.forEach { (key, node)->
    	results.addAll(collections(prefix + key, node))    
    }
    return results
}

 

Extension 사용시

fun Trie<Char>.collections(prefix: String): List<String> {
	return collections(prefix.toList()).map {
    	it.joinToString(separator = "")
    }
}

 

참고 자료 : 

https://underdog11.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Tries-%ED%8A%B8%EB%9D%BC%EC%9D%B4-%ED%95%84%EC%88%98-%EA%B8%B0%EB%B3%B8-%EC%A0%95%EB%A6%AC-Trie-%EA%B5%AC%EC%A1%B0-%EC%9E%A5%EC%A0%90-%EC%82%BD%EC%9E%85-Insert-%ED%8F%AC%ED%95%A8%EC%97%AC%EB%B6%80-contains-%EC%A0%9C%EA%B1%B0-remove-Kotlin-%EA%B5%AC%ED%98%84

[알고리즘] Tries 트라이 자료구조 : 필수 기본 정리 - 구조, 장점, 삽입 Insert, 포함여부 contains, 제

https://twpower.github.io/187-trie-concept-and-basic-problem

[Algorithm] 트라이(Trie) 개념과 기본 문제

https://rebro.kr/86

[자료구조] 트라이(Trie) 자료구조

https://velog.io/@wonseok/Tries-with-Kotlin#%EC%9A%94%EC%95%BD

Tries with Kotlin