a tree question

[amirben at TAURUS.BITNET]

In article <421 at ohs.UUCP> bhil at 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
------