10 September 2010
Trie data structure - In C++
Having had a comprehensive coverage of the TRIE data structure in Java, me and my roommate thought it would achieve completion if we have the same implemented in C++. Don't get carried away by the length of the code. Its as simple and easy as the equivalent one in Java. You may go through the comprehensive tutorial here. Trust me, it takes only 10 minutes!!.
Please feel free to ask any questions if you face difficulties in understanding any part of the resource. I would respond to you immediately.
Demonstration of trie operations
Cheers!!
Jack.
Subscribe to:
Post Comments (Atom)
9 comments:
I think
'void trie::delete_word(char* s)' is not perfect. it just look for the condition '(t->edge[c]->prefixes == 1' and then delete the node. Actually we can get this situation and possibly the whole word is not validate yet, it means suppose we have a string in data structure say "abcdef" where "e" has "1" as prefixes. Now suppose we pass a string to be deleted as "abcdeM", this code will delete the string from DS without validating that it does not exists at all.
Please let me know if i am wrong any where.
Yes, you are very true Tapesh. We need to check for word existence before deleting it from the trie DS. Thanks for bringing this to our notice. We will update the code accordingly.
Hi, I'm still learning c++ at the moment, and I'm doing a project where a trie would work best.
First of all thanks a lot for posting this resource, I've had so much trouble finding a good trie resource online.
I am having trouble understanding the node struct within the trie class. Specifically the node* member and the root part (line 39-40). My understanding of struct goes as far as using them like classes with typical data types like int, char etc, so I don't understand why it accepts node as a data type. Also a word on the pointers in the program if you can as I'm still fuzzy on usage and implementation.
Thanks a lot!
Hey, What happens if I insert same string two times by doing this:
insert("Hello");
insert("Hello");
Above insert() implementation, will simply increase the prefixes value for each character in the string thus making to difficult to delete that string later.
Its better, if we check for the existence of the string in the trie before inserting it again.
Pls correct me if I am wrong.
I just want to say thank you!!
I search high and low through out the net for Trie implementation.
You are a life saver.
Thanx again!
Blessings!
@Ronin: You're most welcome !
This is little nitpicking but where you increment the "s" pointer e.g. *s++ can be simplified to s++ because you are not using the value of *s. Just good programming standard!
I'm not sure i understand how the nodes work, for example how could you implement breadth first search to find the shortest path from one word to another?
Hi Prabhu,
Great implementation! Your implementation has definitely been the most comprehensible one from others I have searched for on the internet. I do have one question, however.
In the search_word function, why do you only return true, if it is the end of the word in the trie? For example if you insert "hey", and then search to see if "he" is a word in the trie, you will return false, because at the end of "he" you will not be at the end of the word that is already inserted. Any help would be greatly appreciated.
Thanks,
Adam Johns
Post a Comment