if i want to implement phonebook using trie then how will i manage key value pairs as in hashmaps , i mean if we make a trie of phone numbers then how will we know that whose number is this and if implementing trie using names then how will i know what is the number of a partifcular person.
Implementation of phonebook using trie
We know that in trie at the last digit of number we mark isTerminal is true. Now create a hashmap of this terminal node’s address and the name of the person. Then, we can mark phone number to each of the person.
even after using trie we had to use hashmaps for creating phonebook then what is the benefit.
The benefit is that we do not need to stores phone numbers in hashmaps. We can store phone numbers in trie in much lesser space. Hashing phone number with the name of person do not take much extra space.
Ok , that i understood
Can you please explain the tradeoff while using trie and hashmaps to create a phonebook.
One more thing ,
If a want to implement a phonebook like the original one in our phones in which we can search with phone numbers as well as with name , so for that i am thinking that i will make two tries one for names and other for phone numbers and two hashmaps as well one containing the names as key and address of terminal nodes in phone number trie as values and other hashmap vice versa.
So in this if a user wants to search from name then our code would use the name hashmap to search for the name and the pointer to the termial node of the phone number trie will provide us the phone number , similarly in case when user wants to search from phone nunber.
In this way functionality is improved as well as time complexity but just space complexity is suffered.
So is what i am thinking right or it needs some optimization , my aim is just to enable users both way searching.
Please reply…
I didn’t get ur first question.
Yes, u can do in this way to store name and phone numbers and trie separately in different trie but still hashmap is required for mapping two. So, again it consumes more space than the approach we previously discussed.