Por favor, no entiendo la lógica en el método de agregar y buscar aquí, ¿alguien puede ayudarme a explicar qué sucede en estos métodos, especialmente en los dos ciclos while dentro de add() ? Encontré esto en el libro Hands-On Data Structures and Algorithms with JavaScript de Kashyap Mukkamala . También quiero entender cómo se relaciona esta implementación con un árbol trie, posiblemente sugiera una implementación más simple de esta misma lógica.
export class Trie { tree: any = {}; constructor() {} add(input) { // set to root of tree var currentNode = this.tree; // init value var nextNode = null; // take 1st char and trim input var curChar = input.slice(0,1); input = input.slice(1); // find first new character, until then keep triming input while(currentNode[curChar] && curChar){ currentNode = currentNode[curChar]; // update remainder array, this will exist as we added the node earlier currentNode.remainder.push(input); // trim input curChar = input.slice(0,1); input = input.slice(1); } // while next character is available keep adding new branches and prune till end while(curChar) { // new reference in each loop // create remainder array starting with current input // so when adding the node `a` we add to the remainder `dam` and so on nextNode = { remainder: [input] }; // assign to current tree node currentNode[curChar] = nextNode; // hold reference for next loop currentNode = nextNode; // prepare for next iteration curChar = input.slice(0,1); input = input.slice(1); } } search(input) { // get the whole tree var currentNode = this.tree; var curChar = input.slice(0,1); // take first character input = input.slice(1); // keep extracting the subtree based on the current character while(currentNode[curChar] && curChar){ currentNode = currentNode[curChar]; curChar = input.slice(0,1); input = input.slice(1); } // reached the end and no subtree found // ie no data found if (curChar && !currentNode[curChar]) { return { remainder: [] }; } // return the node found return currentNode; } }La principal diferencia con las implementaciones habituales de trie es el uso del remainder aquí.
Para las palabras adam y adx , un trie común se vería así
a -> d -> a -> m | -> x En esta implementación, el trie también almacena la palabra "restante" en cada nodo. Entonces, cuando inserta "adx" en un árbol vacío, se convierte en
a (remainder: ["dx"] | d (remainder: ["x"] | x (remainder: [] | null Insertando "adam" en el mismo árbol
a (remainder: ["dx", "dam"]) | d (remainder: ["x", "am"]) |------------------------| x (remainder: []) a (remainder: ["m"]) | | null m (remainder: [])Sin embargo, el proceso de búsqueda es trivial, solo busca si el nodo actual tiene el carácter dado o no, y si lo tiene, continúa el proceso en el nodo secundario de forma iterativa.