数据结构学习:Trie树

news/2024/4/20 11:55:25/文章来源:https://blog.csdn.net/nzbing/article/details/125323533

Trie

- 一、概念
- 二、代码实现
- 三、Tire树的时间复杂度和空间复杂度
- 四、Tire树的优势

一、概念

Trie树,也叫"字典树",顾名思义,是一种专门处理字符串匹配的树形结构,用来解决在一组字符串集合中快速找到某个字符串
类似于这种字符串匹配问题,可以使用RF暴力匹配、RK哈希匹配、散列表、红黑树等,但Trie树有它特有的优势

在这里插入图片描述

如上图所示,就是一颗Trie树,头节点’/'是无意义字符,节点存储了hi、how、see、so、her、hello等单词；
可以看到Tire树就是利用字符串的公共前缀,将公共前缀存储在一起

二、代码实现

可以看到,Tire树是一颗多叉树,二叉树可以每个节点存储左右节点的指针,那多叉树怎么存储呢?

可以利用散列表的思想,利用一个数组和下标来存储子节点的指针

package StringMatch;/*Trie树*/
public class Trie_zhu {private TrieNode head = new TrieNode('/'); //头节点,存储无意义字符static class TrieNode{private char value;private TrieNode[] Children = new TrieNode[26];private boolean isEnding = false;public TrieNode(char value){this.value = value;}}public void insert(String value){TrieNode p = head;char[] text = value.toCharArray();for (int i = 0; i < text.length;i++){int index = text[i] - 'a';if (p.Children[index] == null){TrieNode newNode = new TrieNode(text[i]);p.Children[index] = newNode;}p = p.Children[index];}p.isEnding = true;}public boolean find(String value){char[] text = value.toCharArray();TrieNode p = head;for (int i = 0; i < text.length;i++){int index = text[i] - 'a';if (p.Children[index] == null){return false;}p = p.Children[index];}return p.isEnding;}
}

三、Tire树的时间复杂度和空间复杂度

如果要在一组字符串中,频繁地查询某些字符串,用Trie树会非常高效,

构建trie树:需要扫描所有的字符串,时间复杂度为O(n),(n表示所有字符串的长度和)
查询trie树:如果要查询的字符串长度为k,那么只需要比对k个节点,就能完成查询操作,时间复杂度为O(k)

Trie对于匹配字符串的效率是很高的,但是会比较耗内存,是一种"空间换时间"的思路

Trie树在实现的时候,如果是用数组,且字符串中包含’a’-'z’这26个字符,那每个节点都要存储一个长度为26的数组,并且每个数组元素还需要维护指针
Trie树的本质是避免重复存储一组字符串的相同的前缀子串,但是现在每个字符(对应一个节点)的存储远远大于1个字节,而且,如果字符串中不仅包含小写字母,还包含大写字母、数字甚至是中文,重复前缀也不多,trie树不仅不能节省内存,还有可能浪费更多的内存