루비에서 접두사 트리 구현하기

접두사 트리(Prefix Tree), 또는 트라이(Trie)는 문자열 검색을 효율적으로 수행할 수 있는 자료구조입니다. 이 자료구조는 특히 자동 완성 기능이나 사전 검색과 같은 애플리케이션에서 유용하게 사용됩니다. 이번 글에서는 루비를 사용하여 접두사 트리를 구현하는 방법을 알아보겠습니다.

접두사 트리란?

접두사 트리는 문자열의 접두사를 저장하는 트리 구조입니다. 각 노드는 문자 하나를 나타내며, 루트 노드에서 시작하여 각 문자에 따라 자식 노드로 이동합니다. 이 구조의 주요 장점은 다음과 같습니다:

효율적인 문자열 검색
자동 완성 기능 구현
중복 문자열 저장 최소화

접두사 트리의 기본 구조

접두사 트리를 구현하기 위해서는 먼저 노드(Node) 클래스를 정의해야 합니다. 각 노드는 다음과 같은 속성을 가집니다:

문자(character)
자식 노드(children)
단어의 끝 여부(is_end_of_word)

노드 클래스 구현

아래는 루비로 노드 클래스를 구현한 예시입니다:

class TrieNode
  attr_accessor :children, :is_end_of_word

  def initialize
    @children = {}
    @is_end_of_word = false
  end
end

트라이 클래스 구현

이제 트라이(Trie) 클래스를 구현해 보겠습니다. 이 클래스는 문자열을 삽입하고 검색하는 기능을 제공합니다.

트라이 클래스의 기본 구조

트라이 클래스는 다음과 같은 메서드를 포함합니다:

insert(word): 단어를 트리에 삽입
search(word): 단어가 트리에 존재하는지 확인
starts_with(prefix): 주어진 접두사로 시작하는 단어가 있는지 확인

트라이 클래스 구현

class Trie
  def initialize
    @root = TrieNode.new
  end

  def insert(word)
    node = @root
    word.each_char do |char|
      node.children[char] ||= TrieNode.new
      node = node.children[char]
    end
    node.is_end_of_word = true
  end

  def search(word)
    node = find_node(word)
    node && node.is_end_of_word
  end

  def starts_with(prefix)
    !!find_node(prefix)
  end

  private

  def find_node(word)
    node = @root
    word.each_char do |char|
      return nil unless node.children[char]
      node = node.children[char]
    end
    node
  end
end

접두사 트리 사용 예시

이제 구현한 접두사 트리를 사용하여 몇 가지 예시를 살펴보겠습니다.

trie = Trie.new
trie.insert("apple")
trie.insert("app")
trie.insert("banana")

puts trie.search("apple")  # true
puts trie.search("app")    # true
puts trie.search("appl")   # false
puts trie.starts_with("ap") # true
puts trie.starts_with("ban") # true
puts trie.starts_with("bat") # false

접두사 트리의 장점과 단점

접두사 트리는 여러 가지 장점이 있지만, 단점도 존재합니다. 아래에서 각각을 살펴보겠습니다.

장점

빠른 검색 속도: 문자열의 길이에 비례하여 검색 속도가 결정되므로, 긴 문자열을 다룰 때 유리합니다.
메모리 효율성: 중복된 접두사를 공유하므로 메모리 사용량이 줄어듭니다.
자동 완성 기능 구현에 적합: 사용자가 입력하는 동안 가능한 단어를 빠르게 찾을 수 있습니다.

단점

메모리 사용: 많은 문자열을 저장할 경우, 각 문자에 대한 노드를 생성해야 하므로 메모리 사용량이 증가할 수 있습니다.
구현 복잡성: 다른 자료구조에 비해 구현이 복잡할 수 있습니다.

결론

이번 글에서는 루비를 사용하여 접두사 트리를 구현하는 방법을 알아보았습니다. 접두사 트리는 문자열 검색과 자동 완성 기능을 구현하는 데 매우 유용한 자료구조입니다. 이 자료구조의 장점과 단점을 이해하고, 필요에 따라 적절히 활용해 보시기 바랍니다. 루비로 접두사 트리를 구현하는 과정이 여러분에게 도움이 되었기를 바랍니다!