java 单词查找树

单词查找树的结点有两个域，一个是字符串键对应的值，字符串的最后一个字符所在的结点才有值，其他结点的值都为空；另一个域指向下一个结点，这里实际上是大小为R的结点数组，每个数组中保存着若干字符，其余位置都是空的。

根结点没有存放任何字符，每个结点都包含下一个可能出现的所有字符的链接。从根结点开始首先经过了键的首字母所对应的链接，如此这般沿着结点不断前进，直到到达键的最后一个字符或是遇到一条空链接。这时可能出现以下三种情况：

键的尾字符所对应的结点中的值非空，这是一次命中的查找——键所对应的值就是键的尾字符对应结点中保存的值。如下图中对shells和she的查找
键的尾字符对应的结点中的值为空，这是次未命中的查找。如下图对shell的查找。
查找结束于一条空链接，这是次未命中的查找。如下图对shore的查找。

java 单词查找树

单词查找树的插入和二叉查找树一样，在插入之前要先进行一次查找。有两种情况：

在到达键的尾字符之前就遇到一条空链接。此时需要为键中还未被检查的每个字符创建一个对应的结点，并将值存放到最后一个字符的结点中；比如下图中饭shells和shore的插入就属于这种情况。
在遇到空链接之前就已经到达键的尾字符。此时需要将该结点的值设置为键所对应的值。下图中第二次插入sea就属于这种情况。

java 单词查找树

package Tu;

public class TriST {
    private static int R = 256;
    private Node root;

    private static class Node {
        private int val;
        private Node[] next = new Node[R];
    }

    public int get(String key) {
        Node x = get(root, key, 0);
        if (x == null) {
            return -1;
        }
        return x.val;
    }

    private Node get(Node x, String key, int d) {
        if (x == null) {
            return null;
        }
        // d记录了单词查找树的层数, 假设定义在根结点root时为0（树的层数一般定义是根结点处是第一层）。
        // root没有保存字符，所以d = 1表示字符串的第0个字符d = key.length表示字符串最后一个字符key.length - 1
        if (d == key.length()) {
            return x;
        }
        char c = key.charAt(d);//找到第d个字符对应的子单词查找树
        return get(x.next[c], key, d + 1);
    }

    public void put(String key, int val) {
        root = put(root, key, val, 0);
    }

    private Node put(Node x, String key, int val, int d) {
        // 为每个未检查的字符新建一个结点
        if (x == null) {
            x = new Node();
        }
        // 并将值保存在最后一个字符中
        if (d == key.length()) {
            x.val = val;
            return x;
        }
        char c = key.charAt(d);
        x.next[c] = put(x.next[c], key, val, d + 1);
        return x;
    }

    public static void main(String[] args) {
        chazhaoTree<Integer> trieST = new chazhaoTree<>();
        trieST.put("she", 0);
        trieST.put("sells", 1);
        trieST.put("sea", 2);
        trieST.put("shells", 3);
        trieST.put("by", 4);
        trieST.put("the", 5);
        trieST.put("sea", 6);
        trieST.put("shore", 7);
        System.out.println(trieST.keys());
        System.out.println(trieST.get("sea"));
        System.out.println(trieST.get("she"));
        System.out.println(trieST.get("shells"));

    }
}

秒客网

java 单词查找树

相关文章