前綴樹是什么

前綴樹是一種樹結(jié)構(gòu),其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節(jié)點(diǎn)中，而是由節(jié)點(diǎn)在樹中的位置決定。一個(gè)節(jié)點(diǎn)的所有子孫都有相同的前綴，也就是這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的字符串，而根節(jié)點(diǎn)對(duì)應(yīng)空字符串。一般情況下，不是所有的節(jié)點(diǎn)都有對(duì)應(yīng)的值，只有葉子節(jié)點(diǎn)和部分內(nèi)部節(jié)點(diǎn)所對(duì)應(yīng)的鍵才有相關(guān)的值。

前綴樹基本性質(zhì)

1，根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)意外每個(gè)節(jié)點(diǎn)只包含一個(gè)字符。
2，從根節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。
3，每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符串不相同。
優(yōu)點(diǎn)：
可以最大限度地減少無謂的字符串比較，故可以用于詞頻統(tǒng)計(jì)和大量字符串排序。
跟哈希表比較：
1，最壞情況時(shí)間復(fù)雜度比hash表好
2，沒有沖突，除非一個(gè)key對(duì)應(yīng)多個(gè)值（除key外的其他信息）
3，自帶排序功能（類似Radix Sort），中序遍歷trie可以得到排序。

缺點(diǎn)：
1，雖然不同單詞共享前綴，但其實(shí)trie是一個(gè)以空間換時(shí)間的算法。其每一個(gè)字符都可能包含至多字符集大小數(shù)目的指針（不包含衛(wèi)星數(shù)據(jù)）。
每個(gè)結(jié)點(diǎn)的子樹的根節(jié)點(diǎn)的組織方式有幾種。1>如果默認(rèn)包含所有字符集，則查找速度快但浪費(fèi)空間（特別是靠近樹底部葉子）。2>如果用鏈接法(如左兒子右兄弟)，則節(jié)省空間但查找需順序（部分）遍歷鏈表。3>alphabet reduction: 減少字符寬度以減少字母集個(gè)數(shù)。,4>對(duì)字符集使用bitmap，再配合鏈接法。
2，如果數(shù)據(jù)存儲(chǔ)在外部存儲(chǔ)器等較慢位置，Trie會(huì)較hash速度慢（hash訪問O(1)次外存，Trie訪問O(樹高)）。

如何生成前綴樹

結(jié)點(diǎn)的值由結(jié)點(diǎn)的位置決定,比如該樹是一個(gè)字符串樹.
我們可以定義結(jié)點(diǎn)有一個(gè)長(zhǎng)度為26的結(jié)點(diǎn)數(shù)組,利用字符和'a'的差值
確定字符要存的位置,比如a-'a'=0,則a字符存到root[0]位置,c-'a'=2,那么c存到root[2]位置

前綴樹代碼實(shí)現(xiàn)和測(cè)試:

package com.algorithm.practice.tree;

import org.omg.PortableInterceptor.INACTIVE;

public class CreatTrieTree {
    public static class TrieTree {
        int path;//略過的次數(shù)---有多少字符串包含此結(jié)點(diǎn)到根結(jié)點(diǎn)的所有字符
        int end;//以該結(jié)點(diǎn)為最后一個(gè)字符的字符串
        TrieTree[] nodes;

        public TrieTree() {
            path = 0;
            end = 0;
            nodes = new TrieTree[26];
        }
    }

    public static class Trie {
        private TrieTree root;

        public Trie() {
            root = new TrieTree();
        }

        public void insert(String word) {
            if (word == null || "".equals(word)) {
                return;
            }
            TrieTree node = root;
            int index;
            for (char c : word.toCharArray()//遍歷字符串中的每一個(gè)字符
            ) {
                index = c - 'a';
                if (node.nodes[index] == null) {
                    node.nodes[index] = new TrieTree();
                }
                node = node.nodes[index];
                node.path++;
            }
            node.end++;
        }


public  int search(String str) {
            if (str == null || "".equals(str)) {
                return 0;
            }
            char[] chars = str.toCharArray();
            TrieTree node = root;
            int index;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                if (node.nodes[index] == null) {
                    return 0;
                }
                node = node.nodes[index];
            }
            return node.end;
        }

        public void delete(String str) {
            if (search(str)!=0){ //前綴樹中有才進(jìn)行刪除
             char[]chars=str.toCharArray();
             int index;
             TrieTree node=root;
             for(int i=0;i<chars.length;i++){
                 index=chars[i]-'a';
                 if (--node.nodes[index].path==0){
                     node.nodes[index]=null;
                     return;
                 }
                 node=node.nodes[index];
             }
             node.end--;
            }
        }

        public int preFixNumber(String str){
            if (str==null||"".equals(str)){
                return 0;
            }
            char[] chars=str.toCharArray();
            TrieTree node=root;
            int index;
            for(int i=0;i<chars.length;i++){
                index=chars[i]-'a';
                if (node.nodes[index]==null){
                    return 0;
                }
                node=node.nodes[index];
            }
            return node.path;
        }
    }
    public static void main(String[] args) {
        Trie trie = new Trie();
        System.out.println(trie.search("zuo"));
        trie.insert("zuo");
        System.out.println(trie.search("zuo"));
        trie.delete("zuo");
        System.out.println(trie.search("zuo"));
        trie.insert("zuo");
        trie.insert("zuo");
        trie.delete("zuo");
        System.out.println(trie.search("zuo"));
        trie.delete("zuo");
        System.out.println(trie.search("zuo"));
        trie.insert("zuoa");
        trie.insert("zuoac");
        trie.insert("zuoab");
        trie.insert("zuoad");
        trie.delete("zuoa");
        System.out.println(trie.search("zuoa"));
        System.out.println(trie.preFixNumber("zuo"));

    }
}