Implementación de Árboles de Prefijos en Ruby

Los árboles de prefijos, también conocidos como tries, son estructuras de datos que se utilizan principalmente para almacenar cadenas de texto. Son especialmente útiles para tareas como la búsqueda de palabras, la autocompletación y la verificación de prefijos. En este artículo, exploraremos cómo implementar un árbol de prefijos en Ruby, paso a paso, y discutiremos sus aplicaciones y beneficios.

¿Qué es un Árbol de Prefijos?

Un árbol de prefijos es una estructura de datos que organiza cadenas de texto de manera que las cadenas que comparten un prefijo común se almacenan en la misma rama del árbol. Cada nodo del árbol representa un carácter de una cadena, y la ruta desde la raíz hasta un nodo específico representa el prefijo de las cadenas almacenadas.

Por ejemplo, si tenemos las palabras "gato", "gato", "gallina" y "gallo", el árbol de prefijos se vería algo así:

        (raíz)
         /   \
       g       g
      /         \
     a           a
    / \         / \
   t   l       l   o
  /     \     /
 o       i   i

Ventajas de Usar Árboles de Prefijos

Búsqueda Rápida: La búsqueda de palabras o prefijos es muy eficiente, ya que se puede realizar en tiempo O(m), donde m es la longitud del prefijo.
Autocompletado: Permiten implementar funciones de autocompletado de manera efectiva.
Almacenamiento Eficiente: Pueden ahorrar espacio al compartir prefijos comunes entre palabras.
Verificación de Palabras: Facilitan la verificación de la existencia de palabras en un conjunto.

Implementación de un Árbol de Prefijos en Ruby

A continuación, implementaremos un árbol de prefijos en Ruby. Comenzaremos creando una clase para el nodo del árbol y luego la clase principal para el árbol de prefijos.

Clase Nodo

La clase Nodo representará cada nodo en el árbol. Cada nodo tendrá un hash para almacenar sus hijos y un booleano para indicar si representa el final de una palabra.

class Nodo
  attr_accessor :hijos, :es_final

  def initialize
    @hijos = {}
    @es_final = false
  end
end

Clase Árbol de Prefijos

Ahora, crearemos la clase principal para el árbol de prefijos. Esta clase tendrá métodos para insertar palabras, buscar palabras y buscar prefijos.

class ArbolDePrefijos
  def initialize
    @raiz = Nodo.new
  end

  def insertar(palabra)
    nodo_actual = @raiz
    palabra.each_char do |caracter|
      nodo_actual.hijos[caracter] ||= Nodo.new
      nodo_actual = nodo_actual.hijos[caracter]
    end
    nodo_actual.es_final = true
  end

  def buscar(palabra)
    nodo_actual = @raiz
    palabra.each_char do |caracter|
      return false unless nodo_actual.hijos[caracter]

      nodo_actual = nodo_actual.hijos[caracter]
    end
    nodo_actual.es_final
  end

  def buscar_prefijo(prefijo)
    nodo_actual = @raiz
    prefijo.each_char do |caracter|
      return false unless nodo_actual.hijos[caracter]

      nodo_actual = nodo_actual.hijos[caracter]
    end
    true
  end
end

Ejemplo de Uso

Veamos cómo usar nuestra implementación del árbol de prefijos. Primero, crearemos una instancia del árbol y luego insertaremos algunas palabras.

arbol = ArbolDePrefijos.new
arbol.insertar("gato")
arbol.insertar("gallina")
arbol.insertar("gallo")
arbol.insertar("gato")

Ahora, probemos a buscar algunas palabras y prefijos:

puts arbol.buscar("gato")      # Salida: true
puts arbol.buscar("gallina")   # Salida: true
puts arbol.buscar("gallo")      # Salida: true
puts arbol.buscar("gatoo")      # Salida: false
puts arbol.buscar_prefijo("ga")  # Salida: true
puts arbol.buscar_prefijo("g")   # Salida: true
puts arbol.buscar_prefijo("x")   # Salida: false

Consideraciones Finales

Los árboles de prefijos son una herramienta poderosa para trabajar con cadenas de texto. Su capacidad para organizar y buscar palabras de manera eficiente los convierte en una opción ideal para aplicaciones que requieren autocompletado, verificación de palabras y búsqueda de prefijos.

En este artículo, hemos cubierto cómo implementar un árbol de prefijos en Ruby, desde la creación de nodos hasta la inserción y búsqueda de palabras. Con esta base, puedes expandir la funcionalidad del árbol de prefijos, como agregar métodos para eliminar palabras o listar todas las palabras almacenadas.

Esperamos que este artículo te haya sido útil y que ahora tengas una mejor comprensión de cómo funcionan los árboles de prefijos y cómo implementarlos en Ruby. ¡Feliz codificación!