算法(第4版) Chapter 5.2 单词查找树

Algorithms Fourth Edition
Written By Robert Sedgewick & Kevin Wayne
Translated By 谢路云
Chapter 5 Section 2 单词查找树


  • 查找所需要的单词的时间和键的长度成正比

  • 查找未命中只需检查若干个单词

单词查找树

单词查找树API

算法(第4版) Chapter 5.2 单词查找树

基本性质

算法(第4版) Chapter 5.2 单词查找树

  • 每个链接对应一个字符

  • 每个结点可能有一个值

    • 有值,说明存在从根结点到这个结点的字符串。

    • 没有值,说明不存在从根结点到这个结点的字符串。没有对应的键值。它的存在是为了简化查询。

算法(第4版) Chapter 5.2 单词查找树

  • 查找

    • 命中: 对应结点有值(注意不单单是指向该对应结点d链接存在,并且该结点一定要有值!)

    • 未命中: 没有值 or 链接为空

算法(第4版) Chapter 5.2 单词查找树

  • 结点的表示

    • 每个结点下面有R个链接,一个链接对应一个字符

    • 键隐式地保存在结点里

TrieST 代码

public class TrieST<Value> {
    private static int R = 256; // radix
    private Node root; // root of trie

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

    public Value get(String key) {
        Node x = get(root, key, 0);
        if (x == null)
            return null;
        return (Value) x.val;
    }
    
    // Return value associated with key in the subtrie rooted at x.
    private Node get(Node x, String key, int d) { 
        if (x == null)
            return null;
        if (d == key.length())
            return x;
        char c = key.charAt(d); // Use dth key char to identify subtrie.
        return get(x.next[c], key, d + 1);
    }

    public void put(String key, Value val) {
        root = put(root, key, val, 0);
    }
    
    // Change value associated with key if in subtrie rooted at x.
    private Node put(Node x, String key, Value val, int d) { //神一般的递归思想
        if (x == null)
            x = new Node();
        if (d == key.length()) {
            x.val = val;
            return x;
        }
        char c = key.charAt(d); // Use dth key char to identify subtrie.
        x.next[c] = put(x.next[c], key, val, d + 1); //神来之笔
        return x;
    }

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

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

    private void collect(Node x, String pre, Queue<String> q) {
        if (x == null)
            return;
        if (x.val != null)
            q.enqueue(pre);
        for (char c = 0; c < R; c++) //这个效率简直了。。。烂到爆炸
            collect(x.next[c], pre + c, q);
    }
}
  • 方法keys:返回一个Queue,里面有所有的字符串

  • 方法keysWithPrefix(String pre):返回一个Queue,里面有所有以给定字符串pre开头的所有字符串

  • 方法collect:递归用

通配符匹配

  • 结构差异

    • 不含通配符的结构。keysWithPrefix(); get(); collect();

    • 含通配符的结构。keysWithPrefix(); collect();

  • 为什么结构和之前不一样呢?因为get方法要重写。直接把重写的get方法归并进collect方法里去了。

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

    public void collect(Node x, String pre, String pat, Queue<String> q) {
        int d = pre.length(); 
        // begin修改于原get方法()和collect方法()
        if (x == null) // get&collect
            return;
        if (d == pat.length() && x.val != null) // 前collect,后get
            q.enqueue(pre);
        if (d == pat.length())// get
            return; 
        // end 修改于原get方法()和collect方法()
        
        char next = pat.charAt(d);
        for (char c = 0; c < R; c++)
            if (next == '.' || next == c) //如果next=='.' 就要遍历接在当前字符后面的所有字符!!!
                collect(x.next[c], pre + c, pat, q); //还是神一般的递归想法
    }
private Node get(Node x, String key, int d) { 
        if (x == null)
            return null;
        if (d == key.length())
            return x;
        char c = key.charAt(d); // Use dth key char to identify subtrie.
        return get(x.next[c], key, d + 1);
    }

最长前缀

public String longestPrefixOf(String s) {
        int length = search(root, s, 0, 0);
        return s.substring(0, length);
    }

    //当前搜索的是第d位字符,返回的是具有最长length位前缀的子字符
    private int search(Node x, String s, int d, int length) {
        if (x == null) // 查到单词树的尽头了
            return length;
        if (x.val != null) // 如果存在这个单词,就更新length值
            length = d;
        if (d == s.length()) // 查到字符串的尽头了(一定要先做上一步)
            return length;
        char c = s.charAt(d);
        return search(x.next[c], s, d + 1, length); //递归搜索下一位
    }

删除操作

  • 依旧是神一般的递归思路

  • 如果它的链接不为空

    • 删去这个结点的即可

  • 如果它的所有链接都为空

    • 删去这个结点

    • 检查这个结点的父结点的所有链接是否为空

      • 不为空,结束

      • 为空,删去父结点并检查父结点的父结点是否为空
        ……循环如此

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

    private Node delete(Node x, String key, int d) {
        if (x == null)
            return null;
        if (d == key.length()) //找到了的话就将该结点的值删去
            x.val = null;
        else {
            char c = key.charAt(d);
            x.next[c] = delete(x.next[c], key, d + 1); //依旧是神一般的递归思路
        }
        if (x.val != null) //如果该结点有值,则不管当前结点链接是否为空,该结点都在树里,不能被删去。
            return x;
        for (char c = 0; c < R; c++) //否则就看该结点链接是否为空(即该结点没有值)
            if (x.next[c] != null) //如果当前结点链接不为空,则返回当前结点
                return x; 
        return null; //否则返回为空。(因为是返回上一层递归, 即把自己置为空,也即删除了自己)
    }

复杂度

字母表大小为R,N个随机键组成的单词查找树中

  • 时间:

    • 查找和插入最差时间为:键的长度+1

    • 查找未命中的平均时间为:logRN (查找未命中的时间和键的长度无关
      算法(第4版) Chapter 5.2 单词查找树

  • 空间

    • 与 R和所有键的字符总数之积 成正比

    • 链接

      • 一棵单词查找树的链接总数为RN到RNw之间,w为键的平均长度

      • 当所有键较短时,链接总数接近RN

      • 当所有键较长时,链接总数接近RNw

      • 缩小R能节省大量空间

三向单词查找树

  • 避免空间消耗

  • 每个结点含有一个字符,三个链接(小于,等于,大于),可能含有一个值

  • 字符是显式保存在每个结点中

TST 代码

public class TST<Value> {
    private Node root; // root of trie

    private class Node {
        char c; // character
        Node left, mid, right; // left, middle, and right subtries
        Value val; // value associated with string
    }

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

    private Node get(Node x, String key, int d) {
        if (x == null)
            return null;
        char c = key.charAt(d);
        if (c < x.c)
            return get(x.left, key, d);
        else if (c > x.c)
            return get(x.right, key, d);
        else if (d < key.length() - 1)
            return get(x.mid, key, d + 1);
        else
            return x;
    }

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

    private Node put(Node x, String key, Value val, int d) {
        char c = key.charAt(d);
        if (x == null) {
            x = new Node();
            x.c = c;
        }
        if (c < x.c)
            x.left = put(x.left, key, val, d);
        else if (c > x.c)
            x.right = put(x.right, key, val, d);
        else if (d < key.length() - 1)
            x.mid = put(x.mid, key, val, d + 1);
        else
            x.val = val;
        return x;
    }
}

相关推荐