Memory efficient Trie Implementation using Map | Insert, Search and Delete

Implement Trie using map in C++.

Prerequisites: Trie Implementation | Insert, Search and Delete

Trie is a tree-based data structure, which is used for efficient retrieval of a key in a large data-set of strings.

There are several ways to represent tries, corresponding to different trade-offs between memory use and speed of the operations. The basic form is that of a linked set of nodes, where each node contains an array of child pointers, one for each symbol in the alphabet (so for the English alphabet, one would store 26 child pointers and for the alphabet of bytes, 256 pointers).

This is simple but wasteful in terms of memory: using the alphabet of bytes (size 256) and four-byte pointers, each trie node requires a kilobyte of storage, and when there is little overlap in the strings’ prefixes, the number of required nodes is roughly the combined length of the stored strings. Also, the nodes near the bottom of the tree tend to have few children and there are many of them, so the structure wastes space storing null pointers.

The storage problem can be alleviated by an implementation where we use map to store children of a node. Now we allocate memory only for alphabets in use, and don’t waste space storing null pointers.

C++ implementation –

Download   Run Code


1 1 0 1 1
0 1 1
0 1 1
0 1 0
Trie empty!!


Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

Notify of