# hash & balanced trees

Charles Victor Bancroft (bancroft@america.net)
Mon, 30 Jun 1997 23:28:59 -0400 (EDT)

- Messages sorted by:[ date ][ thread ][ subject ][ author ]

    On Mon, 30 Jun 1997, Amy Bruckman wrote:

    > Subject : Re: my kingdom for a hash table!
    > ----- Message Text -----
    > ..., something about operations increasing exponentialy, ...
    The computational complexity of most algorithms over particular data
    structures is provable.  The computational complexity for searching a
    linear list for a specified string is on the order of the number of
    elements in the list and is often denoted O(n).  If the list is kept in
    a sorted fashion, algorithms can achieve greater efficency than O(n/2).
    Of course, there is a greater cost of adding an element to a sorted list
    than to an unordered list.  This tradeoff, between computation required to
    create and maintain a data structure and the complexity of searching for
    an element, is a primary issue when considering alternative structures.

    Balanced binary trees are O(log(n)) on searches, and algortithms such as AVL
    trees have acceptable insertion and deletion measures.  Besides, there is c
    source code available.

    more,
    l8r,
    v