Aka prefix tree or digital tree. It is a k-ary search tree used for information retrieval. The edges between nodes are normally individual/subset characters instead of the full key.
Pros | Cons |
---|---|
Efficient/fast data structure for text searches | Needs to be created manually |
Larger space requirement |
# assume only lower case characters
class Trie():
class Node():
def __init__(self, value):
self.value = value
self.children = [None] * 26
self.is_word = Falsedef build_node(self, word):
node = self.root
for letter in word:
letter_idx = ord(letter) - ord('a')
if node[letter_idx] == None:
node = Node(letter)
node.is_word = Truedef __init__(self, words):
self.root = Node("")
for word in words:
self.build_node(word)def is_word(self, word):
for letter in word:
letter_idx = ord(letter) - ord('a')
if not node[letter_idx]:
return False
node = node[letter_idx]
return node.is_word
Operations | Worst | Average |
---|---|---|
Delete | O(n) | O(n) |
Insert | O(n) | O(n) |
Search | O(n) | O(n) |
Space | O(n) | O(n) |