El árbol de Patricia es una estructura de datos muy eficiente, conocida también como Patricia Trie o árbol de radix compacto. Se trata de una variante optimizada de un trie (prefix tree o árbol de prefijos) que comprime las rutas donde no hay bifurcaciones, eliminando nodos con un solo hijo para ahorrar espacio. PATRICIA es un acrónimo de Practical Algorithm To Retrieve Information Coded In Alphanumeric, propuesto por Donald R. Morrison. Originalmente diseñado para búsquedas eficientes en cadenas alfanuméricas.
Características principales
Es un trie de radix variable (generalmente radix 2 en su forma clásica binaria, pero se usa con radix mayor en variantes modernas).
Comprime caminos: Si varios nodos consecutivos tienen solo un hijo, se "colapsan" en un solo nodo que almacena una subcadena más larga (skip o "edge label" con longitud).
Cada nodo interno representa un punto de decisión (bifurcación).
Los nodos hoja (o nodos terminales) almacenan el valor asociado a la clave completa.
Muy eficiente en memoria para conjuntos de cadenas con muchos prefijos compartidos.
Ejemplo
Supongamos insertamos las palabras:
"romano"
"romero"
"rosa"
"ruta"
En un trie normal habría muchos nodos con un solo hijo ("rom" → "a" → "n" → etc.).
En un Patricia Trie se comprimen: Raíz → nodo con "ro" → bifurcación:
"mano" (romano)
"mero" (romero)
"sa" (rosa)
"ta" (ruta)
Usos
Ethereum → Merkle Patricia Trie (MPT) o Modified Merkle Patricia Trie: combina Patricia Trie + Merkle Tree para almacenar el estado de la blockchain (cuentas, saldos, contratos) de forma verificable criptográficamente.
Enrutamiento IP (tablas de ruteo con longest prefix match).
Autocompletado en buscadores y teclados.
Bases de datos de claves (como en algunas implementaciones de Redis o sistemas de archivos).
