Trie树的实现(代码实现) [Java]

Trie树的实现(代码实现)

先给出TrieNode类(Trie树节点类):

class TrieNode{
    //定义子节点数组, 因为我们的trie树是一个多叉树, 我们的子节点有多个, 所以我们直接定义一个子节点数组即可
    TrieNode [] children;

    //表示当前位置的字符串是否为一个单词
    boolean isWord;

    //提供无参构造, 给children数组初始化, 这个时候我们使用的是普通数组作为子节点数组, 所以这个时候的数组长度我们直接定义为26即可
    public TrieNode(){
        /*
        在创建一个节点的时候我们就要完成对子节点数组的初始化操作, 使用的是数组动态初始化方式, 声明了一个长度为26的TireNode[], 初始的时候
        数组中的所有元素默认赋值为null
         */
        this.children = new TrieNode[26];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

然后给出Trie树类:

public class Trie {
    //定义根节点
    TrieNode root;

    //定义一个无参构造, 在其中完成根节点的初始化, 也就是创建一个Trie树
    public Trie(){
        this.root = new TrieNode();
    }

    //编写在Trie树中添加单词的方法
    public void insert(String word){
        //因为我们要遍历Trie树, 一旦需要遍历, 我们就要定义一个临时变量, 使用这个临时变量来代替root引用来遍历trie树, 因为我们的root引用的指向是不能改变的
        TrieNode node = root;

        //进行一个循环, 进行char[]的遍历以及trie数中元素的添加
        for(char c : word.toCharArray()){
            //如果trie中对应子节点数组中没有改字母, 则我们我们就要添加该字母到trie树中的对应位置
            /*
            这个时候注意: 我们这里标识某个位置有没有指定字母只需要判断children数组中对应位置有没有结点即可, 因为我们每个索引位置都对应的一个字母, 只要这个位置是有结点的
            这个时候就是表示有对应的字母, 所以我们添加指定的某个字母的时候其实就是在对应位置添加一个节点即可
             */
            if(node.children[c - 'a'] == null) node.children[c - 'a'] = new TrieNode();

            //指针下移 (这一步操作就和我们的二叉树中的node = node.left 或者是node = node.right的功能还是一样的)
            node = node.children[c - 'a'];
        }

        //最终遍历完数组之后退出for循环之后node是指向了最后一个结点的, 我们这个节点位置表示的是一个单词(因为此时我们的操作就是添加单词), 所以这个时候我们一定要将这个结点的isWord属性修改为true
        node.isWord = true;
    }

    //查询单词的方法, 如果存在目标单词就返回true, 如果不存在目标单词就返回一个false
    public boolean search(String word){
        //因为我们查询单词的时候要遍历trie树, 所以我们需要定义一个临时变量用于遍历
        TrieNode node = root;

        for(char c : word.toCharArray()){
            if(node.children[c - 'a'] == null) return false;

            //指针下移
            node = node.children[c - 'a'];
        }

        //即使这些字母都存在于trie数中, 这个时候我们也不能直接返回true, 因为这个时候我们是判断是否存在指定单词, 我们最终要判断这个查询的字符串是否是一个单词, 如果真的是单词再返回true
        return node.isWord;
    }

    //查询前缀的方法, 如果存在目标前缀就返回true
    public boolean startsWith(String prefix){
        //因为我们查询单词的时候要遍历trie树, 所以我们需要定义一个临时变量用于遍历
        TrieNode node = root;

        for(char c : prefix.toCharArray()){
            if(node.children[c - 'a'] == null) return false;

            //指针下移
            node = node.children[c - 'a'];
        }

        //这个时候我们是查找指定的前缀, 这个时候前缀不是一个单词, 只要对应的字符都按照顺序出现在我们的trie树中, 那么我们就返回一个true
        return true;
    }
}
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

最后再给出测试代码:

//测试代码
public static void main(String[] args) {
    Trie trie = new Trie();
    trie.insert("hello");

    boolean he = trie.startsWith("he");
    System.out.println(he);

    boolean hello = trie.search("hello");
    System.out.println(hello);
}
1
2
3
4
5
6
7
8
9
10
11

复杂度分析:

时间复杂度分析:

1. 假设所有的字符串长度之和为n, 构建字典树的方法的时间复杂度为O(n)
2. 假设要查找的字符串长度为k, 查找的时间复杂度为O(k)

空间复杂度分析:

字典树每个结点都需要用一个数组来存储子节点的指针, 即便某个结点只有两三个子节点, 但依然需要一个完整大小的数组, 所以, 字典树是比较消耗内存的, 也就是空间复杂度较高

• 那么我们如何优化字典树的空间复杂度较高的问题?

  1. 使用其他数组结构代替数组来存储子节点

     • 我们之前讲过的, 可以将每个结点的子节点数组使用其他数组结构代替( 例如: 有序数组, 红黑树, 散列表等) --> 我们之前讲过使用HashMap来存储子节点数组, 使用HashMap存储子节点时可以降低空间复杂度, 但是会有一定程度的效率降低, 就是因为当一个HashMap集合中存储的元素比较多的时候key就容易冲突, 那么就会出现多个key存储到底层数组中的同一个位置, 那么当多个key存储到底层数组中同一个位置的时候查找的效率就不是正真的O(1), 会比正真的O(1)慢一点
       • 当子节点使用有序数组存储时, 可以使用二分查找查找下一个字符
       • 我们的字典树的子节点存储结构可以使用有序数组是因为如果有序, 那么我们同样就能确定一个字母在数组中的位置, 但如果是无序数组, 那么相对位置就是无序的,为了确定字母在数组中的位置, 子节点数组的长度就只能是声明为26, 一个字母占一个位置 —> 使用有序数组存储子节点的时候我们的字符就可以根据相对位置, 根据比较的结构判断出来(可以通过夹逼定理得出 , 其实就是通过二分查找确定下一个字符的位置)
       • 但是采用这几种结构的时候空间复杂度降低之后, 效率也有一定的降低

  2. 缩点优化

     • 将末尾一些只有一个子节点的结点, 可以进行合并, 但是增加了编码的难度, 如下:

       [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mQWXa7nI-1669121402687)(E:\非凡英才\数据结构(java)]\数据结构图解\Trie的缩点优化(空间复杂度优化).png)

• 那么我们要如何实现上图的这种缩点优化?

  • 我们肯定是先构建好上面图中左图这样的trie树, 然后构建的时候为每个结点添加一个成员属性sum, 这个属性表示这个节点的后续还有几个单词, 左图的根节点sum = 4, 第一层中a结点的sum = 3, s结点的sum = 1, 第二层中b结点的sum = 2, d结点的sum = 1, i结点的sum = 1, 第三层中cfra结点的sum都等于1, 到这里其实我们到这里就可以发现: 从上到下遍历的时候如果某个结点的sum = 1, 就可以对这个节点进行一个缩点优化, 将这个sum = 1的结点的子节点的值全部合并到这个节点中来, 然后将这个结点的子节点全部删去即可