[comp.lang.c] Binary Tree Re-balancing

oesterle@wpi.wpi.edu (Shawn H. Oesterle) (03/30/90)

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....

andrews@hpcupt1.HP.COM (Edward E. Andrews) (04/09/90)

Here is a translation of Wirth's PASCAL version:

-------------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>

#define TRUE	1
#define FALSE	0

struct node {
   int key;
   int count;
   struct node *left;
   struct node *right;
   int bal;
};

int search(int x, struct node **p)
{
   struct node *p1, *p2;
   int h;

   if (*p == NULL) {
      *p          = (struct node *) malloc(sizeof (struct node));
      (*p)->key   = x;
      (*p)->count = 1;
      (*p)->left  = NULL;
      (*p)->right = NULL;
      (*p)->bal   = 0;
      return(TRUE);
   };
   if (x == (*p)->key) {
      (*p)->count++;
      return(FALSE);
   };
   if (x < (*p)->key) {
      if ((h=search(x, &((*p)->left))) == TRUE)
	 switch ((*p)->bal) {
	    case 1:  (*p)->bal = 0;
		     return(FALSE);
	    case 0:  (*p)->bal = -1;
		     return(h);
	    case -1: p1 = (*p)->left;
		     if (p1->bal == -1) {
			(*p)->left = p1->right;
			p1->right  = *p;
			(*p)->bal  = 0;
			*p         = p1;
		     } else {
			p2         = p1->right;
			p1->right  = p2->left;
			p2->left   = p1;
			(*p)->left = p2->right;
			p2->right  = *p;
			(*p)->bal  = (p2->bal == -1?  1 : 0);
			p1->bal    = (p2->bal ==  1? -1 : 0);
			*p         = p2;
		     }
		     (*p)->bal = 0;
		     return(FALSE);
	 };
   } else {
      if ( (h=search(x, &((*p)->right))) == TRUE)
	 switch ((*p)->bal) {
	    case -1: (*p)->bal = 0;
		     return(FALSE);
	    case 0:  (*p)->bal = 1;
		     return(h);
	    case 1:  p1 = (*p)->right;
		     if (p1->bal == 1) {
			(*p)->right = p1->left;
			p1->left    = *p;
			(*p)->bal   = 0;
			*p          = p1;
		     } else {
			p2          = p1->left;
			p1->left    = p2->right;
			p2->right   = p1;
			(*p)->right = p2->left;
			p2->left    = *p;
			(*p)->bal   = (p2->bal ==  1? -1 : 0);
			p1->bal     = (p2->bal == -1?  1 : 0);
			*p          = p2;
		     }
		     (*p)->bal = 0;
		     return(FALSE);
	 }
   }
}

void visit(struct node *p)
{
   if (p != NULL) {
      printf("%d(%d)", p->key, p->bal);
      if (p->left != NULL)
	 printf("\tl:%d", p->left->key);
      if (p->right != NULL)
	 printf("\tr:%d", p->right->key);
      printf("\n");
      visit(p->left);
      visit(p->right);
   }
}

main()
{
   int i, j;
   struct node *root;
   root = (struct node *) NULL;
   for (i = 0; i < 20; i++) {
      j = random(100);
      printf("-----%d-----\n", j);
      search(j, &root);
      visit(root);
   }
}