CODEWITHSUNDEEP
time-complexitybinary-search-treeternary-search-tree
msd
msd

Reputation: 73

Which is faster, a ternary search tree or a binary search tree?

ternery search tree requires O(log(n)+k) comparisons where n is number of strings and k is the length of the string to be searched and binary search tree requires log(n) comparisons then why is TST faster than BST ?

Upvotes: 2

Views: 2189

Answers (2)

templatetypedef
templatetypedef

Reputation: 372814

Ternary search trees are specifically designed to store strings, so our analysis is going to need to take into account that each item stored is a string with some length. Let's say that the length of the longest string in the data structure is L and that there are n total strings.

You're correct that a binary search tree makes only O(log n) comparisons when doing a lookup. However, since the items stored in the tree are all strings, each one of those comparisons takes time O(L) to complete. Consequently, the actual runtime of doing a search with a binary search tree in this case would be O(L log n), since there are O(log n) comparisons costing O(L) time each.

Now, let's consider a ternary search tree. With a standard TST implementation, for each character of the input string to look up, we do a BST lookup to find the tree to descend into. This takes time O(log n) and we do it L times for a total runtime of O(L log n), matching the BST lookup time. However, you can actually improve upon this by replacing the standard BSTs in the ternary search tree with weight-balanced trees whose weight is given by the number of strings in each subtree, a more careful analysis can be used to show that the total runtime for a lookup will be O(L + log n), which is significantly faster than a standard BST lookup.

Hope this helps!

Upvotes: 0

user207421
user207421

Reputation: 310957

Because in the ternary case it is log3(n) where in the binary case it is log2(n).

Upvotes: 0

Related Questions