概念

单词查找树由字符串键中的所有字符构造而成，允许使用被查找键中的字符进行查找。

与各种查找树一样，单词查找树也是由链接的节点组成，每个节点都只有一个父节点（根结点除外），每个节点有R个子节点，R 为字母表的大小，示例中使用大小为 256 的字母表。我们将每个键所关联的值，保存在该键最后一个字母所在的结点中。

值为空的结点，在字母表中没有对应的键。因为在单词查找树中，并不保存键，仅按照字母在字母表中的索引构造单词查找树。

API

与之前的符号表学习一样，首先需要了解单词查找树的 API，弄清楚需要实现什么样的代码

其中增加了几个不同的 api，假设符号表中有 she，sh，sells，by，sea 这几个键：

longestPrefixOf（）接受一个字符串参数，返回符号表中该字符串前缀中最长的键。longestPrefixOf(“shel”)返回的结果是 she；
keysWithPrefix（）接受一个字符串参数，返回符号表中所有以该字符串为前缀的键。keyWithPrefix(“sh”)返回的结果是 she sh；
keysThatMatch（）接受一个字符串参数，返回符号表中所有与改字符串匹配的键（”.”能够匹配任意字符）。keysThatMatch(“se.”)返回的结果是 sea；

图解

代码实现

查找与插入

查找方法递归地在子树中查找键，期间如果键为空，则查找未命中。

插入方法在查找键的过程中，如果键为空，则插入新建，继续在子树中递归操作。直到查找出对应的键，无论键是否为空，均修改该值。

V get(String key) {
    Node n = get(root, key, 0);
    return n == null ? null : (V) n.val;
}

Node get(Node n, String key, int d) {
    if (n == null) {
        return null;
    }
    if (d == key.length()) {
        return n;
    }
    char c = key.charAt(d);
    return get(n.nodes[c], key, d + 1);
}

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

Node put(Node n, String key, V val, int d) {

    if (n == null) {
        n = new Node();
    }

    if (d == key.length()) {
        n.val = val;
        return n;
    }
    char c = key.charAt(d);
    n.nodes[c] = put(n.nodes[c], key, val, d + 1);
    return n;
}

删除

删除操作稍微复杂一点，再删除之后，检查该结点是否为空节点，如果为空，则删除该结点，再检查该结点的父节点，如果父节点也为空，则删除父节点，依次递归向上。

void delete(String key) {
    root = delete(root, key, 0);
}

Node delete(Node n, String key, int d) {
    if (n == null) {
        return null;
    }
    if (d == key.length()) {
        n.val = null;
    } else {
        char c = key.charAt(d);
        n.nodes[c] = delete(n.nodes[c], key, d + 1);
    }

    if (n.val != null) {
        return n;
    }
    for (Node node : n.nodes) {
        if (node != null) {
            return n;
        }
    }
    return null;
}

遍历所有键

由于在单词查找树中，并未显式地储存键，所以要得到所有键的集合有点麻烦。解决思路是使用队列来收集键，在方法中传入一个节点（可以理解为一颗子树），前缀（该结点以上的所有字符按顺序拼接），以及一个用于存储键的队列（队列使用《算法》中提供的数据结构，代码见下文）。该方法递归地在每一颗子树中收取符合条件的键。

keys（）方法起始前缀为 “ ”，因为包含所有键；keysWithPrefix（）方法会先查找符合前缀条件的结点（子树），再使用 collect（）收集。

Iterable<String> keys() {
    return keysWithPrefix("");
}

Iterable<String> keysWithPrefix(String pre) {
    Queue<String> q = new Queue<>();
    collect(get(root, pre, 0), pre, q);
    return q;
}

void collect(Node n, String pre, Queue<String> queue) {
    if (n == null) {
        return;
    }
    if (n.val != null) {
        queue.enqueue(pre);
    }
    for (char c = 0; c < R; c++) {
        collect(n.nodes[c], pre + c, queue);
    }
}

字符串匹配

需要注意的是，“.” 表示所有字符，因此，在遍历时，如果遇到 “.”，需要遍历所有子树，而如果是特定字符，只需遍历该字符的子树。

Iterable<String> keysThatMatch(String pat) {
    Queue<String> q = new Queue<>();
    collect(root, "", pat, q);
    return q;
}

void collect(Node n, String pre, String pat, Queue<String> queue) {
    if (n == null) {
        return;
    }
    if (n.val != null) {
        queue.enqueue(pre);
    }
    int d = pre.length();
    if (d == pat.length()) {
        return;
    }
    char c = pat.charAt(d);
    if (c == '.') {
        for (char i = 0; i < R; i++) {
            collect(n.nodes[i], pre + i, pat, queue);
        }
    } else {
        collect(n.nodes[c], pre + c, pat, queue);
    }

}

最长前缀

这里使用一个 search（）方法去查找最长字符串索引

String longestPrefix(String s) {
    int index = search(root, s, 0, 0);
    return s.substring(0, index);
}

int search(Node n, String s, int d, int length) {
    if (n == null) {
        return length;
    }
    if (n.val != null) {
        length = d;
    }
    if (d == s.length()) {
        return length;
    }
    return search(n.nodes[s.charAt(d)], s, d + 1, length);
}

完整代码参考

参考文档

《算法》