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

In this post, we will cover memory efficient Trie implementation in C++ using map data structure.

 
 

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

Output:

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

 

 
Also see: Java Implementation of Trie Data Structure

 
References: https://en.wikipedia.org/wiki/Trie

 
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

avatar
  Subscribe  
newest oldest most voted
Notify of
sachin
Guest
sachin

Nice implementation. Keep up the good work!!

TheRock
Guest
TheRock

and it’s not space efficient if you really think about millions of string insertion, check this solution for an english directory having as less as 400K words and check it’s space efficiency.

Tom K.
Guest
Tom K.

Also take a look at Judy arrays which are more efficient.

Tishant
Guest
Tishant

Hi Techie Delight, I loved your post but since I am java user I tried implementing it in java, I am not able to delete the node, I would be glad if you can help me asap.

https://textb.org/t/chand/