Trie란

Trie는 문자열 검색에 좋은 알고리즘이다.

영어를 저장할 때 Trie는 다음의 장점을 가지고 hash table을 대체할 수 있다.

1. 값을 탐색하는 것은 일반적으로 더 나은 worst-case 시간 복잡도를 가진다.
2. hash table과 달리, Trie는 key충돌을 걱정하지 않아도 된다.
3. unique한 path를 위해 해싱 알고리즘을 구현하지 않아도 된다.
4. Trie구조는 알파벳 순서로 정렬된다.

Trie 구현

다른 트리처럼 Trie또한 노드로 구현되어 있다. implementation은 TrieNode클래스와 Trie클래스로 구현될 것이다. TrieNode클래스는 character를 표현할 것이다.

TrieNode

class TrieNode<T: Hashable> {
  var value: T?
  weak var parent: TrieNode?
  var children: [T: TrieNode] = [:]
  
  init(value: T? = nil, parent: TrieNode? = nil) {
    self.value = value
    self.parent = parent
  }
}

func add(child: T) {
  // 1
  guard children[child] == nil else { return }

  // 2
  children[child] = TrieNode(value: child, parent: self)
}

T는 딕셔너리에 들어가야하기 때문에 Hashable해야한다. parent는 리테인 사이클 방지를 위해 들어가야 한다.

add에서 child가 이미 있으면 return한다.
없으면 새로운 TrieNode를 생성한다.

Trie

Trie class는 노드를 관리한다.

class Trie {
    fileprivate let root: TrieNode<Character>
    
    init() {
        root = TrieNode<Character>()
    }
}

extension Trie {
    func insert(word: String) {
        guard !word.isEmpty else {
            return
        }
        
        // 1
        var currentNode = root
        
        // 2
        for character in word.lowercased() {
            // 3
            if let childNode = currentNode.children[character] {
                currentNode = childNode
            } else {
                currentNode.add(value: character)
                currentNode = currentNode.children[character]!
            }
        }
        // Word already present?
        guard !currentNode.isTerminating else {
            return
        }
        
        // 4
        wordCount += 1
        currentNode.isTerminating = true
    }
    func contains(word: String) -> Bool {
        guard !word.isEmpty else { return false }
        
        // 1
        var currentNode = root
        
        // 2
        var characters = Array(word.lowercased())
        var currentIndex = 0
        
        // 3
        while currentIndex < characters.count, 
              let child = currentNode.children[characters[currentIndex]] {
            
            currentNode = child
            currentIndex += 1
        }
        
        // 4
        if currentIndex == characters.count && currentNode.isTerminating {
            return true
        } else {
            return false
        }
    }
    
    func remove(word: String) {
        guard !word.isEmpty else {
            return
        }
        
        // 1
        guard let terminalNode = findTerminalNodeOf(word: word) else {
            return
        }
        
        // 2
        if terminalNode.isLeaf {
            deleteNodesForWordEndingWith(terminalNode: terminalNode)
        } else {
            terminalNode.isTerminating = false
        }
        wordCount -= 1
    }
} 

시간 복잡도

contains - Worst Case O(n)
insert - O(n)
remove - O(n)

count - O(1)
words - O(1)
isEmpty - O(1)

공간 복잡도

Trie의 단점은 공간 복잡도가 높아 메모리를 많이 사용한다는 점이다.