On (15 May 97) Soren Petersen wrote to All...
 SP> Is there anybody out there, how can tell me were i can find something
 SP> about programming and servicing a binary search tree.
Sure.
 SP> I would like to know something about the following subjects:
 SP> How to insert something in the tree and still be sure that the tree is
 SP> very compact (to enable the fastest search capabilities)
 SP> How to delete a node in the tree.
If at all possible, I'd advise finding a copy of the Standard Template
Library. (aka STL)  If you have a recent compiler, it might include a
copy; otherwise, it's available a number of different places on the
internet, and from quite a few BBSes.
This includes code for maps, which are typically implemented as
Red-Black trees.  They could use AVL trees instead, but I've never
actually seen such an implementation.
If you really want to deal with this at a low-level on your own, writing
your own code for the tree, almost any decent algorithms and data
structures book will cover them.  One that I like is ,  _Information
Retrieval: Data Structures and Algorithms_ edited by W. Frakes and R.
Baeza-Yates, copyright 1992, Prentice Hall.   Corman and Rivest's book
is also extremely good.
Other possiblities include _Algorithms in C++_, by Robert Sedgewick, and
_Algorithms + Data Structures = Programs_ by Niklaus Wirth.  Sedgewick's
book covers Red-Black trees, but doesn't give sample code for a complete
implementation.  Wirth's book covers AVL trees and another type of tree
very similar to a Red-Black tree that he calls a Binary B-Tree.  In both
cases complete examples are given in Pascal (hardly surprising since
Wirth invented Pascal...)
    Later,
    Jerry.
... The Universe is a figment of its own imagination.
--- PPoint 1.90
---------------