Binary Search Trees 
Author Message
 Binary Search Trees

I have just begun looking at ADT's and was wondering if there are any
advantages or disadvantages of using Hash Tables over using Binary Search
Trees?
--



Fri, 23 Nov 2001 03:00:00 GMT  
 Binary Search Trees

   I have just begun looking at ADT's and was wondering if there are any
   advantages or disadvantages of using Hash Tables over using Binary Search
   Trees?

Quote:
>From the documentation to libavl at <URL:http://www.msu.edu/~pfaffben/avl>:

   Consider some techniques that can be used to find a particular item
   in an ordered data set. Typical methods include sequential
   searching, binary searching, digital searches, and hash
   tables. Sequential searching is simple, but slow (O(n)). Digital
   searching requires that the entire data set be known in advance,
   and memory efficient implementations are also slow.

   Hash tables are fast (O(1)) for static data sets, but they require
   expensive table enlargements if table size can't be predicted in
   advance, and they can be wasteful of memory. In addition, it can be
   difficult and time-consuming to choose an effective hash
   function. Some hash tables variants also make deletion an expensive
   operation.

   Binary search techniques work almost as quickly (O(log(n)) on an
   ordered table, or on a binary tree. Plus, binary trees are
   efficient for insertion, deletion, and searching, if data are
   inserted in random. But if data are inserted in order then ordinary
   binary searching can degenerate to a sequential search.

   One further advantage of binary trees is that they allow easy
   iteration over the data in the tree in sorted order. With hash
   tables it is necessary to sort the data before iterating, and after
   sorting the data is no longer in hash form.

By the way, comp.programming is probably a better place to ask this
question.
--



Fri, 23 Nov 2001 03:00:00 GMT  
 Binary Search Trees

says...

Quote:
> I have just begun looking at ADT's and was wondering if there are any
> advantages or disadvantages of using Hash Tables over using Binary Search
> Trees?

There are both.  On average hashing gives access with both high and
quite uniform speed, more or less regardless of the size of collection
being searched.  Depending upon the type of hash table you use,
insertion is typically quite fast, but deletion MAY be considerably
slower.  Despite their excellent average performance, hash tables
typically have quite poor worst-case performance (linear for most
operations, as a rule).  Hash tables allow fast lookups of individual
items, but don't allow retrieval of the entire contents in an order
that's generally meaningful.

On average a binary tree will be slower if you deal with a really
large collection.  If you keep a tree (nearly) balanced, you can get
much better worst-case performance (typically a small multiple of
logarithmic), but you also make the code considerably more complex as
a rule.  A tree allows relatively simple access in the order by which
the tree is sorted.
--



Fri, 23 Nov 2001 03:00:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Binary Search Trees

2. Binary search tree

3. binary search tree problem

4. Binary Search Tree using dynamic memory allocation (URGENT request for example)

5. What is the algorithm of binary search tree?

6. Binary search tree doesn't work properly

7. Adding to a binary search tree

8. Help... Binary Search Tree

9. Binary Search Tree

10. algorythm to balance a binary search tree

11. Binary search trees

12. Binary Search Trees

 

 
Powered by phpBB® Forum Software