Trie字典树(前缀树)

对字典树的理解:

a.Trie字典树又可以称为前缀树,是一种真正为字典设计的数据结构,其中的核心实现就包含了字典Map.
b.Trie专门用来处理字符串相关的问题,运行十分高效.其运算时的复杂度跟树的规模无关,只跟用于操作的目标字符串W的长度L相关,即O(L).鉴于大部分的字符串长度一般都较短(10+的很少)即字典树相对其他结构有着明显更低的时间复杂度-->例如:一个100w规模的条目,即使使用树结构,时间复杂度为logn级别,基本上为20,对比得到,在较大规模的数据背景下可以看出Trie字典树的优势.
c.Trie树的结构如图1

图1 Trie树的结构原理

从结构图中可以看出(1).Trie树结构是由一个一个节点构成
(2).每个节点代表的是一个对应的字符
(3).每个节点上都挂载有子节点.

设计代码:

设计思路:

从Trie树的结构上看,Trie也是一个一个节点node相互挂接而成,并且每个节点都包含相应的变量var信息.到这里,可以发现Trie和链表LinkedList似乎是完全一样.但进一步读图可以发现--->①Trie树并非是二叉树,而是多叉树,并且不同的父亲节点带子节点的数量也是不定的,链表的父子节点则是一一链接的.②节点表达的信息是字符,每个节点Node和字符Chararter一一对应.
综上所述的思路,可以将Trie设计为以Node节点为基本单元的数据结构,节点之间相互链接,节点相互多链接的属性体现为节点挂载节点集合,又由于节点的字符和节点本身是一一对应,那么集合选择为字典Map.

class Node{
                 public boolean isWord;
        public TreeMap<Character,Node> next;        
}

核心代码实现:

/**
 * class Trie
 * @author Administrator
 *
 */
import java.util.TreeMap;
public class Trie {
    /**
     * aim class --> connect each other
     * @author Administrator
     *
     */
    private class Node{
        public boolean isWord;
        // the TreeMap support generic
        public TreeMap<Character,Node> next;
        
        public Node(boolean isWord) {
            this.isWord = isWord;
            next = new TreeMap<>();
        }
        
        public Node() {
            this(false);
        }
    }
    private int size;
    private Node root;
    
    /**
     * constructor
     */
    public Trie() {
        size = 0;
        root = new Node();
    }
    
    public int getSize() {
        return size;
    }
    
    /**
     * add method-->add a new word into Trie tree
     * @param word
     */
    public void add(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c= word.charAt(i);
            if (cur.next.get(c) == null) {
                cur.next.put(c, new Node());
            }
            cur = cur.next.get(c);
        }
        
        if (!cur.isWord) {
            cur.isWord = true;
            size++;
        }   
    }
    
    /**
     * method contains --> determine whether the target String if in the Trie
     * @param word
     * @return
     */
    public boolean contains(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.next.get(c)==null) {
                return false;
            }
            cur = cur.next.get(c);
        }
        if (!cur.isWord) {
            cur.isWord = true;
        }
        return true;
    }
    
    public boolean isPrefix(String prefix) {
        Node cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (cur.next.get(c) == null) {
                return false;               
            }
            else {
                cur = cur.next.get(c);
            }
        }
        /**
         * determine if there are any words after the prefix
         */
        if (cur.next.keySet()!=null) {
            return true;    
        }
        else
            return false;
    }
}

最后编辑于：2019.03.12 14:01:20