Trie Operations (Insert, Search, Delete) 🎯

Welcome to an exciting journey through the world of Tries! In this lesson, we'll explore how to create, manage, and manipulate a Trie (also known as a prefix tree or trie) for efficient data storage and retrieval. By the end of this lesson, you'll understand the key operations of a Trie: Insert, Search, and Delete, and be ready to implement them in your own projects. 💡 Pro Tip: Tries are particularly useful in applications like spell-checkers, autocomplete suggestions, and URL shorteners.

What is a Trie? 📝

A Trie is a tree-like data structure that stores a collection of strings. Each node in the Trie represents a character, and branches represent the subsequent characters. The beauty of Tries lies in their ability to quickly search for strings with a common prefix, making them incredibly efficient for handling large datasets.

Nodes and Edges

Each node in a Trie has a maximum of 26 children (for an English alphabet), a parent node, a value (for the end nodes), and a boolean indicating whether the node is a terminating node or not.

Terminology

Prefix: A sequence of characters that can be extended to a word in the Trie
Non-terminal node: A node in the Trie that is not a terminal node (i.e., it doesn't have a value)
Terminal node: A node in the Trie that has a value

Creating a Trie 💡 Pro Tip: Start with an empty Trie

To create a Trie, we'll initialize a root node with all its children being null. We'll represent the Trie as a dictionary, where each key is a character and the value is another dictionary (or None for the root node).

python

class TrieNode:
    def __init__(self):
        self.children = {chr(i): None for i in range(ord('a'), ord('z') + 1)}
        self.is_terminal = False
        self.value = None
        self.parent = None

root = TrieNode()

Insert Operation 💡 Pro Tip: Adding new words to the Trie

To insert a word into the Trie, we'll traverse from the root node to the appropriate terminal node for the word, creating missing nodes as necessary.

python

def insert(node, word):
    current_node = node
    for char in word:
        current_node = current_node.children[char]
        if current_node is None:
            current_node = TrieNode()
            current_node.parent = current_node.children[char]

    current_node.is_terminal = True

Search Operation 💡 Pro Tip: Checking if a word is in the Trie

To search for a word in the Trie, we'll follow the same path as during the insert operation, checking if we reach a terminal node. If the terminal node has a value, we return that value; otherwise, we return None.

python

def search(node, word):
    current_node = node
    for char in word:
        if current_node.children.get(char) is None:
            return None
        current_node = current_node.children[char]

    return current_node.value if current_node.is_terminal else None

Delete Operation 💡 Pro Tip: Removing words from the Trie

Deleting a word from the Trie involves removing the terminal node and all its descendant non-terminal nodes if they have no other children. We'll mark a non-terminal node for deletion if all its children are marked for deletion and it has no other children.

python

def delete(node, word):
    current_node = node
    for char in word:
        if current_node.children.get(char) is None:
            return False  # Word not found
        current_node = current_node.children[char]

    if current_node.is_terminal and not current_node.children:
        current_node.is_terminal = False
        current_node.value = None
        current_node.parent.children.pop(char)
    else:
        current_node.is_terminal = False
        current_node.value = None

        if not current_node.children:
            parent = current_node.parent
            if not parent.children:
                root = parent.parent
                root.children.pop(ord(char))
            else:
                parent.children.pop(char)

    return True

Practical Examples 💡 Pro Tip: Seeing Tries in action

To demonstrate the power of Tries, we'll create a simple autocomplete suggestion system that suggests words as the user types.

python

words = ["apple", "banana", "cherry", "date", "orange"]
trie = Trie()

for word in words:
    trie.insert(word)

def autocomplete(prefix):
    current_node = trie.root
    results = []

    for char in prefix:
        if current_node.children.get(char) is None:
            return results
        current_node = current_node.children[char]

    traverse_trie(current_node, prefix, results)
    results.sort()
    return results

def traverse_trie(node, prefix, results):
    if node.is_terminal:
        results.append(prefix + node.value)

    for char, child in node.children.items():
        traverse_trie(child, prefix + chr(ord(char)), results)

Trie Operations (Insert, Search, Delete) 🎯

Trie Operations (Insert, Search, Delete) 🎯

What is a Trie? 📝

Nodes and Edges

Terminology

Creating a Trie 💡 Pro Tip: Start with an empty Trie

Insert Operation 💡 Pro Tip: Adding new words to the Trie

Search Operation 💡 Pro Tip: Checking if a word is in the Trie

Delete Operation 💡 Pro Tip: Removing words from the Trie

Practical Examples 💡 Pro Tip: Seeing Tries in action

Quiz