ÁRBOL RADIX: QUÉ ES Y CÓMO FUNCIONA

Un árbol radix, también llamado radix tree, compact prefix tree o trie comprimido. Es una estructura de datos muy usada en programación, especialmente para diccionarios, autocompletado, enrutamiento IP, bases de datos de claves, etc.

¿Qué es un árbol radix?

Un árbol radix es una versión optimizada y comprimida de un árbol de prefijos, o trie. La idea principal es que fusiona (comprime) los nodos que tienen un solo hijo, para ahorrar memoria y reducir la profundidad del árbol. En un trie normal: Cada carácter (o bit) ocupa un nodo separado → puede ser muy profundo y gastar mucha memoria si hay prefijos largos compartidos.
En un radix tree:
  • Cada arista puede representar varios caracteres (o varios bits) a la vez.
  • Si un camino es único (un solo hijo), se "aplana" y se pone todo en una sola arista.
  • El "radix" (base) suele ser una potencia de 2 (por ejemplo radix 256 para bytes, radix 16 para nibbles, radix 4 para 2 bits, etc.).

Ventajas principales

  • Búsquedas, inserciones y eliminaciones muy rápidas (O(k) donde k es la longitud de la clave).
  • Mucho más eficiente en memoria que un trie normal.
  • Ideal para claves con muchos prefijos comunes (palabras, rutas de URLs, direcciones IP, etc.).
En el siguiente ejemplo se insertan las palabras:
  • "casa"
  • "caso"
  • "cama"
  • "perro"
En un trie normal tendrías muchos nodos individuales para cada letra. En un radix tree se vería más o menos así (representación simplificada):

raíz
├── "ca" ──► nodo
│  ├── "sa" → (fin: "casa")
│  └── "so" → (fin: "caso")
└── "cama" → (fin: "cama")
└── "perro" → (fin: "perro")
Usos comunes:
  • Autocompletado en buscadores y teclados (como Google o WhatsApp)
  • Enrutamiento en redes (lookup de IPs).
  • Bases de datos clave-valor (Redis usa algo similar en algunos casos).
  • Almacenar rutas en servidores web (Fastify, Fiber, etc.).
  • Linux kernel usa radix trees para mapear páginas, etc.