Re: binary search

alfps@xxxxxxxx (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
.

Relevant Pages

  • Re: Binary Trees Help!
    ... The property I stated in previous posting was only for binary search ... To maintain the basic property of a 2 key binary search tree, ... ready example in hand and dont have much time to look for one, ... where, L is he key value in left child node, P is he key ...
    (comp.graphics.algorithms)
  • Re: NEED HELP WITH A PROGRAM....ANYONE PLEASE HELP!
    ... Write a program that opens and read a text file and records how many ... to store both a word and the number of times it occurs. ... Forget about the binary search tree. ...
    (comp.lang.c)
  • Decent datastructure for queue operations
    ... I've been developing a tool which has to use lots of queues, ... efficient as enqueue operation can take linear time (this is because ... Binary search tree might ... - or if a binary search tree is really a great idea, ...
    (comp.lang.lisp)