Patricia Trie (PATRICIA): compressed prefix tree. Internal nodes split on bit/char position. Each edge labeled with shared prefix string. O(k) lookup.