Trie树的实现(思路分析)

Trie树的实现(思路分析)

这里我们只讲解关于普通Trie树的实现思路:

第一: 结点类(TrieNode)的定义

1. 我们的Trie树是一个多叉树, 而不是一个二叉树, 所以结点类中的子节点不止有左右子结点, 子节点有多个, 因此我们一般都是直接声明一个子节点数组

   • 我们此时是要做一个单词字典树, 所以这个树最多是一个26叉树, 所以我们的子节点数组长度都定为26即可

     • 但是我们可以发现: 如果我们使用数组的形式来存储子节点, 那么将会很浪费空间, 因为我们的某些结点后面可能只有几个子节点, 但是由于数组初始化时必须确定长度, 由于数组的不可变长, 所以我们为了满足要求在初始化时我们就只能将数组的长度定义为26, 但实际使用中可能远远不需要这么多结点, 并且在第一层中有数组长度为26, 那么到了下一次之后每个结点又会有26个结点, 那么也就是第二层中就会有26 * 26个结点, 层数多了之后就会出现严重的空间浪费, 那么我们可不可以使用另一种结构来代替数组存储子节点?

       • 当然是有的, 比如我们的HashMap就可以替代数组来存储子节点, 我们使用HashMap来代替数组存储子节点的时候空间复杂度肯定是会大幅度减少的, 但是同时效率也会有一点点的减缓

         • 为什么效率会减缓?

           • 因为如果我们是使用长度为26的数组存储的时候, 那么我们在找对应的某个结点的子节点中是否有我们的目标字母时, 我们只需要去使用目标字母减去a, 这样我们就能得到一个数值, 这个数值就能作为索引, 我们只要在数组中这个对应索引位置去找即可, 时间复杂度为"正真的O(1)", 但是如果是使用HashMap的时候, 那么我们肯定也是使用的目标字母减去a之后的值作为键, 然后值就存储目标字母即可, 但是使用HashMap在查找的时候如果我们这个时候多个键计算出hash值之后如果最终计算出在底层数组中存储的索引位置重复之后这个时候查询的时候的时间复杂度就不是正真的O(1)了, 因为这个时候我们会去对应位置下挂载的链表或者是红黑树上去找, 此时的查找效率就不是正真的O(1)了

         • 但是这个时候空间复杂度肯定是降低了很多, 因为我们子节点中实际存储几个值, 我们就创建几个结点之后放到子节点对应的HashMap中即可

2. 声明一个isword属性(boolean类型) —> 表示这个字母对应的字符串是一个单词

3. 声明一个无参构造, 其中为我们的char [] 进行初始化

第二: trie树类

1. 我们肯定是先声明一个TrieNode root作为根节点
   • 注意: 根节点是一个虚拟结点, 不存储字母
2. 声明一个无参构造方法用于创建Trie树
   • 在无参构造方法中为root赋值, 也就是完成对root结点的初始化, 因为root结点为虚拟结点, 所以我们初始化的时候我们直接创建一个TrieNode赋值给root即可完成Trie树的创建
3. 在Trie树中添加单词的方法
   • 我们首先肯定是传入一个String类型的实参, 这个String类型的实参中存储的就是单词, 那么我们将这个String类型的单词转换为一个char [] , 然后对这个char[] 进行一个遍历, 遍历到第一个字母时, 判断我们的头结点的子节点数组中有没有该字母, 如果有, 则继续向下遍历下一个字母, 并且判断第一个字母的子节点数组中是否有我们的这个字母, 如果没有, 则将此字母添加到数组中的对应位置, 一直到char[] 遍历完为止, 等到最后一个字母遍历完成之后, 我们在最后的这个字母所在的节点里将isword属性修改为true即可
4. 判断Trie树中是否有参数单词的方法
   • 我们也是先将参数单词转换为char [], 然后开始遍历char[],一遍遍历char[], 一边在trie树中从头结点开始向下判断是否存在对应字符序列, 当char[]遍历完之后, 如果trie树中此时遍历到的最后一个节点中的isword属性是true, 则return true(也就表示存在此单词), 如果遍历过程中char[] 中的某个值在trie树中没有对应存在, 那么就直接return false(表示不存在)
5. 判断trie树中是否存在指定前缀的方法
   • 判断是否存在指定前缀其实和判断是否存在某个的方法的实现几乎是一样的, 只是判断是否存在前缀的时候最终不需要最后一个遍历的trie数中的对应结点的isword属性为true, 因为前缀可以不是一个单词, 所以对isword属性是没有要求的