Please I don't understand the logic in the add and search method here, can someone help me explain what's going on in these methods, especially in the two while loops inside add(). I encountered this in the book Hands-On Data Structures and Algorithms with JavaScript by Kashyap Mukkamala. Also I want to understand how this implementation is related to a trie tree, possibly suggest a more simpler implementation of this same logic.
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
// i.e. no data found
if (curChar && !currentNode[curChar]) {
return {
remainder: []
};
}
// return the node found
return currentNode;
}
}The main difference with usual trie implementations is the use of remainder here.
For words adam and adx, a common trie would look like
a -> d -> a -> m
| -> x
In this implementation, the trie is also storing the "remaining" word in each node. So when you insert "adx" in an empty tree, it becomes
a (remainder: ["dx"]
|
d (remainder: ["x"]
|
x (remainder: []
|
null
Inserting "adam" in the same tree
a (remainder: ["dx", "dam"])
|
d (remainder: ["x", "am"])
|------------------------|
x (remainder: []) a (remainder: ["m"])
| |
null m (remainder: [])
The search process is trivial though, it just search if the current node has the given character or not, and if it does, it continues the process on the child node iteratively.