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 pointernode, 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 notfalse, exists and traverses to the end thereisEndIf the end of the flag is found, returntrue
  • Prefix lookup: The process is the same as lookup, but withoutisEndLogo 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