La estructura de datos de Trie en Java

Programación

1. Informació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.

2. Prueba

Un trie es una estructura de datos discreta que no es muy conocida ni se menciona ampliamente en los cursos típicos de algoritmos, pero sin embargo es importante.

Un trie (también conocido como árbol digital) y, a veces, incluso árbol de radix o árbol de prefijos (ya que se pueden buscar por prefijos), es una estructura de árbol ordenada, que aprovecha las claves que almacena, generalmente cadenas.

La posición de un nodo en el árbol define la clave con la que ese nodo está asociado, lo que hace que los intentos sean diferentes en comparación con los árboles de búsqueda binaria, en los que un nodo almacena una clave que corresponde solo a ese nodo.

Todos los descendientes de un nodo tienen un prefijo común de una Cadena asociada con ese nodo, mientras que la raíz está asociada con una Cadena vacía .

Aquí tenemos una vista previa de TrieNode que usaremos en nuestra implementación de Trie:

public class TrieNode { private HashMap 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, estos son diferentes. Tanto los árboles de búsqueda binaria como los intentos son árboles, pero cada nodo en los árboles de búsqueda binaria siempre tiene dos hijos, mientras que los nodos de intentos, por otro lado, pueden tener más.

En un trie, cada nodo (excepto el nodo raíz) almacena un carácter o un dígito. Al atravesar el trie desde el nodo raíz hasta un nodo n particular , se puede formar un prefijo común de caracteres o dígitos que también es compartido por otras ramas del trie.

Al atravesar el trie 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; //... }

3. Operaciones comunes

Ahora, veamos cómo implementar operaciones básicas.

3.1. Insertar elementos

La primera operación que describiremos es la inserción de nuevos nodos.

Antes de comenzar la implementación, es importante comprender el algoritmo:

  1. Establecer un nodo actual como nodo raíz
  2. Establecer la letra actual como la primera letra de la palabra
  3. Si el nodo actual ya tiene una referencia existente a la letra actual (a través de uno de los elementos en el campo "hijos"), entonces establezca el nodo actual en ese nodo referenciado. De lo contrario, cree un nuevo nodo, establezca la letra igual a la letra actual y también inicialice el nodo actual a este nuevo nodo
  4. Repita el paso 3 hasta que se atraviese la llave

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 usar 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 probar que trie ya se ha poblado con nuevos nodos de la siguiente prueba:

@Test public void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty()); }

3.2. Encontrar elementos

Agreguemos ahora un método para verificar si un elemento en particular ya está presente en un trie:

  1. Consigue hijos de la raíz
  2. Iterar a través de cada carácter de la Cadena
  3. Comprueba si ese personaje ya forma parte de un sub-trío. Si no está presente en ninguna parte del ensayo, detenga la búsqueda y devuelva falso
  4. Repita 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 verdadero

La complejidad de este algoritmo es O (n) , donde n representa la longitud de la clave.

La implementación de Java puede verse así:

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:

@Test public void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life")); }

3.3. Eliminar un elemento

Aparte de insertar y encontrar un elemento, es obvio que también necesitamos poder eliminar elementos.

Para el proceso de eliminación, debemos seguir los pasos:

  1. Comprueba si este elemento ya forma parte del trie.
  2. Si se encuentra el elemento, quítelo del trie.

La complejidad de este algoritmo es O (n) , donde n representa la longitud de la clave.

Echemos un vistazo rápido a 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:

@Test void whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming")); }

4. Conclusión

En este artículo, hemos visto una breve introducción a la estructura de datos de prueba y sus operaciones más comunes y su implementación.

El código fuente completo de los ejemplos que se muestran en este artículo se puede encontrar en GitHub.