Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!think!husc6!m2c!wpi!oesterle
From: oesterle@wpi.wpi.edu (Shawn H. Oesterle)
Newsgroups: comp.lang.c
Subject: Binary Tree Re-balancing
Message-ID: <10403@wpi.wpi.edu>
Date: 29 Mar 90 22:06:51 GMT
Reply-To: oesterle@wpi.wpi.edu (Shawn H. Oesterle)
Organization: Worcester Polytechnic Institute, Worcester, MA
Lines: 50
Followup-To:


Greetings!

     I would like to make a request for some references or C code
for balancing binary trees after insertion/deletion.  I have been
looking at two books (_Algorithms + Data Structures = Programs_,
by Nicklaus Wirth; and _Algorithms:  Their Complexity and
Efficiency_ by Lydia Kronsj:o).  Both the books' code is in
PASCAL; I would more or less want to compare to see if I am
interpreting the code correctly, since both books implement the
balancing differently and I still want to implement it
differently than both of the books.  I plan to keep the balancing
information in structures for speed.  Simplicity is much
desirable, recursive is great.


     Disclaimer:  This is not homework, etc., etc..  I am going
to perform some manipulations with a dictionary.  If you wish,
I'll tell you more.

                      To iterate is human.
                       to recurse divine.

                        -L. Peter Deutsch

    [Stolen from The C++ Programing Language by Stroustrup] 

Shawn Oesterle { oesterle@wpi.wpi.edu }



WARNING!  The following is trivial information about SWAPPING! 
          Press 'n' NOW to skip.


Another disclaimer:  No, I don't ponder on the following stuff
night and day.  The code I came up with looks almost machine
independent and workable:

#define swap(x,y)  {     int i;\
                         for(i=0; i<sizeof(void *); i++)  {\
                              ((char *)x)[i] ^= ((char *)y)[i];\
                              ((char *)y)[i] ^= ((char *)x)[i];\
                              ((char *)x)[i] ^= ((char *)y)[i];}}

So much for efficiency/simplicity.  I hope the thread about
SWAPPING is DEAD now.  Please don't clutter up the forum with
meaningless stuff I start.

                                           long live swapping....