Descripción general
Las estructuras de datos representan un activo crucial en la programación de computadoras, y saber cuándo y por qué usarlas es muy importante.
Este artículo es una breve introducción a la estructura de datos Trie (pronunciado «try»), su implementación y análisis de complejidad.
Trie
Una trie es una estructura de datos discreta que no es muy conocida o ampliamente mencionada en los típicos cursos de algoritmos, pero que sin embargo es importante.
Una trie (también conocida como árbol digital) y a veces incluso árbol radix o árbol prefijo (ya que se pueden buscar por prefijos), es una estructura de árbol ordenada, que aprovecha las claves que almacena – normalmente cadenas.
La posición de un nodo en el árbol define la clave con la que se asocia ese nodo, lo que hace que los tries sean diferentes en comparación con los árboles de búsqueda binarios, en los que un nodo almacena una clave que sólo corresponde a ese nodo.
Todos los descendientes de un nodo tienen un prefijo común de una Cadena asociada a ese nodo, mientras que la raíz está asociada a una Cadena vacía.
Aquí tenemos una vista previa del TrieNode que utilizaremos en nuestra implementación del Trie:
public class TrieNode { private HashMap<Character, TrieNode> children; private String content; private boolean isWord; // ...}Puede haber casos en los que un trie sea un árbol de búsqueda binario, pero en general, son diferentes. Tanto los árboles de búsqueda binaria como los tries son árboles, pero cada nodo de los árboles de búsqueda binaria siempre tiene dos hijos, mientras que los nodos de los tries, en cambio, pueden tener más.
En un trie, cada nodo (excepto el nodo raíz) almacena un carácter o un dígito. Atravesando el trie hacia abajo desde el nodo raíz hasta un nodo n en particular, se puede formar un prefijo común de caracteres o dígitos que es compartido por otras ramas del trie también.
Atravesando el trie hacia arriba desde un nodo hoja hasta el nodo raíz, se puede formar una Cadena o una secuencia de dígitos.
Aquí está la clase Trie, que representa una implementación de la estructura de datos trie:
public class Trie { private TrieNode root; //...}Operaciones comunes
Ahora, veamos cómo implementar las operaciones básicas.
3.1. Inserción de elementos
La primera operación que describiremos es la inserción de nuevos nodos.
Antes de comenzar la implementación, es importante entender el algoritmo:
- Establezca un nodo actual como nodo raíz
- Establezca la letra actual como la primera letra de la palabra
- Si el nodo actual ya tiene una referencia a la letra actual (a través de uno de los elementos del campo «hijos»), entonces establezca el nodo actual a ese nodo referenciado. De lo contrario, crea un nuevo nodo, establece la letra igual a la letra actual, y también inicializa el nodo actual a este nuevo nodo
- Repite el paso 3 hasta que la clave sea atravesada
La complejidad de esta operación es O(n), donde n representa el tamaño de la clave.
Aquí está la implementación de este algoritmo:
public void insert(String word) { TrieNode current = root; for (char l: word.toCharArray()) { current = current.getChildren().computeIfAbsent(l, c -> new TrieNode()); } current.setEndOfWord(true);}Ahora veamos cómo podemos utilizar este método para insertar nuevos elementos en un trie:
private Trie createExampleTrie() { Trie trie = new Trie(); trie.insert("Programming"); trie.insert("is"); trie.insert("a"); trie.insert("way"); trie.insert("of"); trie.insert("life"); return trie;}Podemos comprobar que el trie ya ha sido poblado con nuevos nodos a partir de la siguiente prueba:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty());}3.2. Encontrar elementos
Añadamos ahora un método para comprobar si un elemento concreto ya está presente en un trie:
- Obtener hijos de la raíz
- Iterar por cada carácter de la Cadena
- Comprobar si ese carácter ya forma parte de un sub-trie. Si no está presente en ninguna parte de la triada, entonces se detiene la búsqueda y se devuelve false
- Repite el segundo y el tercer paso hasta que no quede ningún carácter en la Cadena. Si se alcanza el final de la Cadena, devuelve true
La complejidad de este algoritmo es O(n), donde n representa la longitud de la clave.
La implementación en Java puede ser como:
public boolean find(String word) { TrieNode current = root; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); TrieNode node = current.getChildren().get(ch); if (node == null) { return false; } current = node; } return current.isEndOfWord();}Y en acción:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life"));}3.3. Borrar un elemento
Además de insertar y encontrar un elemento, es obvio que también necesitamos poder borrar elementos.
Para el proceso de borrado, necesitamos seguir los pasos:
- Comprobar si este elemento ya forma parte del trie
- Si el elemento se encuentra, entonces eliminarlo del trie
La complejidad de este algoritmo es O(n), donde n representa la longitud de la clave.
Veamos rápidamente la implementación:
public void delete(String word) { delete(root, word, 0);}private boolean delete(TrieNode current, String word, int index) { if (index == word.length()) { if (!current.isEndOfWord()) { return false; } current.setEndOfWord(false); return current.getChildren().isEmpty(); } char ch = word.charAt(index); TrieNode node = current.getChildren().get(ch); if (node == null) { return false; } boolean shouldDeleteCurrentNode = delete(node, word, index + 1) && !node.isEndOfWord(); if (shouldDeleteCurrentNode) { current.getChildren().remove(ch); return current.getChildren().isEmpty(); } return false;}Y en acción:
@Testvoid whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming"));}Conclusión
En este artículo, hemos visto una breve introducción a la estructura de datos trie y sus operaciones más comunes y su implementación.