Trie Tree
The Trie Tree is also called prefix tree, is a kind of search tree used to store a dynamic set ort assoriative array where the keys are usually strings.
The first to propose this concept was in 1959
This paper discusses techniques for use in locating records stored within a low-speed memory medium where they are identifiable by a key word or words of variable length on a machine not equipped to accomplish this automatically. The technique is also applicable to the conversion of variable word length information into fixed length code words.
from File Searching Using Variable Length Keys REN E D E LA BRIANDAISf 1959
Algorithm
The Trie tree has 3 oprations, find,insert and startsWith.
Define Node
Firstly, we need define a trie with dict. Because the dict uses hashable method to build, the time complexity of search is as quick as Tree
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.trie_dic = {}
Find strings
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
node = self.trie_dic
for i in word:
if i in node:
node = node[i]
else:
return False
return True if node["val"] == 1 else False
Insertion
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: None
"""
node = self.trie_dic
for i in word:
if i in node:
node = node[i]
else:
node[i] = {"val":0}
node = node[i]
node["val"] = 1
Startswith
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
node = self.trie_dic
for i in prefix:
if i not in node:
return False
else:
node = node[i]
return True
Trie Visualization
Leetcode 208th Implement Trie (Prefix Tree)
Implement a trie with insert, search, and startsWith methods.
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
Note:
You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.
Source code
Content
lass Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.dict_trie = {}
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: None
"""
node = self.dict_trie
for i in word:
if i in node:
node = node[i]
else:
node[i] = {"val":0}
node = node[i]
node["val"] = 1
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
node = self.dict_trie
for i in word:
if i in node:
node = node[i]
else:
return False
return True if node["val"] == 1 else False
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
node = self.dict_trie
for i in prefix:
if i not in node:
return False
else:
node = node[i]
return True
if __name__ == '__main__':
pre_tree = Trie()
words = ["Trie","insert","search","search","startsWith","insert","search"]
for i in words:
pre_tree.insert(i)
print(pre_tree.search("Trie"))
print(pre_tree.search("search"))
print(pre_tree.search("inser"))
Reference
前缀树
trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
Trie trree概念最早提出是在1959年, REN E D E LA BRIANDAISf 讨论了用于定位存储在低速存储介质中的记录的技术，在这些记录中，可以通过未配备自动完成此功能的机器上的一个或多个可变长度的关键字来识别它们。该技术也适用于可变字码长度转换为固定长度代码。
应用
trie树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能
Leetcode 208th 实现 Trie (前缀树)
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。
可以通过字典来存储键值,因为字典是用hash方法创建, 查找时间快
Source code
Content
lass Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.dict_trie = {}
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: None
"""
node = self.dict_trie
for i in word:
if i in node:
node = node[i]
else:
node[i] = {"val":0}
node = node[i]
node["val"] = 1 #使用1来做结尾
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
node = self.dict_trie
for i in word:
if i in node:
node = node[i]
else:
return False
return True if node["val"] == 1 else False
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
node = self.dict_trie
for i in prefix:
if i not in node:
return False
else:
node = node[i]
return True
if __name__ == '__main__':
pre_tree = Trie()
words = ["Trie","insert","search","search","startsWith","insert","search"]
for i in words:
pre_tree.insert(i)
print(pre_tree.search("Trie"))#True
print(pre_tree.search("search"))#True
print(pre_tree.search("inser"))#False