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

Compressed tries: delete exact keys and merge unused edges

Last updated: 3 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

Deletion from a compressed trie first locates a complete stored key, clears its terminal marker, and walks back toward the root. An edge whose child has no terminal marker and no children can be removed. An edge whose child has no terminal marker and exactly one child can merge with that child's edge label. A branch shared by other keys must remain. The operation depends on exact-key status: removing a traversable prefix that was never a stored key should report false and leave the index unchanged. This program keeps variable-length edge labels and a separate terminal boolean.

Operational case

A parts index stores dock47, dock52, doll61, and the complete key dock. Removing dock makes dock an internal prefix but leaves dock47 and dock52 searchable. Removing dock52 then permits some nonbranching path labels to merge, while doll61 remains intact. Both calls return true because both keys were stored. A repeated removal of dock52 would return false. The index is case-sensitive and uses Python string comparison without Unicode normalization; an application handling user-entered identifiers should define normalization before key insertion and deletion.

Working Python program

python
class PartNode:
    def __init__(self):
        self.terminal = False
        self.children = {}


part_root = PartNode()


def shared_length(first, second):
    length = 0
    while length < min(len(first), len(second)) and first[length] == second[length]:
        length += 1
    return length


def insert(part_code):
    if not part_code:
        raise ValueError("part code is empty")
    current = part_root
    suffix = part_code
    while suffix:
        edge = next((label for label in current.children if shared_length(label, suffix)), None)
        if edge is None:
            child = PartNode()
            child.terminal = True
            current.children[suffix] = child
            return
        width = shared_length(edge, suffix)
        if width < len(edge):
            old_child = current.children.pop(edge)
            branch = PartNode()
            branch.children[edge[width:]] = old_child
            current.children[edge[:width]] = branch
            edge = edge[:width]
        current = current.children[edge]
        suffix = suffix[width:]
    current.terminal = True


def locate(part_code):
    current = part_root
    suffix = part_code
    path = []
    while suffix:
        edge = next((label for label in current.children if suffix.startswith(label)), None)
        if edge is None:
            return None, []
        path.append((current, edge))
        current = current.children[edge]
        suffix = suffix[len(edge):]
    return current, path


def contains(part_code):
    current, _ = locate(part_code)
    return current is not None and current.terminal


def remove(part_code):
    current, path = locate(part_code)
    if current is None or not current.terminal:
        return False
    current.terminal = False
    for parent, edge in reversed(path):
        child = parent.children[edge]
        if child.terminal or len(child.children) > 1:
            break
        del parent.children[edge]
        if child.children:
            suffix, grandchild = next(iter(child.children.items()))
            parent.children[edge + suffix] = grandchild
    return True


for part_code in ("dock47", "dock52", "doll61", "dock"):
    insert(part_code)
print(remove("dock"), contains("dock"), contains("dock47"))
print(remove("dock52"), contains("dock52"), contains("doll61"))

Output

Output
True False True
True False True

Time, space, and tradeoff

For a key of length L, the path walk compares edge labels against remaining input. With a bounded child alphabet and indexed edge choice, work is O(L); this simple implementation scans child labels, so a node with many children adds a branching-factor cost. The path stack uses O(number of traversed edges) extra space and the stored labels plus nodes use space proportional to inserted key material. Merging edges creates a new concatenated Python string and therefore copies those characters. Concurrent mutation would need synchronization; this example is an in-memory single-writer index.

Common Mistakes

  • Do not delete a shared branch while removing one terminal key.
  • Do not report success when only a prefix path exists.
  • Do not leave two consecutive single-child nonterminal nodes after cleanup.

Connected lessons

Apply this mutation in the index mutation project, then check the mutation quiz.

data structures
range-query-structures
Storage details