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); } }