Trie with path compression

1. Sort all prefixes from shortest to longest, alphanumerically (only for convenience)
2. Go the colums from left to right: find the first bit that is different for at least 2 prefixes
3. Tree split point
4. Jump only all variants share the same segment

Construction

Search in trie with path compression

Search in binary trie with path compression. Word 1100011001 given,

1. Check the 2. bit → 1 → go in right child node. P5 matches the search word. Best Match: P5
2. Check the 6. bit → 1 → go in right child node. P3 matches the search word. Best Match: P3
3. Terminate. Result: P3

In each search in trie of all types: compare search word with stored prefix in the node at the every best match update

In which case is the path compression effective?

→ Path Compression is effective, when we can constuct a tries with good balancing. Would each node have only one child, lookup will not be efficient.