Subject: All you ever wanted to know about binary search trees (and were afraid to ask)

From: Shlomi Fish <[email-masked]>
Date: Thu, 28 Mar 2002 17:43:06 +0200 (IST)

Looking for a good literate programming example, I went to check the
status of libavl 2.0. I had some positive experience working with libavl
1.4 and heard its author was planning on 2.0 to be written in literate
programming style.

I disocvered he already released it:

http://www.msu.edu/~pfaffben/avl/

In any case, it compiles into a 2.5 MB PostScript (or alternatively 1.5 MB
PDF) which contains hundreds of pages of the description of algorithms for
all sorts of binary search trees. Namely:

Plain binary trees:
Binary search trees
AVL trees
Red-black trees

Threaded binary trees:
Threaded binary search trees
Threaded AVL trees
Threaded red-black trees

Right-threaded binary trees:
Right-threaded binary search trees
Right-threaded AVL trees
Right-threaded red-black trees

Binary trees with parent pointers:
Binary search trees with parent pointers
AVL trees with parent pointers
Red-black trees with parent pointers

You got to admire these people.

Regards,

	Shlomi Fish

Knuth is not God! God's Book of Algorithms contains a volume the
word-length of Encycolpedia Britannica on hashes alone.

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"