Subject: Re: list searching
From: (Rob Warnock)
Date: Sat, 27 Aug 2005 05:26:34 -0500
Newsgroups: comp.lang.lisp
Message-ID: <>
John  <> wrote:
| Unfortunately, for problems not suited for hash tables people sometimes
| mistakenly believe they need a balanced tree.  Balanced trees are most
| useful when you need a total ordering with frequent insertions and
| deletions. If you just want your items sorted, for example, but never add
| and delete items once you have it setup then a sorted vector will be much
| faster.

One should also consider AVL trees (a.k.a. HB[1]), red/black trees,
2-3 trees [order 3 B-tree], and other kinds of trees which permit
limited height or splay imbalance in exchange for better performance
than balanced binary trees. The following contains a summary of some
of the variations:

Also see:


Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607