DS Menu

Compressed tries



Compressed tries, also known as radix trees, are an optimized version of standard tries that reduce the space they require. The main idea behind compressed tries is to merge nodes with single children to reduce the height and size of the tree. This optimization is particularly useful for reducing the memory footprint of tries that store sparse data sets, such as routing tables in network devices or dictionaries with long words.

Definition of Compressed Trie

A compressed trie is a modified version of a standard trie where chains of redundant nodes are collapsed into single nodes. This reduces the overall size of the trie while maintaining its searching capabilities

Compressed Trie Structure

  • Nodes: Unlike standard tries, where each node typically represents a single character, nodes in a compressed trie can represent entire strings or substrings of the keys being stored.
  • Edges: Each edge in a compressed trie is labeled with a non-empty string, which represents the concatenation of characters along a path in the equivalent standard trie.
  • Leaf Nodes: Leaf nodes contain the values associated with keys (if any), and indicate the termination of a key.

Constructing a Compressed Trie

  • Start with a Standard Trie: Begin by constructing a standard trie for the set of keys you need to store.
  • Merge Single-Child Nodes: For each node with a single child, merge the node with its child, combining their edge labels into a single label. Repeat this process recursively up from the leaf nodes to the root, until no more nodes can be merged.

This process reduces the depth of the trie and the total number of nodes by collapsing linear paths of nodes into single edges with combined labels.

Inserting Keys into a Compressed Trie

  • Search for the Key: Start at the root and traverse the trie following the path described by the key. Two situations may arise:
    • Exact Match: The search may terminate at a node exactly at the end of the key, indicating the key already exists.
    • Partial Match or Mismatch: The search may reach a point where it cannot proceed because of a partial match or a complete mismatch on an edge.
  • Handle Mismatches: If the search stops at a partial match:
    • Split the edge at the point of divergence, creating a new node that represents the common prefix.
    • Attach the remaining substring of the original key as a new edge leading to a new leaf node.
    • If the divergence happens at an existing node, simply add the remaining substring of the key as a new edge to a new leaf node.
  • Update Edge Labels: Adjust the edge labels to reflect the newly inserted keys or the split operation.

Searching for Keys in a Compressed Trie

  • Start at the Root: Begin your search at the root node.
  • Traverse the Trie: Follow the edges that match the sequence of characters in the key you're searching for. The search involves comparing substrings of the key with the labels on the edges.
  • Handle Matches and Mismatches:
    • Exact Match: If you can follow a path that matches the entire key exactly, the key exists in the trie.
    • Mismatch: If at any point there is no edge to follow for the next substring of the key, the key does not exist in the trie.

Deleting Keys from a Compressed Trie

Deleting keys from a compressed trie can be more complex than from a standard trie due to the merged nodes and substrings as edge labels. You would typically reverse the insertion process, removing the key and then checking if nodes can be merged again to maintain the compressed nature of the trie. Efficiency

Next Topic :Suffix Trie