John  <IrLGwLee@mailinator.com> 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:

    http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic19/

Also see:

    http://www.cliki.net/TREES
    http://www.cliki.net/spatial-trees
    http://www.cliki.net/Red-Black-trees
    http://www.toad.net/~menkejg/nary-tree


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607