Loading ...
Sorry, an error occurred while loading the content.
 

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

Expand Messages
  • Shlomi Fish
    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
    Message 1 of 1 , Mar 28, 2002
      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 shlomif@...
      Home Page: http://t2.technion.ac.il/~shlomif/
      Home E-mail: shlomif@...

      "Let's suppose you have a table with 2^n cups..."
      "Wait a second - is n a natural number?"
    Your message has been successfully submitted and would be delivered to recipients shortly.