Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Python compressed trie updates: split on insertion and compact after deletion

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

A compressed trie stores multi-character edge labels and keeps terminal markers where complete keys end.

Download Python source kit

Operation contract

The owned trie accepts at most 64 distinct lowercase ASCII keys, each no longer than 16 characters. Insertion scans for an edge with the same first character, consumes a shared prefix, and splits an edge when a key ends or diverges inside it. Deletion removes only the terminal marker for the exact key. An empty child is pruned; a nonterminal child with one edge is merged into its parent edge. A terminal prefix is never merged away. The test sequence inserts car, cart, carbon and cat, removes car, then confirms the longer keys survive.

Failure and ownership boundary

The tree stores set membership, not counts or payload records. Missing deletion returns false and repeated insertion leaves the set unchanged. An empty key is rejected so the root has no special terminal-key role. Recursion is bounded by the 16-character key contract. Python compressed trie: merge single-child paths without losing terminal words, Python trie deletion: remove one word without losing its prefix neighbors and Python trie: exact words, prefixes and node allocation establish the comparison.

Working program

python
class RadixSet:
    def __init__(self):
        self.root = [False, {}]
        self.size = 0
    def validate(self, key):
        if type(key) is not str or not 1 <= len(key) <= 16 or any(char not in "abcdefghijklmnopqrstuvwxyz" for char in key):
            raise ValueError("bounded ASCII key")
    def contains(self, key):
        self.validate(key)
        node = self.root
        while key:
            edge = next((label for label in node[1] if key.startswith(label)), None)
            if edge is None:
                return False
            key, node = key[len(edge):], node[1][edge]
        return node[0]
    def add(self, key):
        self.validate(key)
        if self.contains(key):
            return False
        if self.size >= 64:
            raise ValueError("key capacity")
        def insert(node, suffix):
            if not suffix:
                node[0] = True
                return
            for label, child in list(node[1].items()):
                shared = 0
                while shared < min(len(label), len(suffix)) and label[shared] == suffix[shared]:
                    shared += 1
                if not shared:
                    continue
                if shared == len(label):
                    insert(child, suffix[shared:])
                else:
                    branch = [False, {label[shared:]: child}]
                    del node[1][label]
                    node[1][label[:shared]] = branch
                    insert(branch, suffix[shared:])
                return
            node[1][suffix] = [True, {}]
        insert(self.root, key)
        self.size += 1
        return True
    def discard(self, key):
        self.validate(key)
        def remove(node, suffix):
            if not suffix:
                if not node[0]:
                    return False
                node[0] = False
                return True
            for label, child in list(node[1].items()):
                if not suffix.startswith(label):
                    continue
                if not remove(child, suffix[len(label):]):
                    return False
                if not child[0] and not child[1]:
                    del node[1][label]
                elif not child[0] and len(child[1]) == 1:
                    extension, descendant = next(iter(child[1].items()))
                    del node[1][label]
                    node[1][label + extension] = descendant
                return True
            return False
        removed = remove(self.root, key)
        self.size -= int(removed)
        return removed

index = RadixSet()
for identifier in ("car", "cart", "carbon", "cat"):
    index.add(identifier)
print("removed prefix:", index.discard("car"))
print("membership:", [index.contains(key) for key in ("car", "cart", "carbon", "cat")])
print("missing removal:", index.discard("cab"))
print("duplicate:", index.add("cart"))
print("size:", index.size)

Output

Output
removed prefix: True
membership: [False, True, True, True]
missing removal: False
duplicate: False
size: 3

Costs and limits

Each node scans at most 26 outgoing first-character choices under the declared alphabet. Traversal comparisons follow the key, but Python slicing and concatenation allocate strings; this implementation can perform O(L squared) copied-character work along a deeply split L-character key. Distinct-key storage is bounded by total stored key characters plus node/mapping overhead. It is not a compact native-memory index or a concurrent structure.

Common Mistakes

  • Never merge away a terminal prefix during compaction.
  • Deleting a prefix must not delete the subtree containing longer keys.

Connected lessons

Python compressed trie: merge single-child paths without losing terminal words, Python trie deletion: remove one word without losing its prefix neighbors, Python trie: exact words, prefixes and node allocation.

python
radix-trie-updates
Storage details