Trie

A trie is a kind of search tree – an efficicent information reTrieval data structure. Using Trie, search complexities can be brought to optimal limit.

If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree. Using Trie, we can search the key in O(M) time. However the penalty is on Trie storage requirements.

Illustration by WikiPedia

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class TrieNode:
def __init__(self):
self.children = [None] * 26
# isLeaf is True if node represent the end of the word
self.isLeaf = Fasle

class Trie:
def __init__(self):
self.root = self.getNode()

def getNode(self):
return TrieNode()

def _charToIndex(self, ch):
return ord(ch) - ord('a')

def insert(self, word):
node = self.root
for level in range(len(word)):
index = self._charToIndex(word[level])
if not node.children[index]:
node.children[index] = self.getNode()
node = node.children[index]
node.isLeaf = true

def search(self, word):
node = self.root
for level in range(len(word)):
index = self._charToIndex(word[level])
if not node.children[index]:
return False
node = node.children[index]
return node.isLeaf
0%