swift-algorithm-club

트라이(Trie)

이 주제에 대한 튜토리얼은 여기에서 확인할 수 있다.

트라이(Trie)란 무엇인가?

트라이는 접두사 트리(prefix tree)라고도 불리며, 어떤 구현에서는 기수 트리(radix tree)라고도 한다. 이는 연관 데이터 구조를 저장하기 위해 사용되는 특별한 형태의 트리다. 사전을 저장하는 트라이는 다음과 같은 모습을 보인다:

트라이

트라이의 주요 사용 사례 중 하나는 영어 단어를 저장하는 것이다. 트라이의 각 노드는 단어의 한 문자를 나타낸다. 여러 노드가 연결되면 하나의 단어를 구성한다.

트라이(Trie)를 사용하는 이유

트라이는 특정 상황에서 매우 유용하다. 주요 장점은 다음과 같다:

일반적인 알고리즘

Contains (또는 일반적인 조회 메서드)

Trie 구조는 조회 작업에 매우 적합하다. 영어를 모델링한 Trie 구조에서 특정 단어를 찾는 것은 몇 번의 포인터 탐색으로 가능하다:

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
  }
}

contains 메서드는 상당히 직관적이다:

  1. root에 대한 참조를 생성한다. 이 참조는 노드 체인을 따라 내려갈 수 있게 해준다.
  2. 매칭하려는 단어의 문자를 추적한다.
  3. 포인터를 노드를 따라 이동시킨다.
  4. isTerminating은 이 노드가 단어의 끝인지 여부를 나타내는 불리언 플래그다. 이 if 조건이 충족되면 trie에서 단어를 찾았다는 의미다.

삽입

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]!
    }
  }
  // 단어가 이미 존재하는지 확인
  guard !currentNode.isTerminating else {
    return
  }

  // 4
  wordCount += 1
  currentNode.isTerminating = true
}
  1. 루트 노드에 대한 참조를 생성한다. 이 참조를 사용해 노드 체인을 따라 이동한다.
  2. 단어의 각 글자를 하나씩 순회한다.
  3. 삽입하려는 글자를 나타내는 노드가 이미 존재하는 경우가 있다. 예를 들어, “Apple”과 “App”처럼 공통 글자를 공유하는 단어가 Trie에 있는 경우가 이에 해당한다. 글자가 이미 존재하면 해당 노드를 재사용하고 체인을 더 깊이 탐색한다. 그렇지 않으면 새로운 노드를 생성한다.
  4. 단어의 끝에 도달하면 isTerminating을 true로 설정해 해당 노드가 단어의 끝임을 표시한다.

키 제거

Trie에서 키를 제거하는 작업은 약간 까다롭다. 여러 가지 경우를 고려해야 하기 때문이다. Trie의 노드는 여러 단어 간에 공유될 수 있다. 예를 들어, “Apple”과 “App”이라는 두 단어를 생각해 보자. Trie 내부에서 “App”을 나타내는 노드 체인은 “Apple”과 공유된다.

만약 “Apple”을 제거하려면, “App” 체인을 그대로 유지해야 한다.

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
}
  1. findTerminalNodeOf 함수는 Trie를 순회하며 word를 나타내는 마지막 노드를 찾는다. 만약 문자 체인을 따라갈 수 없다면 nil을 반환한다.
  2. deleteNodesForWordEndingWith 함수는 뒤로 순회하며 word를 나타내는 노드를 삭제한다.

시간 복잡도

Trie에서 어떤 값의 길이를 n이라고 가정한다.

주요 연산

자세한 내용은 위키피디아 Trie 항목을 참고한다.

Swift Algorithm Club을 위해 Christian Encarnacion이 작성. Kelvin Lau가 리팩토링

Rick Zaccone의 변경 사항