Skip to content

Trie API Reference

trie

Trie (prefix tree) data structure implementation.

This module provides a Trie data structure that stores key-value pairs efficiently for prefix-based lookups. Unlike a radix tree, a standard trie stores one character per node, making it simpler but potentially more memory-intensive.

Classes

Trie

A trie (prefix tree) data structure for efficient key-value storage.

The Trie stores key-value pairs where each node represents a single character, allowing for fast prefix-based searches and insertions.

Attributes:

Name Type Description
root TrieNode

The root node of the trie.
Source code in patrix/trie.py 
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
class Trie:
    """
    A trie (prefix tree) data structure for efficient key-value storage.

    The Trie stores key-value pairs where each node represents a single character,
    allowing for fast prefix-based searches and insertions.

    Attributes
    ----------
    root : TrieNode
        The root node of the trie.
    """

    def __init__(self, key_value_pairs):
        """
        Initialize a Trie with a collection of key-value pairs.

        Parameters
        ----------
        key_value_pairs : iterable
            An iterable of (key, value) tuples to insert into the trie.
            Each key must be a non-empty string.

        Raises
        ------
        ValueError
            If any key is empty or not a string.
        """
        self.root = TrieNode()
        for key, value in key_value_pairs:
            self.insert(key, value)

    def insert(self, key, value):
        """
        Insert a key-value pair into the trie.

        If the key already exists, its value will be updated. Each character
        of the key is stored in a separate node.

        Parameters
        ----------
        key : str
            The key to insert. Must be a non-empty string.
        value
            The value to associate with the key.

        Raises
        ------
        ValueError
            If key is empty or not a string.
        """
        if key == "":
            raise ValueError("Key cannot be empty")
        if not isinstance(key, str):
            raise ValueError("Key must be a string")
        self.root.insert(key, value)

    def search(self, word):
        """
        Search for a node corresponding to the given word in the trie.

        Traverses the trie following the characters of the word and returns
        the node if found, or None if the word is not present in the trie.

        Parameters
        ----------
        word : str
            The word to search for. Must be a non-empty string.

        Returns
        -------
        TrieNode or None
            The node corresponding to the word if found, None otherwise.

        Raises
        ------
        ValueError
            If word is empty or not a string.
        """
        if word == "":
            raise ValueError("Word cannot be empty")
        if not isinstance(word, str):
            raise ValueError("Word must be a string")
        return self.root.search(word)

    def asdict(self):
        """
        Convert the trie to a nested dictionary representation.

        Returns
        -------
        dict
            A nested dictionary where each key is a character and the value
            is either another dictionary (for nodes with children) or None.
            Note: This representation does not preserve the values stored
            in leaf nodes, only the tree structure.
        """
        return self.root.asdict()
Functions
__init__ 
__init__(key_value_pairs)

Initialize a Trie with a collection of key-value pairs.

Parameters:

Name Type Description Default
key_value_pairs iterable

An iterable of (key, value) tuples to insert into the trie. Each key must be a non-empty string.

 required

Raises:

Type Description
ValueError

If any key is empty or not a string.
Source code in patrix/trie.py 
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def __init__(self, key_value_pairs):
    """
    Initialize a Trie with a collection of key-value pairs.

    Parameters
    ----------
    key_value_pairs : iterable
        An iterable of (key, value) tuples to insert into the trie.
        Each key must be a non-empty string.

    Raises
    ------
    ValueError
        If any key is empty or not a string.
    """
    self.root = TrieNode()
    for key, value in key_value_pairs:
        self.insert(key, value)
asdict 
asdict()

Convert the trie to a nested dictionary representation.

Returns:

Type Description
dict

A nested dictionary where each key is a character and the value is either another dictionary (for nodes with children) or None. Note: This representation does not preserve the values stored in leaf nodes, only the tree structure.
Source code in patrix/trie.py 
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
def asdict(self):
    """
    Convert the trie to a nested dictionary representation.

    Returns
    -------
    dict
        A nested dictionary where each key is a character and the value
        is either another dictionary (for nodes with children) or None.
        Note: This representation does not preserve the values stored
        in leaf nodes, only the tree structure.
    """
    return self.root.asdict()
insert 
insert(key, value)

Insert a key-value pair into the trie.

If the key already exists, its value will be updated. Each character of the key is stored in a separate node.

Parameters:

Name Type Description Default
key str

The key to insert. Must be a non-empty string.

 required
