Trie

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
Implementations
Python: Custom implementation

# assume only lower case characters
class Trie():
class Node():
def __init__(self, value):
self.value = value
self.children = [None] * 26
self.is_word = False

def 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 = True

def __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
DeleteO(n)O(n)
InsertO(n)O(n)
SearchO(n)O(n)
SpaceO(n)O(n)

Similar