¿Cómo implementar un método para eliminar en un trie?

Answer

1. 

   davy.ai

   June 11, 2023 at 8:18 am

   Para agregar un método de eliminación a la clase Trie, podemos seguir estos pasos:

   1. Recorrer el Trie para verificar si la cadena a eliminar existe en el Trie o no.
   2. Si la cadena existe, establecer la bandera isWord en falso para el último nodo de la cadena, ya que estamos eliminando un nodo hoja.
   3. Si el TrieNode no tiene otros hijos y no es la raíz, eliminarlo de forma recursiva.
   4. Si cualquier TrieNode intermedio tiene la bandera isWord establecida en verdadero, eso significa que representa una palabra válida, por lo que no podemos eliminarla. Por lo tanto, dejaremos de eliminar en ese TrieNode.

   Aquí está la implementación del método de eliminación:

   public void delete(String s) {
       if (root == null)
           return;
   
       deleteHelper(root, s, 0);
   }
   
   private boolean deleteHelper(TrieNode node, String s, int index) {
       if (index == s.length()) {
           if (!node.isWord)
               return false;
           node.isWord = false;
           return node.children.size() == 0;
       }
   
       char curChar = s.charAt(index);
       TrieNode curNode = node.children.get(curChar);
   
       if (curNode == null)
           return false;
   
       boolean deleteNode = deleteHelper(curNode, s, index + 1);
   
       if (deleteNode) {
           node.children.remove(curChar);
           // Eliminar recursivamente el TrieNode si no tiene otros hijos
           return node.children.size() == 0;
       }
       return false;
   }
   

   El método delete toma una cadena s como parámetro de entrada y recorre recursivamente el Trie para verificar si la cadena s existe en el Trie o no.

   Si se encuentra la cadena s en el Trie, establecemos la bandera isWord del último nodo en falso para indicar que ‘s’ ya no es una palabra válida. Si el TrieNode no tiene otros hijos y no es la raíz, lo eliminamos de forma recursiva.

   Finalmente, devolvemos verdadero si el TrieNode no tiene otros hijos y no es la raíz. Devolvemos falso de lo contrario.

   Nota: También podemos agregar una variable de tamaño a la clase Trie para almacenar el número de palabras en el Trie. Podemos decrementar esta variable de tamaño cuando eliminamos una palabra del Trie.

Comments are closed.