Deleting a word from a specific implementaion of trie in Python -

i kinda new datastructures , implementing trie disambiguate database of names using edit distance. using following implementation of trie:

http://stevehanov.ca/blog/index.php?id=114

which basically:

class trienode:      def __init__(self):        self.word = none        self.children = {}         global nodecount        nodecount += 1      def insert( self, word ):        node = self        letter in word:             if letter not in node.children:                  node.children[letter] = trienode()              node = node.children[letter]         node.word = word  # read dictionary file trie trie = trienode() name in names:     wordcount += 1     trie.insert( name ) 

this job beautifully inserts names trie. now, go through list of names have 1 one, , use trie return list of names @ edit distance passed name. want delete names trie returned in list.

is there fast way that?

thanks!

there 2 ways this, depending on whether want check whether you're removing last path through internal node (which makes removes slower, potentially makes searches after removes faster). both ways trivial recursively, if want unroll iteratively (as insert does), not checking easier, i'll that.

def delete(self, word):     node = self     letter in word[:-1]:         if letter not in node.children:             return false         node = node.children[letter]     if word[-1] in node.children:         del node.children[letter]         return true     return false 

---

can make faster? yes, may not matter.

first, know nodes exist, can remove of error checking. more importantly, if can make search function return nodes, instead of values, make things little faster. if can add backlinks trie, means can erase node in constant time instead of repeating search. if don't want backlinks trie, can exact same benefit returning zipper instead of node—or, more simply, returning stack of nodes.

but really, worst case here doubling work, not increasing algorithmic complexity or multiplying large factor, simple wins.