4

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!

Jack Twain
  • 6,273
  • 15
  • 67
  • 107

1 Answers1

6

Both techniques have their advantages, and their drawbacks:

Suffix tree

  • Advantages:
    • O(N) building complexity
    • O(M) search of a pattern of length M
    • They allow online construction
  • Drawbacks:
    • Space inefficient
    • Really complex construction algorithms

Binary search (with suffix array)

  • Advantages:
    • You can sort the string array in O(N) time
    • Space efficient (five times less memory (at least))
    • Simple and straightforward construction algorithms
  • Drawbacks:
    • They don't support online construction
    • O(M lg N) time to search a pattern of length M among N strings (this can be reduced to O(M+lg N) but this is still a little slower than suffix tree)

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...

Rontogiannis Aristofanis
  • 8,883
  • 8
  • 41
  • 58
  • is there a differnce between suffix trees and prefix trees? are they the same? – Jack Twain Jun 24 '13 at 10:53
  • I think if you build a Binary-Tree which is indexed by a good hashing function, search is `O(log N)` since you will be searching using a numerical index – Khaled.K Jun 25 '13 at 06:12