Solution:5 - PATRICIA TRIE (RADIX TRIE)
The problem with TRIES is the space requirement. It stores characters at each node. So the number of nodes is (d*N), even with linked list approach. That means we would need 151671*26 nodes just for English alphabets. To address this we have PATRICIA (Practical Algorithm to Retrieve Information Coded in Alphanumeric) TRIE. Here if we have N keys the total nodes would be (2*N - 1) always.
Read full article from Break the CODE!!!: 5 Solutions for Search
No comments:
Post a Comment