算法练习_三向单词查找树

Posted on | Comments: | Views:
三向单词查找树的学习笔记以及代码实现

概念

在 R 向单词查找树中，每生成一个新结点，就会为该结点生成 R 个子节点，然后很多结点都是空的，因此，为了避免 R 向单词查找树的过度空间消耗，可以使用另一种数据结构的表示方法——三向单词查找树。

三向单词查找树中：

  • 每个结点包含一个字符，一个值，三个子节点；
  • 三个子节点分别对应着当前结点中，结点字母小于，等于，或大于当前结点的所有键；
  • 字符显式地保存在结点中。

图解

下图上，上面为 R 向单词查找树的示例，下面为三向单词查找树的示例

kS1cvR.png

代码实现

查找与插入

在三向单词查找树的查找操作中，我们先对比根节点，如果键的首字母较小，则在左侧子树中查找；如果键首字母较大，则在右子树中查找。递归进行该算法，知道遇到空节点或键结束。

进行插入操作时，在查找的基础之上，每当遇到一个空链接，则新建一个结点并保存字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class TST<V> {

    private Node root;

    private class Node {
        char c;
        V val;
        Node left;
        Node mid;
        Node right;
    }

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

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

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

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

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

    public static void main(String[] args) {
        TST<Integer> tst = new TST<>();
        tst.put("test", 9);
        tst.put("by", 2);
        tst.put("she", 3);
        tst.put("tyan", 5);
        Assert.check(9 == tst.get("test"));
        Assert.check(2 == tst.get("by"));
        Assert.check(3 == tst.get("she"));
        Assert.check(5 == tst.get("tyan"));
    }
}

参考文档

《算法》