Simple Implementation of a Trie data structure.

Senthil Kumaran — Thu, 22 Sep 2022 13:35:28 +0000

Trie is a type of k-ary search tree, a tree data structure used for locating specific keys from within a set.

Trie is implemented as a nested dictionary. Every insert a new temp dictionary is created for nesting, and Trie is a dictionary of dictionaries. Trie can be identified as data structure with four building blocks.

Here are the components of our trie building block

make_trie.

Input: list of words
Output: Trie
Process: Creates a top of dictionary, and calls add_word to the dictionary for each word.

add_word

Input: A trie, and a word to add.
Output: A nested dictionary with the word added.
Process: Make a copy of the dictionary in the parameter. For each character of the word, nest further either by getting value dictionary or creating a new value dictionary. Add a Marker to signify end of word addition.

is_word

Input: A trie and a word to test
Output: True if the word is present in the dictionary.
Process: Work with a copy to keep nesting until the end of word. If a character is not found return False. Finally, end of word should have "end_marker" key.

is_prefix

Input: A trie and a word to test
Output: True if a word is a prefix
Process: Same as is_word, all characters must exist, but the end_marker need not be present when we complete traversing the word.

Building a Trie using Python.


import json

_end_marker = "*"

def add_word(trie, word):
    word_trie = trie

    for ch in word:
        if ch in word_trie:
            word_trie = word_trie[ch]
        else:
            word_trie[ch] = {}
            word_trie = word_trie[ch]

    word_trie[_end_marker] = _end_marker

    return word_trie

def make_trie(*words):
    trie = dict()

    for word in words:
        add_word(trie, word)

    return trie

def is_word(trie, word):
    word_trie = trie
    for ch in word:
        if ch in word_trie:
            word_trie = word_trie[ch]
        else:
            return False
    return _end_marker in word_trie

def is_prefix(trie, word):
    word_trie = trie
    for ch in word:
        if ch in word_trie:
            word_trie = word_trie[ch]
        else:
            return False

    return True

def print_trie(trie):
    print(json.dumps(trie, sort_keys=True, indent=2))

trie = make_trie("hi", "hello", "help")

print_trie(trie)

print(is_word(trie, "hello"))
print(is_word(trie, "he"))
print(is_prefix(trie, "he"))

Output

Here is a visualization that will help us understand the state, when "hi", "help" and "hello" are inserted into the trie. "" is the end-word marker, so after hi and help, the pointer leads to "", but the characters h, e, l, will extend further to create "hello".

DEV Community: Senthil Kumaran

Simple Implementation of a Trie data structure.