python 实现字典树_python 字典树（前缀树）基本操作：插入，删除、查找
1 #coding=utf-8
2 #字典嵌套牛逼,别人写的,这样每一层非常多的东西,搜索就快了,树高26.所以整体搜索一个不关多大的单词表,还是O(1).
3
4 '''
5 Python 字典 setdefault() 函数和get() 方法类似, 如果键不存在于字典中，将会添加键并将值设为默认值。6 说清楚就是:如果这个键存在字典中,那么这句话就不起作用,否则就添加字典里面这个key的取值为后面的默认值.7 简化了字典计数的代码.并且这个函数的返回值是做完这些事情之后这个key的value值.8 dict.setdefault(key, default=None)9 Python 字典 get() 函数返回指定键的值，如果值不在字典中返回默认值。10 dict.get(key, default=None)11 '''
12
13
14 classTrie:15 root ={}16 END = '/' #加入这个是为了区分单词和前缀,如果这一层node里面没有/他就是前缀.不是我们要找的单词.
17
18 definsert(self, word):19 #从根节点遍历单词,char by char,如果不存在则新增,最后加上一个单词结束标志
20 node =self.root21 for c inword:22 """
23 利用嵌套来做,一个trie树的子树也是一个trie树.24 利用setdefault的返回值是value的特性,如果找到了key就进入value25 没找到,就建立一个空字典26 """
27 node =node.setdefault(c, {})28 node[self.END] =None29 #当word都跑完了,就已经没有字了.那么当前节点也就是最后一个字母的节点
30 #加一个属性标签end.这个end里面随意放一个value即可.因为我们只是判定end这个key是否在字典里面.
31 #考虑insert 同一个单词2次的情况,第二次insert 这个单词的时候,因为用setdefault
32 #insert里面的话都不对原字典进行修改.正好是我们需要的效果.
33 #这个self.END很重要,可以作为信息来存储.比如里面可以输入这个单词的
34 #起源,发音,拼写,词组等作为信息存进去.找这个单词然后读出单词的信息.
35
36 def delete(self, word): #字典中删除word
37 node =self.root38 for c inword:39 if c not innode:40 print('字典中没有不用删')41 returnFalse42 node =node[c]43 #如果找到了就把'/'删了
44 del node['/']45 #后面还需要检索一遍,找一下是否有前缀的后面没有单词的.把前缀的最后一个字母也去掉.因为没单词了,前缀也没意义存在了.
46 #也就是说最后一个字母这个节点,只有'/',删完如果是空的就把这个节点也删了.
47 while node =={}:48 if word == '':49 return
50 tmp = word[-1]51 word = word[:-1]52 node =self.root53 for c inword:54 node =node[c]55 delnode[tmp]56
57 defsearch(self, word):58 node =self.root59 for c inword:60 if c not innode:61 returnFalse62 node =node[c]63 return self.END innode64
65 def associate_search(self, pre): #搜索引擎里面的功能是你输入东西,不关是不是单词,他都输出以这个东西为前缀的单词.
66 node =self.root67 for c inpre:68 if c not innode:69 return [] #因为字典里面没有pre这个前缀
70 node = node[c] #有这个前缀就继续走,这里有个问题就是需要记录走过的路径才行.
71 #运行到这里node就是最后一个字母所表示的字典.
72 #举一个栗子:图形就是{a,b,c}里面a的value是{b,c,d} d的value是{/,e,f} 那么/代表的单词就是ad,看这个形象多了
73 #首先看这个字母所在的字典有没有END,返回a这个list
74
75 #然后下面就是把前缀是pre的单词都加到a里面.
76 #应该用广度遍历,深度遍历重复计算太多了.好像深度也很方便,并且空间开销很小.
77 #广度不行,每一次存入node,没用的信息存入太多了.需要的信息只是这些key是什么,而不需要存入node.
78 #但是深度遍历,又需要一个flag记录每个字母.字典的key又实现不了.
79 #用函数递归来遍历:只能先用这个效率最慢的先写了
80 #因为你遍历一直到底,到底一定是'/'和None.所以一定travel出来的是单词不是中间结果.
81 def travel(node): #返回node节点和他子节点拼出的所有单词
82 if node ==None:83 return ['']84 a = [] #现在node是/ef
85
86 for i innode:87 tmp =node[i]88 tmp2 =travel(tmp)89 for j intmp2:90
91 a.append(i +j)92 returna93
94 output =travel(node)95 for i inrange(len(output)):96 output[i] = (pre + output[i])[:-1]97 returnoutput98
99
100
101 a =Trie()102 a.insert('apple')103 a.insert('appl')104 a.insert("badj")105 print(a.root)106 print(a.associate_search('ap'))107 a.delete('apple')108 print(a.search('apple'))