This notebook was prepared by Donne Martin. Source and license info is on GitHub.
find
only match exact words with a terminating character?list_words
only return words with a terminating character?root node is denoted by '' '' / | \ h a* m / \ \ \ a e* t* e* / \ / \ s* t* n* t* / s* find * Find on an empty trie * Find non-matching * Find matching insert * Insert on empty trie * Insert to make a leaf terminator char * Insert to extend an existing terminator char remove * Remove me * Remove mens * Remove a * Remove has list_words * List empty * List general case
Complexity:
Complexity:
Complexity:
Complexity:
%%writefile trie.py
from collections import OrderedDict
class Node(object):
def __init__(self, key, parent=None, terminates=False):
self.key = key
self.terminates = False
self.parent = parent
self.children = {}
class Trie(object):
def __init__(self):
self.root = Node('')
def find(self, word):
if word is None:
raise TypeError('word cannot be None')
node = self.root
for char in word:
if char in node.children:
node = node.children[char]
else:
return None
return node if node.terminates else None
def insert(self, word):
if word is None:
raise TypeError('word cannot be None')
node = self.root
parent = None
for char in word:
if char in node.children:
node = node.children[char]
else:
node.children[char] = Node(char, parent=node)
node = node.children[char]
node.terminates = True
def remove(self, word):
if word is None:
raise TypeError('word cannot be None')
node = self.find(word)
if node is None:
raise KeyError('word does not exist')
node.terminates = False
parent = node.parent
while parent is not None:
# As we are propagating the delete up the
# parents, if this node has children, stop
# here to prevent orphaning its children.
# Or
# if this node is a terminating node that is
# not the terminating node of the input word,
# stop to prevent removing the associated word.
if node.children or node.terminates:
return
del parent.children[node.key]
node = parent
parent = parent.parent
def list_words(self):
result = []
curr_word = ''
self._list_words(self.root, curr_word, result)
return result
def _list_words(self, node, curr_word, result):
if node is None:
return
for key, child in node.children.items():
if child.terminates:
result.append(curr_word + key)
self._list_words(child, curr_word + key, result)
Overwriting trie.py
%run trie.py
%%writefile test_trie.py
import unittest
class TestTrie(unittest.TestCase):
def test_trie(self):
trie = Trie()
print('Test: Insert')
words = ['a', 'at', 'has', 'hat', 'he',
'me', 'men', 'mens', 'met']
for word in words:
trie.insert(word)
for word in trie.list_words():
self.assertTrue(trie.find(word) is not None)
print('Test: Remove me')
trie.remove('me')
words_removed = ['me']
words = ['a', 'at', 'has', 'hat', 'he',
'men', 'mens', 'met']
for word in words:
self.assertTrue(trie.find(word) is not None)
for word in words_removed:
self.assertTrue(trie.find(word) is None)
print('Test: Remove mens')
trie.remove('mens')
words_removed = ['me', 'mens']
words = ['a', 'at', 'has', 'hat', 'he',
'men', 'met']
for word in words:
self.assertTrue(trie.find(word) is not None)
for word in words_removed:
self.assertTrue(trie.find(word) is None)
print('Test: Remove a')
trie.remove('a')
words_removed = ['a', 'me', 'mens']
words = ['at', 'has', 'hat', 'he',
'men', 'met']
for word in words:
self.assertTrue(trie.find(word) is not None)
for word in words_removed:
self.assertTrue(trie.find(word) is None)
print('Test: Remove has')
trie.remove('has')
words_removed = ['a', 'has', 'me', 'mens']
words = ['at', 'hat', 'he',
'men', 'met']
for word in words:
self.assertTrue(trie.find(word) is not None)
for word in words_removed:
self.assertTrue(trie.find(word) is None)
print('Success: test_trie')
def test_trie_remove_invalid(self):
print('Test: Remove from empty trie')
trie = Trie()
self.assertTrue(trie.remove('foo') is None)
def main():
test = TestTrie()
test.test_trie()
test.assertRaises(KeyError, test.test_trie_remove_invalid)
if __name__ == '__main__':
main()
Overwriting test_trie.py
%run -i test_trie.py
Test: Insert Test: Remove me Test: Remove mens Test: Remove a Test: Remove has Success: test_trie Test: Remove from empty trie