value

The value to associate with the key.

 required

Raises:

Type Description
ValueError

If key is empty or not a string.
Source code in patrix/trie.py 
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
def insert(self, key, value):
    """
    Insert a key-value pair into the trie.

    If the key already exists, its value will be updated. Each character
    of the key is stored in a separate node.

    Parameters
    ----------
    key : str
        The key to insert. Must be a non-empty string.
    value
        The value to associate with the key.

    Raises
    ------
    ValueError
        If key is empty or not a string.
    """
    if key == "":
        raise ValueError("Key cannot be empty")
    if not isinstance(key, str):
        raise ValueError("Key must be a string")
    self.root.insert(key, value)
search 
search(word)

Search for a node corresponding to the given word in the trie.

Traverses the trie following the characters of the word and returns the node if found, or None if the word is not present in the trie.

Parameters:

Name Type Description Default
word str

The word to search for. Must be a non-empty string.

 required

Returns:

Type Description
TrieNode or None

The node corresponding to the word if found, None otherwise.

Raises:

Type Description
ValueError

If word is empty or not a string.
Source code in patrix/trie.py 
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
def search(self, word):
    """
    Search for a node corresponding to the given word in the trie.

    Traverses the trie following the characters of the word and returns
    the node if found, or None if the word is not present in the trie.

    Parameters
    ----------
    word : str
        The word to search for. Must be a non-empty string.

    Returns
    -------
    TrieNode or None
        The node corresponding to the word if found, None otherwise.

    Raises
    ------
    ValueError
        If word is empty or not a string.
    """
    if word == "":
        raise ValueError("Word cannot be empty")
    if not isinstance(word, str):
        raise ValueError("Word must be a string")
    return self.root.search(word)

TrieNode

A node in the trie data structure.

Each node stores a single character, an optional value, references to child nodes, and a reference to its parent node.

Attributes:

Name Type Description
children dict

Dictionary mapping characters to child TrieNode instances.
value

The value stored at this node (None if this is not a leaf node).
parent (TrieNode, optional)

Reference to the parent node (None for root).
prefix str

The single character prefix associated with this node.
Source code in patrix/trie.py 
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
class TrieNode:
    """
    A node in the trie data structure.

    Each node stores a single character, an optional value, references to
    child nodes, and a reference to its parent node.

    Attributes
    ----------
    children : dict
        Dictionary mapping characters to child TrieNode instances.
    value
        The value stored at this node (None if this is not a leaf node).
    parent : TrieNode, optional
        Reference to the parent node (None for root).
    prefix : str
        The single character prefix associated with this node.
    """

    def __init__(self):
        """
        Initialize a TrieNode.

        Creates a new node with no children, no value, no parent, and
        an empty prefix.
        """
        self.children = {}
        self.value = None
        self.parent = None
        self.prefix = ""

    def insert(self, key, value):
        """
        Insert a key-value pair into the subtree rooted at this node.

        Recursively traverses or creates nodes for each character in the key,
        storing the value at the final node. If a path already exists for the
        key, the value is updated.

        Parameters
        ----------
        key : str
            The key to insert. If empty, stores the value at the current node.
        value
            The value to associate with the key.
        """
        if len(key) == 0:
            self.value = value
            return self
        prefix, suffix = key[0], key[1:]
        if prefix in self.children:
            child = self.children[prefix]
            child.insert(suffix, value)
            return

        # If there is no children with that key, create one
        child = TrieNode()
        self.children[prefix] = child
        child.parent = self
        child.prefix = prefix
        child.insert(suffix, value)

    def search(self, word):
        """
        Search for a node corresponding to the given word in the subtree.

        Recursively traverses the trie following the characters of the word,
        returning the node if found, or None if the word path does not exist.

        Parameters
        ----------
        word : str
            The word to search for. Must have at least one character.

        Returns
        -------
        TrieNode or None
            The node corresponding to the word if found, None otherwise.
        """
        if len(word) == 1:
            return self.children.get(word)
        char = word[0]
        if char not in self.children:
            return None
        return self.children[char].search(word[1:])

    def asdict(self):
        """
        Convert the subtree rooted at this node to a nested dictionary.

        Recursively converts all children and their subtrees into a nested
        dictionary structure that represents the tree topology.

        Returns
        -------
        dict
            A nested dictionary where keys are characters and values are
            dictionaries representing child subtrees. Leaf nodes return
            empty dictionaries.
        """
        return {k: v.asdict() for k, v in self.children.items()}

    def get_key(self):
        """
        Reconstruct the full key path from the root to this node.

        Recursively traverses up the parent chain, concatenating all prefix
        characters to form the complete key that leads to this node.

        Returns
        -------
        str
            The complete key string from the root to this node. Returns
            empty string if this is the root node.
        """
        if self.parent is None:
            return ""
        return self.parent.get_key() + self.prefix
