Subj : Re: binary search
To   : comp.programming
From : Ben Pfaff
Date : Thu Jul 28 2005 03:38 pm

alfps@start.no (Alf P. Steinbach) writes:

>> but the pay-off is that you can do a binary search trivially, 
>> starting at the first item and using simple comparison to find the item 
>> quickly, chasing "prev" and "next" pointers at each level.
>
> If the data comes in sorted your procedure will build a degenerate tree,
> which is indeed list-like, and in that case searching is O(n).

We were starting from a sorted linked list.  Building a balanced
binary search tree from a sorted linked list is easy.  I have a
webpage on how to do it:
        http://adtinfo.org/libavl.html/Transforming-a-Vine-into-a-Balanced-BST.html
-- 
"Writing is easy.
 All you do is sit in front of a typewriter and open a vein."
--Walter Smith

.