![[알고리즘] Tries 트라이 자료구조 : 필수 기본 정리 - 구조, 장점, 삽입 Insert, 포함여부 contains, 제거 remove - Kotlin 구현](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FuV8vm%2Fbtrhqff2CLm%2F6mqKWxdTngVfcrkAVczW81%2Fimg.png)
목차
Trie 자료 구조 개념
우리가 구글 엔진에서 방대한 자료 중 검색어를 찾을 때 위와 같이 뒤에 올 연관 검색을 찾아주거나, 사전에서 단어 검색을 할 때 자동완성시켜줄 때처럼 Trie는 문자열을 저장하기 위해 가장 효율적인 자료구조입니다. Trie 자료구조를 그림으로 나타내보겠습니다.
springBoot, springCloud, springMvc sports라는 문자열들을 저장한다고 가정합시다. 그리고 springBoot를 검색할 때 node에 있는 character하나하나씩 접근하면서 문자열을 찾게 됩니다. 우리가 사전에서 단어를 찾을 때와 비슷한 메커니즘입니다. 한 글자씩 찾아가며 문자열에 도달합니다.
Trie 자료 구조의 장점
words라는 Array에 몇 개의 단어가 있다고 가정해봅시다.
class EnglishDictionary {
private val words: Array<String> = ...
fun words(prefix: String) = words.filter{
it.startsWith(prefix)
}
}우리는 찾는 단어를 prefix라는 string에 지정하여, words array에서 한 글자씩 확인해가며 매치되는 string이 나올 때까지 찾기 시작합니다. array개수가 많지 않으면 문제없지만, 몇천 개의 단어를 가지고 있다면, 코드가 비효율적으로 작동하여, 성능 저하를 일으키게 됩니다. 시간 복잡도에서 words함수는 O(k*n)입니다. n은 words의 개수이고 k는 가장 긴 string에 길이입니다. string길이가 길고 word 개수가 많아지면 점점 비효율적이기 때문에 이러한 상황에 우리는 Trie자료구조를 사용해야 합니다.
Trie 구현
TrieNode 클래스를 만들어주겠습니다.
class TrieNode<Key>(var key: Key?, var parent: TrieNode<Key>?) {
val children: HashMap<Key, TrieNode<Key>> = HashMap()
var isTerminating = false
}TrieNode와 기본 노드의 차이
1. triNode는 파라미터로 key를 가지고 있습니다. key에 데이터를 가지고 있게 됩니다. key는 없어도 되는 값입니다. 왜냐하면, trie의 루트 노드는 키를 비워놓는 게 원칙이기 때문입니다.
2. 트라이 노드는 문자와 자식 노드를 맵 형태로 가지고 있다.
3. val children: 바이너리 트리에서는 2개의 자식만 가지고 있었지만, trie 자료구조에서는 여러 개의 자식을 가지게 됩니다. 그래서 자식의 정보를 HashMap()에 저장합니다.
4. is terminating: collection의 끝을 나타냅니다.
Trie 클래스 구현
다음으로 만들어줘야 할 것은 Trie 클래스입니다.
class Trie<Key> {
private val root = TrieNode<Key>(key = null, parent = null)
}특별한 건 없고 루트를 포함하고 있습니다.
다음으로 만들어줘야 할 함수는 insert, contains, remove, prefix match입니다.
삽입 Insert
insert함수입니다.
Insert
fun insert(list: List<Key>) {
//1
var current = root
//2
list.forEach { element->
if(current.children[element] == null) {
current.children[element] = TrieNode(element, current)
}
current = current.children[element]!!
}
//3
current.isTerminating = true
}1. current는 포인터 역할을 합니다. 여기저기 돌아다니면서, node를 확인할 때 현재 보고 있는 node를 뜻합니다. Root 노드에서부터 시작합니다.
2. 현제 노드의 자식 맵에 찾는 element가 있는지 먼저 확인합니다. 없다면, 현재 노드에 자식 노드를 새로 추가해야 한다.
3. for Loop가 끝나면, current가 리스트에 끝에 와있어야 합니다.
**Extension을 이용하여 간단하게 구현할 수 있습니다.**
fun Trie<Char>.insert(string: String) {
insert(string.toList())
}
삽입 과정을 다이어그램으로 확인해보겠습니다.
- bed라는 단어를 사전에 추가한다 가정해봅시다.
- 먼저 currentnode가 root에서 시작해서 childmap에서 bed의 가장 첫 글자인 b를 찾습니다.
- b가 존재하기 때문에 currentNode는 b로 업데이트됩니다.
- b의 다음으로 와야 할 e를 b의 자식에서 찾습니다.
- 찾았다면 currentNode는 이제 e가 됩니다.
- e의 자식 맵에서 d 찾습니다.
- 존재하지 않기 때문에 우리는 d를 추가해줘야 합니다.
포함여부 Contains
contain은 포함 여부를 확인합니다. insert와 비슷한 구현 방식을 가지고 있습니다.
fun contains(list: List<Key>): Boolean{
var current = root
list.forEach{ element ->
val child = current.children[element]?: return false
current = child
}
return current.isTerminating
}- 먼저 트리에 찾는 값이 있는지 element를 하나씩 접근하여 찾습니다.
- 있다면 isTerminating이 실행되고 없다면, 트리 안에 찾는 값이 없다는 의미입니다.
- 시간 복잡도에서 contain함수는 O(k)입니다. 이 말은 k(element의 수)가 많으면 많을수록 오래 걸리게 됩니다.
**Extension을 이용해 간단하게 구현할 수 있습니다. **
fun Trie<Char>.contains(string: String): Boolean {
return contains(string.toList())
}제거 Remove
제거 과정은 좀 더 복잡합니다. 왜냐하면, 특정 노드가 다른 노드와 공유되고 있을 수도 있기 때문입니다. 트라이에서 단어 삭제는 재귀를 통해 아래에서부터 위로 올라가면서 단어에 포함된 문자의 노드를 제거합니다. 먼저 코드를 보고 과정을 살펴보겠습니다.
fun remove(collection: CollectionType) {
//1
var current = root
collection.forEach {
val child = current.children[it]? : return
current = child
}
if (!current.isTerminating) return
//2
current.isTerminating = false
//3
val parent = current.parent
while(current.children.isEmpty() && !current.isTerminating) {
parent.let{
it.children[current.key] = null
current = it
}
}
}1. contain구현과 같습니다. 그리고 우리가 찾는 값이 트라이에 있는지 확인하는 동시에 currentNode를 리스트에 끝으로 이동시킵니다.
2. isTerminating이 true라면 list에 끝에 있음을 의미합니다. 현재 노드에 isTerminating을 false로 바꾸면서, 현재 노드를 지울 수 있게 합니다.
3. 트라이 자료구조 특성으로 노드들을 공유하기 때문에 노드를 지울 때 공유하는 노드를 지워서는 안 됩니다.
- current.children.isEmpty: 이 코드에서는 현재 노드가 자식에 도달했을 때 비어있는지 확인합니다. 현재 노드에 도달했는데 여전히 자식 노드가 존재한다면, 현재 문자를 필요로 하는 다른 단어가 존재한다는 뜻입니다.
- current.isTerminating: 현재 노드가 리스트의 마지막 노드 가아니라면 current.isTerminainting은 false이어야 합니다. 예를 들어 bear라는 단어에 r노드는 마지막 노드입니다. 현재 노드가 r을 가리킨다면 current.isTerminating은 true입니다.
- 제거 오퍼레이션은 시간 복잡도에서 O(k)입니다 문자의 길이가 길수록 더 오래 걸립니다.
**제거 또한 Extension을 이용해서 간단하게 구현할 수 있습니다.**
fun Trie<Char>.remove(string: String) {
remove(string.toList())
}
더 쉬운 설명을 위해 다이어그램을 이용해서 예제를 다뤄보겠습니다.
beer라는 단어를 트리에서 삭제한다고 가정해봅시다.
위에서 언급했듯이, 위로 올라가며 element를 제거합니다. 그렇기 때문에 currentNode가 만약 값을 가지고 있다면, 다른 단어가 그 element를 필요로 한다는 의미이기 때문에 지워지지 않고 남아있게 됩니다(current.isTerminating = false). 만약 지워져야 할 노드라면 current.isterminating 이 true로 되어있기 때문에 currentnode로 선택될 때 지워집니다.
접두사 Prefix matching
가장 trie를 이상적으로 쓸 수 있는 prefix-matching알고리즘입니다. 코드로 살펴보겠습니다.
fun collections(prefix: List<Key>): <List<Key>> {
//1
val current = root
prefix.forEach { element->
val child = current.children[element]?: return emptyList()
current = child
}
//2
return collections(prefix, current)
}1. prefix(접두사 ex) tri-, re-...)가 있는 지먼저 체크합니다. 없다면 빈 리스트를 반환합니다.
2. prefix에 끝을 알려주는 node를 찾은 후, 반복 헬퍼 method를 가져와서 currentnode이후 모든 seqeuence들을 찾습니다.
그다음 위 코드의 반환 값인 collections 헬퍼 method를 구현해줍니다.
private fun collections(prefix: List<Key>, node: TrieNode<Key>?): List<List<Key>>{
//1
val results = mutableListOf<List<Key>>()
if(node?.isTerminating == true) {
results.add(prefix)
}
//2
node?.children?.forEach { (key, node)->
results.addAll(collections(prefix + key, node))
}
return results
}1. 결괏값을 저장하기 위한 mutableList를 만들어줍니다. 현재 노드가 terminating 노드라면 (collection의 끝 노드) 해당하는 prefix를 results에 넣어줍니다.
2. 다음으로 현재 노드의 자식들을 확인해줍니다. 모든 자식 노드에게 collections를 실행시켜 다른 terminating node를 찾습니다.
- collection()은 시간 복잡도에서 O(k * m) 오퍼레이션입니다. m은 prefix가 매치하는 collection의 개수입니다.
- 이는 시간 복잡도 형태는 array와 같습니다. Array 또한 O(k * n) 오퍼레이션이고 그 이유는 n의 개수는 collection안에 element개수이기 때문입니다.
- 그러므로 prefix를 찾을 때는 trie를 사용하는 게 성능적인 면에서 훨씬 뛰어납니다.
**Extension을 이용해 간단하게 구현할 수 있습니다. **
fun Trie<Char>.collections(prefix: String): List<String> {
return collections(prefix.toList()).map {
it.joinToString(separator = "")
}
}
메인 문에서 prefix matching을 실행해보겠습니다.
"prefix matching" example {
val trie = Trie<Char>().apply {
insert("car")
insert("card")
insert("care")
insert("cared")
insert("cars")
insert("carbs")
insert("carapace")
insert("cargo")
}
println("\nCollections starting with \"car\"")
val prefixedWithCar = trie.collections("car")
println(prefixedWithCar)
println("\nCollections starting with \"care\"")
val prefixedWithCare = trie.collections("care")
println(prefixedWithCare)
}결과는 아래와 같습니다.
---Example of prefix matching---
collections starting with "car"
[car, carapace, carbs, cars, card, care, cared, cargo]
collections starting with "care"
[care, cared]