递归专项-数据结构-前缀树_前缀树空间复杂度

前缀树

前缀树是一种特殊的树，非常适合于处理一些字符串相关的问题。使用了前缀树其查询性能与有多少个字符串无关，而仅仅与字符串的长度有关。针对与一些英语单词或者一些有字符组成的串，往往长度实际情况下并不是很长，那么这种就特别适合于使用前缀树进行查询或者检索，性能会比较好。但是往往提升这么好的查询性能，就需要牺牲掉空间复杂度，因此前缀树Trie的问题也是在与空间占用较大。一棵形象的前缀树如下所示：

我们使用递归方式来实现前缀树的插入操作， 查询操作，检索操作。

• 插入操作的递归方式如下：

public void insert(String word) {
        insertDg(root, word, 0);
    }

    private void insertDg(Node node, String word, int index) {
        if (index == word.length()) {
            if (!node.isWordTail) {
                node.isWordTail = true;
                size++;
            }
            return;
        }
        if (node.next.get(word.charAt(index)) != null) {
            insertDg(node.next.get(word.charAt(index)), word, index + 1);
        } else {
            Node newNode = new Node(false);
            node.next.put(word.charAt(index), newNode);
            insertDg(newNode, word, index + 1);
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 搜索的递归操作如下：

public boolean search(String word) {
        return searchDg(root, word, 0);
    }

    private boolean searchDg(Node node, String word, int index) {
        if (index >= word.length()) {
            return node.isWordTail;
        }
        if (node.next.get(word.charAt(index)) == null) {
            return false;
        } else {
            return searchDg(node.next.get(word.charAt(index)), word, index + 1);
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 前缀匹配查询的递归操作如下：

public boolean startsWith(String prefix) {


        return startsWithDg(root, prefix, 0);
    }

    private boolean startsWithDg(Node node, String prefix, int index) {

        if (index >= prefix.length()) {
            return true;
        }

        if (node.next.get(prefix.charAt(index)) != null) {
            return startsWithDg(node.next.get(prefix.charAt(index)), prefix, index + 1);
        } else {
            return false;
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

其最终全部的代码参考：

package data.structure.trie;

import java.util.Map;
import java.util.TreeMap;

public class Trie {
    private class Node {
        // 是否是某个单词的末尾
        public boolean isWordTail;

        // trie 树的子节点
        public Map<Character, Node> next;

        public Node() {
            this(false);
        }

        public Node(boolean isWordTail) {
            this.isWordTail = isWordTail;
            next = new TreeMap<>();
        }
    }

    // trie树的根节点
    private Node root;
    // 代表有多少个单词
    private int size;

    public int getSize() {
        return size;
    }

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        insertDg(root, word, 0);
    }

    private void insertDg(Node node, String word, int index) {
        if (index == word.length()) {
            if (!node.isWordTail) {
                node.isWordTail = true;
                size++;
            }
            return;
        }
        if (node.next.get(word.charAt(index)) != null) {
            insertDg(node.next.get(word.charAt(index)), word, index + 1);
        } else {
            Node newNode = new Node(false);
            node.next.put(word.charAt(index), newNode);
            insertDg(newNode, word, index + 1);
        }
    }

    public boolean search(String word) {
        return searchDg(root, word, 0);
    }

    private boolean searchDg(Node node, String word, int index) {
        if (index >= word.length()) {
            return node.isWordTail;
        }
        if (node.next.get(word.charAt(index)) == null) {
            return false;
        } else {
            return searchDg(node.next.get(word.charAt(index)), word, index + 1);
        }
    }

    public boolean startsWith(String prefix) {


        return startsWithDg(root, prefix, 0);
    }

    private boolean startsWithDg(Node node, String prefix, int index) {

        if (index >= prefix.length()) {
            return true;
        }

        if (node.next.get(prefix.charAt(index)) != null) {
            return startsWithDg(node.next.get(prefix.charAt(index)), prefix, index + 1);
        } else {
            return false;
        }

    }
}


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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94