Making a trie with continuation classes

Here come a basic trie implementation with some comments to allow a better understanding of the code.

class Node():
    """ A tree's node """
    def __init__(self, value):
        self.value = value
        self.branchs = {}

    # method that start and end with "__" are magic method in python. They are used by many built in function and object
    # see at "http://www.rafekettler.com/magicmethods.html" for more information about them.
    def __repr__(self):
        """ Method called by print """
        subtrees = []
        for key in self.branchs.keys():
            subtrees.append(self.branchs[key].__repr__())

        return "({0}:{1})".format(self.value, ",".join(subtrees))

    def __contains__(self, word):
        """ Method called by 'in' """
        if word == []:
            return True
        else:
            key = word.pop(0)
            if key not in self.branchs.keys():
                return False
            else:
                return self.branchs[key].__contains__(word)

    def add(self, chain):
        """ Add a character chain in the tree. """
        if chain == []:
            pass
        else:
            #have to follow the branch that is labeled by the first letter of the chain.
            branch_key = chain[0]
            #extand the tree if needed
            if not branch_key in self.branchs.keys():
                self.branchs[branch_key] = Node(self.value + branch_key)
            #then recursivly call the add function
            self.branchs[branch_key].add(chain[1:])

# -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*-

class PrefixTree():
    """ A prefix tree object """

    def __init__(self):
        self.root = Node("")

    def insert(self, word):
        """ Insert a word in the tree """
        self.root.add(list(word))

    def __repr__(self):
        """ Method called by print """
        return "<PrefixTree : {0}>".format(self.root.__repr__())

    def __contains__(self, word):
        """ Method called by 'in' """
        return self.root.__contains__(list(word))

# -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*-

#the main block of the program
if __name__ == "__main__" :

    words_1st_group = ["manger", "manquer", "rater", "roter", "rallier"]

    trie = PrefixTree()

    for word in words_1st_group :
        trie.insert(word)
        print(trie)

    print("'manger' is in trie :", 'manger' in trie)
    print("'Manger' is in trie :", 'Manger' in trie)

I believe that this code is more understandable by new being in the python universe than the one you got before. The code you were provided do not split the tree logic from the file parsing code for example that is a bad practice in general.
The next step of this code would be to replace the hard codded list of words by the opening of a file and the add of every word it contains into the tree ( don’t try to print it anymore then 😉 ).

If any question regarding the code do not hesitate. If you do not succeed in asking something in English, I also speak French, so do not hesitate to contact me directly by email for answer.

Leave a Comment