Functions
__init__ 
__init__()

Initialize a TrieNode.

Creates a new node with no children, no value, no parent, and an empty prefix.

Source code in patrix/trie.py 
129
130
131
132
133
134
135
136
137
138
139
def __init__(self):
    """
    Initialize a TrieNode.

    Creates a new node with no children, no value, no parent, and
    an empty prefix.
    """
    self.children = {}
    self.value = None
    self.parent = None
    self.prefix = ""
asdict 
asdict()

Convert the subtree rooted at this node to a nested dictionary.

Recursively converts all children and their subtrees into a nested dictionary structure that represents the tree topology.

Returns:

Type Description
dict

A nested dictionary where keys are characters and values are dictionaries representing child subtrees. Leaf nodes return empty dictionaries.
Source code in patrix/trie.py 
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
def asdict(self):
    """
    Convert the subtree rooted at this node to a nested dictionary.

    Recursively converts all children and their subtrees into a nested
    dictionary structure that represents the tree topology.

    Returns
    -------
    dict
        A nested dictionary where keys are characters and values are
        dictionaries representing child subtrees. Leaf nodes return
        empty dictionaries.
    """
    return {k: v.asdict() for k, v in self.children.items()}
get_key 
get_key()

Reconstruct the full key path from the root to this node.

Recursively traverses up the parent chain, concatenating all prefix characters to form the complete key that leads to this node.

Returns:

Type Description
str

The complete key string from the root to this node. Returns empty string if this is the root node.
Source code in patrix/trie.py 
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
def get_key(self):
    """
    Reconstruct the full key path from the root to this node.

    Recursively traverses up the parent chain, concatenating all prefix
    characters to form the complete key that leads to this node.

    Returns
    -------
    str
        The complete key string from the root to this node. Returns
        empty string if this is the root node.
    """
    if self.parent is None:
        return ""
    return self.parent.get_key() + self.prefix
insert 
insert(key, value)

Insert a key-value pair into the subtree rooted at this node.

Recursively traverses or creates nodes for each character in the key, storing the value at the final node. If a path already exists for the key, the value is updated.

Parameters:

Name Type Description Default
key str

The key to insert. If empty, stores the value at the current node.

 required
value

The value to associate with the key.

 required
Source code in patrix/trie.py 
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
def insert(self, key, value):
    """
    Insert a key-value pair into the subtree rooted at this node.

    Recursively traverses or creates nodes for each character in the key,
    storing the value at the final node. If a path already exists for the
    key, the value is updated.

    Parameters
    ----------
    key : str
        The key to insert. If empty, stores the value at the current node.
    value
        The value to associate with the key.
    """
    if len(key) == 0:
        self.value = value
        return self
    prefix, suffix = key[0], key[1:]
    if prefix in self.children:
        child = self.children[prefix]
        child.insert(suffix, value)
        return

    # If there is no children with that key, create one
    child = TrieNode()
    self.children[prefix] = child
    child.parent = self
    child.prefix = prefix
    child.insert(suffix, value)
search 
search(word)

Search for a node corresponding to the given word in the subtree.

Recursively traverses the trie following the characters of the word, returning the node if found, or None if the word path does not exist.

Parameters:

Name Type Description Default
word str

The word to search for. Must have at least one character.

 required

Returns:

Type Description
TrieNode or None

The node corresponding to the word if found, None otherwise.
Source code in patrix/trie.py 
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
def search(self, word):
    """
    Search for a node corresponding to the given word in the subtree.

    Recursively traverses the trie following the characters of the word,
    returning the node if found, or None if the word path does not exist.

    Parameters
    ----------
    word : str
        The word to search for. Must have at least one character.

    Returns
    -------
    TrieNode or None
        The node corresponding to the word if found, None otherwise.
    """
    if len(word) == 1:
        return self.children.get(word)
    char = word[0]
    if char not in self.children:
        return None
    return self.children[char].search(word[1:])