Trie tree Java template

$Trie$ 树

Welcome to follow my official account ACJavaBear for more exciting content

1. What is
$Trie$ 树

TrieTrieTrie trees, also known as prefix trees or dictionary trees, are used to count and store large numbers of strings.

It has the advantage of reducing query time and minimizing unnecessary string comparisons by using a common prefix for strings.

In short, a TrieTrieTrie tree is a collection of strings used to store and find them.

2.
$Trie$The structure of the tree

The picture is from Baidu Baike.

(1) Root node root

(2) TrieNode child node

• Is this object the end character of a stringisEnd.trueYes, otherwise no
• An array of sons of the nodeTrieNode[] sonIs used to store the son of the node
• The number of occurrences of a string ending in the current nodenum
• Value of the current nodeval(Sometimes not at all)

(3) Several common operations of TrieTrieTrie tree

• insert
• The query

3. How to write a tree in code
$Trie$ 树

Take the TrieTrieTrie tree that stores strings made up of lowercase letters.

(1) Create a class named TrieTrieTrie

(2) attributes

• Root TrieNode root

• Common node TrieNode

  • attribute
    • boolean isEnd
    • TrieNode[] son
    • int num
  • A constructor

  public TrieNode(a){
      isEnd = false;
      son = new TrieNode[26];
      num = 0;
  }
  Copy the code

(3) Construction method

public Trie(a){
    root = new TrieNode();
} 
Copy the code

(4) Basic operations

• Insert a string

public void insert(String word){
    char[] w = word.toCharArray();
    TrieNode p = root;
    for(char c : w){
        // map 'a'~'z' to 0~25
        int u = c - 'a';
        if(p.son[u] == null) p.son[u] = new TrieNode();// No child node, create child node
        p = p.son[u];// to the child node
    }
    p.isEnd = true;// The string ending in the current node is marked true
    p.num++;// The number of occurrences is increased by one
}
Copy the code

• How many times does a query for a string occur in the collection

public int query(String word){
    char[] w = word.toCharArray();
    TrieNode p = root;
    for(char c : w){
        int u = c - 'a';
        if(p.son[u] == null) return 0;// If there is no object, return 0
        p = p.son[u];
    }
    if(p.isEnd == true) return p.num;// Returns the number of occurrences
    return 0;
}
Copy the code

Specific code

public static class Trie{
    public TrieNode root;
    public Trie(a){
        root = new TrieNode();
    } 
    public class TrieNode{
        boolean isEnd;
        TrieNode[] son;
        int num;
        public TrieNode(a){
            isEnd = false;
            son = new TrieNode[26];
            num = 0; }}public void insert(String word){
        char[] w = word.toCharArray();
        TrieNode p = root;
        for(char c : w){
            int u = c - 'a';
            if(p.son[u] == null) p.son[u] = new TrieNode();
            p = p.son[u];
        }
        p.isEnd = true;
        p.num++;
    }
    public int query(String word){
        char[] w = word.toCharArray();
        TrieNode p = root;
        for(char c : w){
            int u = c - 'a';
            if(p.son[u] == null) return 0;
            p = p.son[u];
        }
        if(p.isEnd == true) return p.num;
        return 0;
    }
Copy the code

Exercises of 4.

$LeetCode 208. Implement Trie (prefix tree)$

Leetcode-cn.com/problems/im…

Answer key is as follows

class Trie {

    TrieNode root; / / the root node
    class TrieNode{// Common node class
        boolean isEnd;
        TrieNode[] son;
        public TrieNode(a){
            isEnd = false;
            son = new TrieNode[26]; }}/** Initialize your data structure here. */
    public Trie(a) {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        if(word ! =null&& word.length() ! =0) {char[] w = word.toCharArray();
            TrieNode p = root;
            for(char c : w){
                int u  = c - 'a';
                if(p.son[u] == null) p.son[u] = new TrieNode();
                p = p.son[u];
            }
            p.isEnd = true; }}/** Returns if the word is in the trie. */
    public boolean search(String word) {
        if(word == null || word.length() == 0) return false;
        TrieNode p = root;
        char[] w = word.toCharArray();
        for(char c : w){
            int  u = c - 'a';
            if(p.son[u] == null) return false;
            p = p.son[u];
        }
        if(p.isEnd) return true;
        return false;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String word) {
        if(word.length() == 0 || word == null) return false;
        TrieNode p = root;
        char[] w = word.toCharArray();
        for(char c : w){
            int u = c-'a';
            if(p.son[u] == null) return false;
            p = p.son[u];
        }
        return true; }}/** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); * /
Copy the code