字典树的实现和介绍

优化老代码的时候，用到了字典树。我用 Java 写了一个字典树。分享一下。

先说一下常见的引用场景，单词匹配，统计（敏感词检测，单词检测），还有输入提示等等。

下面是代码了
node 节点代码

public class Node{private List<Node> nodeList = new ArrayList<>();
    private char word; // 这里保存的一个字符
    private int isEnd = 0; // 这里是一个结束标识

    public Node(char w){this.word = w;}

    public Node(){}

    public List<Node> getNodeList() {return nodeList;}

    public void setNodeList(List<Node> nodeList) {this.nodeList = nodeList;}

    public char getWord() {return word;}

    public void setWord(char word) {this.word = word;}

    public int getIsEnd() {return isEnd;}

    public void setIsEnd(int isEnd) {this.isEnd = isEnd;}
}

Node 节点重点就是保存的 char 和 isEnd 这个两个属性，这里我保存的是字符串，其实可以保存成 utf8 的编码，防止一些编码问题。
因为是多叉树结构，可能这两个单词 sad，saddy，需要一个结束的标识位。

添加节点代码

    public void addNode(List<Node> nodeList,char[] word){List<Node> temp = new ArrayList<>();
        // 遍历单词
        for (int i=0;i < word.length; i++){
            // 查看子节点
            for (int j = nodeList.size(); j >= 0; j--) {
                // 有子节点并且字相同，则更新 nodeList 并且跳出循环，检查下一个字
                if (j > 0 && nodeList.get(j-1).getWord() == word[i]) {nodeList = nodeList.get(j-1).getNodeList();
                    break;
                // 如果子节点为零，则说明需要添加新节点    
                }else if(j == 0){Node n = new Node(word[i]);
                    // 判断是否达到单词结尾，添加标志位
                    if(nodeList.size() == 0 && (i == word.length -1)){n.setIsEnd(1);
                    }
                    temp = n.getNodeList();
                    nodeList.add(n);
                    //nodeList 赋值给新节点，结束循环
                    nodeList = temp;
                }
            }
        }
    }

这一段需要注意的一点是，我是用了 List 这个数据结构，这个地方可以优化为 Map 结构，Hash 表的时间复杂度是 O(1)。

搜索单词

public boolean searchNode(List<Node> nodeList,char[] word){for (int i=0;i < word.length; i++){for (int j = nodeList.size() - 1; j >= 0; j--) {if (nodeList.get(j).getWord() == word[i]) {
                // 单词处于结尾，和有标志位，则直接返回
                if((i == word.length -1) && nodeList.get(j).getIsEnd() == 1){return true;}
                nodeList = nodeList.get(j).getNodeList();
                break;
            }
        }
    }

    return false;
}

搜索文本

  
public boolean searchText(List<Node> nodeList,char[] word){
    // 记录头节点
    List<Node> head = nodeList;
    for (int i=0;i < word.length; i++){for (int j = nodeList.size() - 1; j >= 0; j--) {if (nodeList.get(j).getWord() == word[i]) {
            // 搜索文本就不要判断单词是否处于结尾了，查到直接就返回结果
                if(nodeList.get(j).getIsEnd() == 1){return true;}
                nodeList = nodeList.get(j).getNodeList();
                break;
            }
            // 当节点没有子节点，并且程序运行到此，将 nodeList 复位到头节点
            if(j == 0){nodeList = head;}
        }
    }
    return false;
}    

处理敏感词部分，或者相似功能应该做分词的处理。如果不做分词处理的，会出现错误，比如玛丽露 A。往后再推一个单词。
我这里是一个字一个字去进行顺序查找的。但是应该有相关的文本搜索算法和字典树相结合。可以提高效率。

我这里实现的是 O（m*n）上面也提到了可以优化到 O（n），但是也比之前快了不少了。比如输入提示，比每一次查询数据库之类的要快很多。如果字典树更新不频繁，比如地名，字典树是可以 json 化，保存到 Redis 中。这样可以给其他语言去使用，而且比一次性查询数据库，之后再结构化，也是要快一点的。

如果还哪里写错了，或者有什么更好的优化建议，欢迎讨论。