字典树trie树 – 潘登同学的图论笔记

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树，是一种多叉树结构。

trie树的作用

Trie树的核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。

核心应用

• 字符串检索
• 词频统计
• 字符串排序
• 前缀匹配(搜索联想，不知道element-ui中的autocomplete是不是用trie树做的，反正那个用的很爽)

trie树节点

每个字母都占用一个trie树节点，根节点与子节点没有本质的区别，主要有这几个属性

• root: 是否为根节点
• dict: 装子节点的hash表
• flag: 是否为一个单词的结尾
• value: 该单词的完整内容（只有在flag为True时才有）
• count: 该单词出现的次数（只有在flag为True时才有）
• list: 是一个字典，用于遍历储存东西的(只有root节点才有)

class Trie(object):def __init__(self, root=None,flag=False,count=None,value=None):self.root = root  # root 节点用于装内容self.count = count  # count 用于计数，可以统计词频self.dict = {}  # dict 用于装子节点，子节点还是trie树self.flag = flag  # flag用于判断是否结束self.value = value # value就表示这个单词是什么self.list = {}

常规操作

先来实现最基础的四个操作:

• insert: 增,注意最后一个字母的判断以及处理即可
• search: 查
• delete: 删
• startsWith: 判断前缀是否存在

增

def insert(self, word):""":type word: str:rtype: None"""trie = selffor j,i in enumerate(word):# 如果是不是最后一个字母就遍历(或添加)if j != len(word) - 1:if i not in trie.dict:trie.dict[i] = Trie(root=i)trie = trie.dict[i]else:# 是最后一个字母且flag为true就加计数if i in trie.dict and trie.dict[i].flag:trie = trie.dict[i]trie.count += 1# 是最后一个字母但flag为false就修改flag将计数改为1elif i in trie.dict and not trie.dict[i].flag:trie = trie.dict[i]trie.flag = Truetrie.count = 1trie.value = word# 如果trie.dict中没有就新增else:trie.dict[i] = Trie(root=i,flag=True,count=1,value=word)

查

def search(self, word):""":type word: str:rtype: bool"""trie = selffor i in word:if i in trie.dict:trie = trie.dict[i]else:return Falsereturn trie.flag

删

def delete(self, word):''':type word: str:rtype: None'''if self.search(word):trie = selffor i in word:if len(trie.dict) == 1:trie.dict.pop(i)breakelse:trie = trie.dict[i]else:print('该单词不在trie树中')

判断前缀是否存在

def startsWith(self, prefix):""":type prefix: str:rtype: bool"""trie = selffor i in prefix:if i in trie.dict:trie = trie.dict[i]else:return Falsereturn True

遍历操作

遍历操作就首选DFS深度优先搜索,参数中加入prefix的目的是为了后面的联想操作，如果只做遍历可以不加；值得一提的是，我对子节点的储存采用的是字典的形式，遍历出来的结果排序刚刚好就是字典序，也就实现了前面说的字符串字典序的处理（其实真要排字典序，直接sorted就好了，没必要用trie树）

def dfs(self,path,trie,prefix=''):# 如果为真说明走到了一个单词的结尾if trie.flag:self.list[prefix + ''.join(path)] = trie.countif trie.dict == {}:returnfor i in trie.dict:path.append(i)self.dfs(path,trie.dict[i],prefix)path.pop()

给trie树创建可迭代方法

def __iter__(self):self.list = {}  # 重置self.listself.dfs([],self)return iter(self.list)

联想操作

联想业务应该是这样的： 用户输入前几个字母，然后匹配出完整的单词，使用频率越高的单词理应放在最前面；

所以整体思路是这样的： 根据前缀找到前缀最后一个字母所在的trie树节点，从那个节点开始进行DFS遍历，然后在遍历结果前加上一个前缀，最后将结果按照count进行排序最后以列表形式输出结果；

先实现排序算法，这里用的是快速排序,注意比较的值是count，最后留下的是单词；

def quick_sorted(self,dict):''':type dict: dict:rtype: list'''if len(dict) >= 2:nums = list(dict.keys())mid = nums[len(nums) // 2]left, right = {}, {}nums.remove(mid)for d in nums:if dict[d] < dict[mid]:left[d] = dict[d]else:right[d] = dict[d]return self.quick_sorted(right) + [mid] + self.quick_sorted(left)return list(dict.keys())

再实现联想操作

def dream(self,prefix):''':type prefix: str:rtype: list'''trie = selffor i in prefix:if i in trie.dict:trie = trie.dict[i]elif dict[d] == dict[mid]:if d > mid:right[d] = dict[d]else:left[d] = dict[d]else:return []self.list = {}  # 重置self.listself.dfs([],trie,prefix)return self.quick_sorted(self.list)

一些简单的测试用例

if __name__ == '__main__':trie = Trie()for i in ["ogz","eyj","e","ey","ey","hmn","v","hm","ogznkb","ogzn","hmnm","eyjuo","vuq","ogznk","og","eyjuoi","d"]:trie.insert(i)a = trie.dream('e')print(a)for j in trie:print(j)

实战 – LeetCode

208题: 只需要实现简单的增、查、判断前缀是否存在，很简单啦…

720题：词典中最长的单词, 要求返回一个由词典中其他单词逐步添加一个字母形成的最长单词；

思路1: 对每个单词的前缀都做一遍判断，然后选出通过判断的最长的那个单词(不需要额外的操作)

import Trie
class Solution(object):def longestWord(self, words):""":type words: List[str]:rtype: str"""trie = Trie()words = sorted(list(set(words)))for i in words:trie.insert(i)result = ''for i in words:flag = True# 判断这个单词的所有前缀是否都在trie树中for j in range(len(i)):if not trie.search(i[:j+1]):flag = Falsebreak# 如果这个单词的所有前缀都在这个trie树中if flag and len(i) > len(result):result = ireturn resultif __name__ == '__main__':words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]print(Solution().longestWord(words))

思路2： 直接使用DFS找到最长的那个，速度快很多但是还是不理想

#%% trie+深度优先搜索
class Solution(object):def __init__(self):self.result = ''def longestWord(self, words):""":type words: List[str]:rtype: str"""trie = Trie(root=True)words = sorted(list(set(words)))for i in words:trie.insert(i)self.dfs([],trie)return self.resultdef dfs(self, path, trie):# 当不是根节点且是单词结尾的时候(因为在进来的时候已经判断过了是否是单词结尾，不需要再重复判断)if trie.root != True:temp = ''.join(path)if len(temp) > len(self.result):self.result = tempif trie.dict == {}:returnfor i in trie.dict:# 剪枝操作：如果不是单词结尾就直接跳过if not trie.dict[i].flag:continuepath.append(i)self.dfs(path,trie.dict[i])path.pop()if __name__ == '__main__':words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]print(Solution().longestWord(words))

692题: 前K个高频单词, 题目要求是: 给一非空的单词列表，返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

那这不就跟我们写的联想函数很类似嘛…

import Trie
class Solution(object):def topKFrequent(self, words, k):""":type words: List[str]:type k: int:rtype: List[str]"""trie = Trie()for i in words:trie.insert(i)result = trie.dream('')return result[:k]if __name__ == '__main__':words = ["i","love","leetcode","i","love","coding"]k = 2print(Solution().topKFrequent(words.k))