Need help finishing a program

Question

I need some help finishing this code. I don't expect you to give me the full answer, I just need some hint about the 2 functions. thanks

class Trie(object):
 """A Trie of TrieNodes. Trie has the following attributes:
 -- _root: a TrieNode; the root of this Trie.
 """
 def __init__(self):
 """Create an empty Trie."""
 self._root = TrieNode()
 def insert(self, word, data):
 """Insert the string 'word' with data 'data' into this Trie.
 -- word: the string with which the newly inserted 'data' will
 be associated.
 -- data: the data which will be stored in the TrieNode
 associated with the string 'word'.
 If there is a TrieNode associated with the word 'word' in this
 Trie, then _data of this TrieNode is updated to 'data'. Otherwise,
 enough new TrieNodes are created and inserted into this Trie, to
 create a TrieNode associated with 'word'.
 """
 raise Exception, "Implement me!"
 def find_node(self, word):
 """Return the TrieNode that corresponds to the string 'word'
 in this Trie. Return None if there is no such TrieNode in this
 Trie.
 -- word: a string; the TrieNode that corresponds to 'word'
 (if it exists) is returned.
 """
 raise Exception, "Implement me!"

• Mark Rushakoff: Tagging as homework.
• SubniC: He hints are in the docstring, what are you exactly looking for?
• Joe: I hope this isn't homework... are they really teaching data structures in Python?
• user395760: @Joe: What would be so terrifying about that?
• Joe: @delnan - nothing in particular, but it just feels a little absurd. A trie node in C is something like an array of pointers, but in Python is something like a dictionary of references. The reason that structures like tries exist is to make languages like Python, and structures like dictionaries, possible. I know it's only a teaching exercise, but what's the point of teaching data structures if students are not likely going to be able to use them in that form? Better to teach Tries in C. IMHO.

Answer 1

If all you want is a hint, take a look at Wikipedia's entry for the trie, which tells you everything you need to know about how tries work.

Okay, here's another hint: every node of the trie will contain a dictionary whose keys are characters and whose values are trie nodes. The insert method will look at word[0], find or create the node for that character, and then, if len(word) is greater than 1, do something with word[1:].

Answer 2

If Robert's hints aren't enough, here is a minimal implementation of a Trie with the two functions that you were having trouble with.

class Trie(object):
 def __init__(self, char='', data=None):
 self.children = []
 self.char = char
 self.data = data
 def get_child(self, char):
 for child in self.children:
 if child.char == char:
 return child
 def insert(self, key, data, node=None):
 if node is None:
 node = self
 if len(key) == 0:
 #key found
 node.data = data
 return node.data
 else:
 child = node.get_child(key[0])
 if child is None:
 child = Trie(key[0])
 node.children.append(child)
 return self.insert(key[1:], data, child)
 return self.insert(key[1:], data, child)
 def find(self, key, node=None):
 if node is None:
 node = self
 if len(key) == 0:
 #key found
 return node.data
 else:
 child = node.get_child(key[0])
 if child is None:
 return None
 return self.find(key[1:], child)
>>> tree = Trie()
>>> tree.insert('t', 't data')
>>> tree.insert('tr', 'tr data')
>>> print tree.find('t'), tree.find('tr')
t data tr data