数据结构与算法 - Trie字典树(前缀树)
2020-01-06 本文已影响0人
沐兮_d64c
1，Trie树简介
1）字典树，
一种树形结构，用边表示字符，沿途所经过的边组成了一个字符串，结点值为“1” 表示单词的结尾。如由26个字母组成的字典树，就是26叉树，每个节点包含26个子节点。
又称前缀树，某个节点的后代存在共同的前缀。
2）核心思想，最大限度的减少无谓的字符串比较，使用空间换时间，使用公共前缀提高查询效率。
3）时间空间复杂度，如m种字符，n长度：空间复杂度为O(m^n)，时间复杂度O(n)。
image.png
4）主要应用，处理字符串匹配(如前缀匹配搜索提示)、字符串集合中快速查找字符串。
2，数据结构 - 数组实现
1）定义TrieNode
image.png
2）定义insert方法
image.png
3）定义search和startWith
image.png
image.png
4）查找带有通配符.的字符串
image.png
4，数据结构 - hashMap实现
1）HashTrieNode定义
image.png
2）定义insert方法
image.png
3）定义search和startWith
image.png
4）查找带有通配符.的字符串
image.png
