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

Question

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 ?

score 0 · Answer 1 · answered Oct 12 '14 at 09:19

0

Because in the ternary case it is log₃(n) where in the binary case it is log₂(n).

answered Oct 12 '14 at 09:19

user207421

305,947
44
307
483

-1, sorry. A ternary search tree does not find an element in log₃(*n*) time. log₃(*n*) time is what you would get if you had some sort of hypothetical ternary tree where each of the three children had one-third of the descendants; but in a *[ternary search tree](http://en.wikipedia.org/wiki/Ternary_search_tree)*, the middle child typically has only a very small proportion of the descendants. – ruakh Oct 12 '14 at 16:55

score 0 · Answer 2 · answered Nov 27 '14 at 21:35

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!

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

2 Answers2