三叉Trie树

在一个三叉搜索树（Ternary Search Trie）中，每一个节点包括一个字符，但和数字搜索树不同，三叉搜索树只有三个指针：一个指向左边的树；一个指向右边的树；还有一个向下，指向单词的下一个数据单元。三叉搜索树是二叉搜索树和数字搜索树的混合体。它有和数字搜索树差不多的速度但是和二叉搜索树一样只需要相对较少的内存空间。

树是否平衡取决于单词的读入顺序。如果按排序后的顺序插入，则生成方式最不平衡。单词的读入顺序对于创建平衡的三叉搜索树很重要，但对于二叉搜索树就不太重要。通过选择一个排序后数据单元集合的中间值，并把它作为开始节点，我们可以创建一个平衡的三叉树。可以写一个专门的过程来生成平衡的三叉树词典。

   

/**  
     * 在调用此方法前，先把词典数组k排好序  
     * @param fp 写入的平衡序的词典  
     * @param k 排好序的词典数组  
     * @param offset 偏移量  
     * @param n 长度  
     * @throws Exception  
     */  
    void outputBalanced(BufferedWriter fp,ArrayList<String> k,int offset,   
    int n){  
        int m;  
        if (n < 1) {  
            return;  
        }  
        m = n >> 1; //m=n/2  
          
        String item= k.get(m + offset);  
     
        fp.write(item);//把词条写入到文件  
        fp.write('\n');  
          
        outputBalanced(fp,k,offset, m); //输出左半部分  
        outputBalanced(fp,k, offset + m + 1, n - m - 1); //输出右半部分  
    }

 
取得平衡的单词排序类似于洗扑克牌。假想有若干张扑克牌，每张牌对应一个单词，先把牌排好序，然后取最中间的一张牌，单独放着。剩下的牌分成了两摞，左边一摞牌中也取最中间的一张放在取出来的那张牌后面。右边一摞牌中也取最中间的一张放在取出来的牌后面，以此类推。

我们再次以有序的数据单元（as  at  be  by  he  in  is  it  of  on  or  to）为例。 首先我们把关键字"is"作为中间值并且构建一个包含字母"i"的根节点。它的直接后继节点包含字母"s"并且可以存储任何与"is"有关联的数据。对于"i"的左树，我们选择"be"作为中间值并且创建一个包含字母"b"的节点，字母"b"的直接后继节点包含"e"。该数据存储在"e"节点。对于"i"的右树，按照逻辑，选择"on"作为中间值，并且创建"o"节点以及它的直接后继节点"n"。

TernarySearchTrie本身存储关键字到值的对应关系，可以当做HashMap对象来使用。关键字按照字符拆分成许多节点，以TSTNode的实例存在。值存储在TSTNode的data属性中。TSTNode的实现代码如下所示：
   

public final class TSTNode {  
            /**  节点的值  */  
            public Data data=null;// data属性可以存储
    词原文和词性、词频等相关的信息  
              
            protected TSTNode loNode; //左边节点  
            protected TSTNode eqNode; //中间节点  
            protected TSTNode hiNode; //右边节点  
              
            protected char splitchar; // 本节点表示的字符  
            /**  
             *  构造方法  
             *  
             *@param  splitchar  该节点表示的字符  
             */  
            protected TSTNode(char splitchar) {  
                this.splitchar = splitchar;  
            }  
            public String toString()    {  
                return "splitchar:"+ splitchar;  
            }  
    }

 

查找词典的基本过程是：输入一个词，返回这个词对应的TSTNode对象，如果该词不在词典中则返回空。在查找词典的过程中，从树的根节点匹配Key，按Char从前往后匹配Key。charIndex表示Key当前要比较的Char的位置。匹配过程如下所示：
   

protected TSTNode getNode(String key, TSTNode startNode) {  
            if (key == null ) {  
                return null;  
            }  
            int len = key.length();  
            if (len ==0)  
                return null;  
            TSTNode currentNode = startNode; //匹配过程中当前节点的位置  
            int charIndex = 0;  
            char cmpChar = key.charAt(charIndex);  
            int charComp;  
            while (true) {  
                if (currentNode == null) {//没找到  
                    return null;  
                }  
                charComp = cmpChar - currentNode.splitchar;  
                if (charComp == 0) {//相等  
                    charIndex++;  
                    if (charIndex == len) {//找到了  
                        return currentNode;  
                    }  
                    else {  
                        cmpChar = key.charAt(charIndex);  
                    }  
                    currentNodecurrentNode = currentNode.eqNode;  
                } else if (charComp < 0) {//小于  
                    currentNodecurrentNode = currentNode.loNode;  
                } else {//大于  
                    currentNodecurrentNode = currentNode.hiNode;  
                }  
            }  
    }

 

三叉树的创建过程也就是在Trie树上创建和单词对应的节点。实现代码如下所示：
   

//向词典树中加入一个单词的过程  
    private TSTNode addWord(String key) {  
            TSTNode currentNode = root; //从树的根节点开始查找  
            int charIndex = 0; //从词的开头匹配  
            while (true) {  
                //比较词的当前字符与节点的当前字符  
                int charComp =key.charAt(charIndex) - 
    currentNode.splitchar;   
                if (charComp == 0) {//相等  
                    charIndex++;  
                    if (charIndex == key.length()) {  
                        return currentNode;  
                    }  
                    if (currentNode.eqNode == null) {  
                        currentNode.eqNode = new TSTNode(key.charAt  
                    (charIndex));  
                    }  
                    currentNodecurrentNode = currentNode.eqNode;  
                } else if (charComp < 0) {//小于  
                    if (currentNode.loNode == null) {  
                        currentNode.loNode =    new TSTNode(key.charAt  
                    (charIndex));  
                    }  
                    currentNodecurrentNode = currentNode.loNode;  
                } else {//大于  
                    if (currentNode.hiNode == null) {  
                        currentNode.hiNode =    new TSTNode(key.charAt  
                    (charIndex));  
                    }  
                    currentNodecurrentNode = currentNode.hiNode;  
                }  
            }  
    }

 
相对于查找过程，创建过程在搜索过程中判断出链接的空值后创建相关的节点，而不是碰到空值后结束搜索过程并返回空值。

同一个词可以有不同的词性，例如"朝阳"既可能是一个"区"，也可能是一个"市"。可以把这些和某个词的词性相关的信息放在同一个链表中。这个链表可以存储在TSTNode 的Data属性中。