Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!pasteur!ucbvax!TAURUS.BITNET!amirben
From: amirben@TAURUS.BITNET
Newsgroups: comp.lang.c
Subject: Re: a tree question
Keywords: search tree
Message-ID: <1074@taurus.BITNET>
Date: 22 Aug 89 15:27:31 GMT
References: <421@ohs.UUCP>
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: amirben%math.tau.ac.il@CUNYVM.CUNY.EDU (Ben-amram Amir)
Organization: Tel-Aviv Univesity Math and CS school, Israel
Lines: 16

In article <421@ohs.UUCP> bhil@ohs.UUCP (Brian T. Hill) writes:
>Does anyone have a good alternative to the AVL method of balancing
>binary trees?  It seems to me that the AVL method is wasteful of
>both time and space.
>

I don't know if you can save a lot beyond AVL trees, but you may find
one of the following methods more elegant/easy-to-implement:

red-black trees --- Sedgewick, Algorithms (Addison-Wesley 83).
2-3 trees --- Aho, Hopcroft and Ullman, The Design and Analysis of
              Computer Algorithms (Addison-Wesley 74).

------
 Amir
------