Binary tree search vs Binary search

[Matt Long]

Hi

   I would like to check this result:
I have tested binary tree search API from Linux (search.h) by
searching into a binary tree generated from an unsorted dictionary a
given word. The second program uses the same dictionary, from which an
array is initialized which is sorted with qsort() then the same word
is searched with binary search fct (bsearch()).
  Running both programs shows that the binary search (the second
program) is almost twice as fast as the binary tree search.
  I have used directly the sorted distionary (so qsort() should have
the highest complexity), but still the second program is the fastest.
 Is this the correct result ? What advantage has binary tree search
wrt qsort() followed by binary search ?

thanks
Bogdan

Chances are that the binary tree search generated a degenerate tree --
that is, the tree is not balanced. Each lookup _could_ take as long
as a linear search in the worst case.

Quicksort will take O(n log n)to sort, but the lookup is a guaranteed
O(log n) operation.

This is the reason for self-balancing trees, such as red-black trees.

Matt

 

[James Dow Allen]

Chances are that the binary tree search generated a degenerate tree --
that is, the tree is not balanced. Each lookup _could_ take as long
as a linear search in the worst case....

This is the reason for self-balancing trees, such as red-black trees.

OP specified "Linux search.h." Just as qsort() doesn't promise to use
Quick Sort, so 'man tsearch' may not inform about implementation
details, but I *think* the gnu tsearch() *does* use red-black trees.

The inner loops of tsearch() and bsearch() are small enough that
the actual Intel opcodes could be posted and scrutinized but it seems
more fun to speculate. Or to assume (on religious grounds?) that
the index calculation in bsearch() must take *exactly* the same
time as the pointer manipulations in tsearch().

James Dow Allen

 

[Michael Angelo Ravera]

Hi

   I would like to check this result:
I have tested binary tree search API from Linux (search.h) by
searching into a binary tree generated from an unsorted dictionary a
given word. The second program uses the same dictionary, from which an
array is initialized which is sorted with qsort() then the same word
is searched with binary search fct (bsearch()).
  Running both programs shows that the binary search (the second
program) is almost twice as fast as the binary tree search.
  I have used directly the sorted distionary (so qsort() should have
the highest complexity), but still the second program is the fastest.
 Is this the correct result ? What advantage has binary tree search
wrt qsort() followed by binary search ?

It's not surprising that searching a sorted array goes faster in a
binary fashion goes faster than a randomly inserted and not
necessarily perfectly balanced binary tree.

A binary search, on average, requires log2(N)-1 comparisons whereas
the binary tree can degnerate into a linear search if all of the keys
are inserted forwards or backwards or in runs.

I'll summarize that, if your data are either fairly static or fairly
small, and you can afford to resort it everytime something is added,
you can expect to do pretty nearly optimal by a binary search. If your
data are large and dynamic (and pretty randomly generated), a binary
tree search will pay off because you don't have to sort every time.

Basically, you didn't time the part that would have given the tree the
advantage. Under the circumstances, I'm actually a little surprised
that the binary search of a sorted array didn't beat the tree search
by *more* than the factor of two.