【数据结构】Trie树

数据结构——Trie树

概念

Trie树，又称字典树、前缀树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

Trie树的结构如下图所示：

Trie树中的节点数据结构如下：

• 当前字符
• 子节点数组（如果全为小写字母的话，子节点数量固定为26个，根据字符来确定在数组中的位置，如'a'的下标为0，'z'为25）
• 是否为一个单词的结尾（标红的节点）
• 出现次数

特点：root节点不存储字符。

代码实现

public class Trie {
    private Node root;
    class Node{
        int count;
        char ch;
        Node[] child;
        boolean isEnd;

        public Node() {
            this.count = 1;
            this.child = new Node[26];
            this.isEnd = false;
        }
    }


    /** Initialize your data structure here. */
    public Trie() {
        this.root = new Node();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        if (null == word || "".equals(word)) return;
        if (this.search(word)) return;

        Node cur = this.root;
        char[] chars = word.toCharArray();
        for(char c : chars) {
        	//根据字符找到在子节点数组中的下标
            int pos = c - 'a';
            Node child = cur.child[pos];
            //如果子节点没有被初始化过则初始化，并设置其字符
            if (child == null) {
                cur.child[pos] = new Node();
                cur.child[pos].ch = c;
            }
            cur.count++;
            //更新cur节点为子节点，向下递归
            cur = cur.child[pos];
        }

        //最后一个字符的节点
        cur.isEnd = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        if (null == word || "".equals(word)) return true;
        Node cur = this.root;
        char[] chars = word.toCharArray();
        for (char c : chars) {
            int pos = c - 'a';

            Node node = cur.child[pos];
            if (node == null) return false;

            cur = node;
        }
        return cur.isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        if (null == prefix || "".equals(prefix)) return true;
        Node cur = this.root;
        char[] chars = prefix.toCharArray();
        for (char c : chars) {
            int pos = c - 'a';
            Node node = cur.child[pos];
            if (node == null) return false;
            cur = node;
        }

        return cur.count > 0;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();

        trie.insert("a");
        trie.insert("adc");
        trie.insert("aer");

        System.out.println(trie.search("a"));
        System.out.println(trie.startsWith("a"));
    }
}

结果：

208. Implement Trie (Prefix Tree)

超过94%，感觉还不错~