트라이(Trie)는 트리 중 하나로, 주로 문자열을 키로 사용하여 관련된 데이터를 저장하는 데이터 검색에 특화된 자료 구조이다.

일반적으로 문자열 검색에 사용되어 빠른 검색 속도와 메모리를 효율적으로 사용할 수 있다.

  • 특정 접두사로 시작하는 모든 단어를 검색하는 경우 해당 접두사 노드로 들어가 관련 단어를 검색하기 때문에 효율적 탐색할 수 있다.
  • 공통되는 접두사를 공유하기 때문에 비슷한 접두사를 가지는 단어가 많을수록 메모리의 효율적으로 관리할 수 있다.

트라이는 각 노드가 문자 하나를 나타내며, 루트 노드부터 시작하여 현재 노드에서 만들 수 있는 다음 문자들의 링크들을 가지고 있다. 이를 통해서 문자열을 검색할 때 노드들을 순회하며 검색을 수행한다.

주로 문자열 검색과 관련된 솔루션을 제공한다. 예를 들어 사전에서 단어를 검색하거나 자동 완성 기능에 사용할 수 있다.

시간 & 공간 복잡도

Operation Average Worst case
Search O(n) O(n)
Insert O(n) O(n)
Delete O(n) O(n)

https://en.wikipedia.org/wiki/Trie

구현

class TrieNode {
    val children = mutableMapOf<Char, TrieNode>()
    var isEndOfWord = false
}

class Trie {
    private val root = TrieNode()

    fun insert(word: String) {
        var current = root
        for (char in word) {
            val node = current.children.getOrPut(char) { TrieNode() }
            current = node
        }
        current.isEndOfWord = true
    }

    fun search(word: String): Boolean {
        var current = root
        for (char in word) {
            val node = current.children[char] ?: return false
            current = node
        }
        return current.isEndOfWord
    }

    fun startsWith(prefix: String): Boolean {
        var current = root
        for (char in prefix) {
            val node = current.children[char] ?: return false
            current = node
        }
        return true
    }
}