Trie

Compressed Trie

A Compressed Trie compress the paths of nodes with only one child.

• Each node stores an index, corresponding to the depth in the uncompressed trie
  • This gives the next bit to be tested during a search
• A compressed trie with $n$ keys has at most $n-1$ internal nodes