[Subject Prev][Subject Next][Thread Prev][Thread Next][Subject Index][Thread Index]

# re:hash & balanced trees

- Date: Mon, 7 Jul 1997 06:03:55 -0700 (PDT)
- From:
- cc: moo-cows@the-b.org
- Content-Type: TEXT/PLAIN; charset=US-ASCII
- In-Reply-To: <Pine.SOL.3.91.970630232249.2273C-100000@atl1>

    On Mon, 30 Jun 1997, Charles Victor Bancroft wrote:
    > 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.

    In this same vein, there's an article on "treaps" in this month's Dr.
    Dobb's Journal (with accompanzing source code for Java).  Insertion,
    deletion, and sorting are all O(log(n)) operations for treaps, and in
    fact the author(s) basically propose using Treap instead of Hashtable
    whenever one needs an ordered data structure and efficiency is an issue.
    Another nice property is that treaps area apparently hashtable, ordered
    list, and balanced tree all in one.  They might make a suitable addition
    to MOO for these reasons.

    Cheers,

    michael
    brundage@ipac.caltech.edu

References:

- re:hash & balanced trees

- From: Charles Victor Bancroft <bancroft@america.net>

- Prev by Subject: Re: hash & balanced trees
- Next by Subject: re:hash & balanced trees
- Prev by thread: Re: hash & balanced trees
- Next by thread: Re: my kingdom for a hash table!
- Index(es):
  - Subject
  - Thread

Home | Subject Index | Thread Index