Topic link
The prefix tree
The basic concept
What is a prefix tree?
A prefix tree (Trie), also known as a dictionary tree, is a tree-shaped data structure for efficiently storing and retrieving keys in a string dataset. This data structure has a number of applications, such as auto-completion and spell checking.
A prefix tree is a little bit different from a regular number, requiring a field to indicate whether it’s over or not
Definition of nodes of ordinary trees:
class TreeNode {
val: any;
children: TreeNode[];
}
Copy the code
Prefix tree node definition:
class TreeNode {
isEnd: boolean; // indicates whether this node is the end of a string
children: { [key: string] :any }; // The child is represented by an object, with the current character as the key of the object
}
Copy the code
What does a prefix tree look like?
Suppose you have three strings about, and, and apple built into a prefix tree
That’s how it’s built
Train of thought
Knowing what the prefix tree is, the code is clear to write
- Insert: Declares a pointer
node
, iterate over the string to be inserted to see if the current character exists in the current node. If it does not, create a new node, and then point the pointer to this new node. After traversal, add an attribute to the last node that the pointer points tonode.isEnd = ture
- Search: Iterates through the string to see if each character exists in the prefix tree, returns if it does not
false
, exists and traverses to the end thereisEnd
If the end of the flag is found, returntrue
- Prefix lookup: The process is the same as lookup, but without
isEnd
Logo is ok
code
class Trie {
children: { [key: string] :any };
constructor() {
this.children = {};
}
/** * inserts the current string **/ into the prefix tree
insert(word: string) :void {
let node = this.children;
for (const ch of word) {
if(! node[ch]) { node[ch] = {};// If the character does not exist, create a new node
}
node = node[ch]; // points to the next character
}
node.isEnd = true; // Indicates the end of the current string
}
/** * check whether the prefix tree contains the target string as prefix **/
serachPrefix(word: string): { [key: string] :any } | false {
let node = this.children;
for (const ch of word) {
if(! node[ch]) {return false; // If the current character is not found, return false
}
node = node[ch]; // points to the next character
}
return node; // Returns the node corresponding to the last character of the string
}
/** * See if the prefix tree contains the target string **/
search(word: string) :boolean {
const node = this.serachPrefix(word);
returnnode && !! node.isEnd;// The last node exists and has an end identifier
}
/** * check whether the prefix tree contains the target string as prefix **/
startsWith(prefix: string) :boolean {
return this.serachPrefix(prefix) as boolean; // The last node exists with or without an end flag}}Copy the code