Fundamentals of Tries
Basic Implementation
Practice Problems
Learning Resources
Fundamentals of Tries
This data structure is constructed from strings and generates a tree based on the characters of the string. We start from the leftmost character and connect each of the new characters as a node of the tree. The graphic shows the basic idea of insertion and what our data structure would look like.
Basic Implementation
class Node:
def __init__(self, val):
self.value = val
self.children = {}
def insert(self, s, idx):
# idx: index of the current character in s
if idx != len(s):
char = s[idx]
self.children.setdefault(char, Node(char))
self.children.get(char).insert(s, idx + 1)
def query(self):
# Some code goes here
...
def create_trie(words):
trie = Node('$')
for word in words:
trie.insert(word, 0)
return trie
תגובות