/* ************************************************************************ * * tree_nD.c - * * Copyright (c) 1995 * * ETH Zuerich * Institut fuer Molekularbiologie und Biophysik * ETH-Hoenggerberg * CH-8093 Zuerich * * All Rights Reserved * * Date of last modification : 95/09/15 * Pathname of SCCS file : /export/home3/cb/garant-1.0/src/SCCS/s.tree_nD.c * SCCS identification : 1.2 * ************************************************************************ */ /* to compile: ************************************************************* cc -o test tree.c -lm -fsingle -sun4 -g ***************************************************************************/ /******************************************************************** * allgemeiner AVL-Baum, adaptiert aus N. Wirth, Algorithmen und * * Datenstrukturen * * C.Bartels * * programmiert .................................. 1.3.91 * * Version 0.1 ausgetestet ....................... 6.3.91 * * Auf mehrere Dimensionen erweitert ............. 15.3.91 * ********************************************************************/ #include #include "constants.h" #include "data_structures.h" /* Zu exportierende Routinen ****************************************/ /* extern struct node_nD insert_tree(); */ /* extern void list_tree(); */ /* extern struct node_nD erase_tree(); */ /* extern struct node_nD search_tree(); */ /* extern void apply_tree(); */ /* Zu exporierende Struktur des allgemeinen typs ********************* struct node_nD { void *element; char bal; struct node_nD *left; struct node_nD *right; struct node_nD *next_dim; }; *********************************************************************/ /*********************************************************************/ /* insert and adjust tree */ /* to call h must be set to FALSE, dimension to 0 */ /*********************************************************************/ struct node_nD *insert_tree(x, p, h, comp, dimension) void *x; struct node_nD *p; int *h; int (*comp)(); int dimension; { struct node_nD *p1,*p2; int comp_result; /* insert ************************************************************/ if(p==NULL) { p = (struct node_nD *)malloc((unsigned) sizeof(struct node_nD)); *h = TRUE; p->element = x; p->left = NULL; p->right= NULL; p->next_dim = NULL; p->bal = '0'; } else { /* search on the left side and adjust ******* ************************/ comp_result = comp(x,p->element,dimension); if(comp_result < 0) { p->left = insert_tree(x, p->left, h, comp, dimension); if(*h) { switch(p->bal) { case '+': p->bal = '0'; *h = FALSE; break; case '0': p->bal = '-'; break; case '-': p1 = p->left; if(p1->bal == '-') { 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; if(p2->bal == '-') p->bal = '+'; else p->bal = '0'; if(p2->bal == '+') p1->bal = '-'; else p1->bal = '0'; p = p2; } p->bal = '0'; *h = FALSE; break; } } } else if(comp_result > 0) /* search on the right side and adjust ******************************/ { p->right = insert_tree(x, p->right, h, comp, dimension); if(*h) { switch(p->bal) { case '-': p->bal = '0'; *h = FALSE; break; case '0': p->bal = '+'; break; case '+': p1 = p->right; if(p1->bal == '+') { 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; if(p2->bal == '+') p->bal = '-'; else p->bal = '0'; if(p2->bal == '-') p1->bal = '+'; else p1->bal = '0'; p = p2; } p->bal = '0'; *h = FALSE; break; } } } else /* comp_result = 0 */ { if (dimension == DIMENSION - 1) { printf("Warning duplicated coordinate not entered into tree"); } else { if (p->next_dim == NULL) { /* initalize root of next dimension */ p->next_dim = (struct node_nD *)malloc((unsigned) sizeof(struct node_nD)); p->next_dim->element = p->element; p->next_dim->left = NULL; p->next_dim->right= NULL; p->next_dim->next_dim = NULL; p->next_dim->bal = '0'; } /* add x to tree of next dimension **********************/ *h = FALSE; p->next_dim = insert_tree(x, p->next_dim, h, comp, ++dimension); *h = FALSE; } } /* comp_result = 0*/ } /* if (p=NULL) */ return(p); } /* search */ /* prints tree as an ordered list ************************************/ void list_tree(p,print) struct node_nD *p; void (*print)(); { if (p != NULL) { list_tree(p->left,print); if(p->next_dim == NULL) print(p->element); else list_tree(p->next_dim,print); list_tree(p->right,print); } } /* erases tree ******************************************************/ struct node_nD *erase_tree(n) struct node_nD *n; { if(n != NULL) { erase_tree(n->left); if(n->next_dim == NULL) free(n->element); else erase_tree(n->next_dim); erase_tree(n->right); free(n); n = NULL; } } /* searches tree with comp(arguments,dimension) *********************/ struct node_nD *search_tree(t,comp,arguments,dimension) struct node_nD *t; int (*comp)(); void *arguments; int dimension; { int comp_result; if (t != NULL) { comp_result = comp(t->element,arguments,dimension); if (comp_result > 0) return(search_tree((*t).left,comp,arguments,dimension)); else if (comp_result < 0) return(search_tree((*t).right,comp,arguments,dimension)); else if (t->next_dim == NULL) return(t); else return(search_tree(t->next_dim,comp,arguments,++dimension)); } else return(NULL); } /* Applies function func to a node if the result of comp is 0 *************/ /* Returns the logical sum of the results of the called functions *********/ int apply_tree(t,func,comp,args,dimension) struct node_nD *t; int (*func)(); int (*comp)(); void *args; int dimension; { int comp_result; int func_result; if (t != NULL) { comp_result = comp(t->element,args,dimension); if (comp_result > 0) return(apply_tree((*t).left,func,comp,args,dimension)); else if (comp_result < 0) return(apply_tree((*t).right,func,comp,args,dimension)); else { func_result = apply_tree((*t).left,func,comp,args,dimension); func_result |= apply_tree((*t).right,func,comp,args,dimension); if (t->next_dim == NULL) func_result |= func(t->element,args); else func_result |= apply_tree(t->next_dim,func,comp,args,++dimension); return(func_result); } } else { return(0); } }