algorithmbinary-searchprefix-tree

Which search is faster, binary search or using prefix tree?


Suppose I have a list of strings and a prefix tree of those strings, and I would like to locate a string given a key, which one is more faster? binary search or prefix tree search?

Why and what's the time complexity?

Thanks!


Solution

  • Both techniques have their advantages, and their drawbacks:

    Suffix tree

    Binary search (with suffix array)

    Both of these data structures are really powerful. If your application requires fast searching, and the space supplied is enough, then definitely go for suffix trees. But if the space matters, then suffix array(binary search) is the only choice you have...