Is the usual implementation of a trie equivalent to
std::map<std::string, int>
in C++?
By equivalence, I mean: do they have the same space complexity, and does their respective operation have the same time complexity?
1 Answers
No, I don't believe so. std::map and std::set are usually implemented as red-black balanced binary trees
Space complexity is much better in a prefix tree -- you're storing the common prefix to a whole bunch of strings in one consolidated place, whereas in a binary tree the whole string is stored in the node, so the prefix is repeated in each string that has it.
Time complexity for finds, inserts, removals is still average O(log n). However, the constant factor is often important. Prefix trees generally trade for lower height but greater width. The specific application is important for choosing which one.
Related