/* ALGORITHM 727, COLLECTED ALGORITHMS FROM ACM. THIS WORK PUBLISHED IN TRANSACTIONS ON MATHEMATICAL SOFTWARE, VOL. 20, NO. 1, MARCH, 1994, PP. 100-102. */ /* ** Program: driver (Single Precision version) ** ** Written by: Sherif Hashem - Purdue University - May 17, 1991 ** ** Revised: May 28, 1991 ** ** Language: C ** ** Computer: Sun/Sparc workstations ** ** Purpose: Provide a driver program to test the function 'obq' ** ** Uses: Function: OBQ ** ** Usage: This main program needs to be compiled and linked ** with the (3) modules: obq.c , selct.c , and xtree.c . ** It needs also to be linked with the C Math library. ** ** Variables: - a: array of real numbers of size n ** - n: size of the array a ** - m: batch size ** - q: quantile value ** - qq: estimate of the quantile ** - stdv: estimate of the standard deviation of qq ** */ #include #include void obq(); main() { float *a,qq=0.,stdv=0.; float q=0.4; unsigned long int n=100,m=4; unsigned long int i; /* Initialization */ a=(float *) malloc(n * sizeof(float)); if(!a) { puts("Memory request failed -- driver.c\n"); exit(1); } for (i=0;i #include float selct(); void xtree(); void obq(a,n,m,q,pqq,pstdv) float *a,*pqq,*pstdv; float q; unsigned long int n,m; { float nq,mq,qq,stdv,var=0.,*sa; register long int i; unsigned long int nnq,mmq; if(q<0. || q>1. || m<2 || m>(n-1)) { /* Input Validation */ puts("Input validation failed--Function obq\n"); exit(1); } sa=(float *) malloc( n * sizeof(float)); /* Initialization step */ if(!sa) { puts("Memory request failed -- Function obq\n"); exit(1); } /* Compute the estimate of the quantile */ nq=(float) q*n; nnq=ceil(nq); if(nnq==0) nnq=1; /* The case where q=0. */ for (i=0;inbig=50,say), divide-and-conquer ** strategy is used. Otherwise, quicksort is used to sort the ** given array at first, then the required element is picked up. ** ** Complexity: O(n) time, O(n) space. ** ** Reference: Aho A., J. Hopcroft and J. Ullman [1974], The Design and ** Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, ** 92-102. ** ** Uses: Function: QQSORT ** ** Usage: selct(k,n,s) ** ** Type: Float ** ** Arguments: ** -Input: ** k: rank of the required element ** n: number of elements in the array ** s: float pointer to the array ** -Output: The value of the required element is RETURNed to the ** calling program ** */ #include #include void qs(),qqsort(); float selct(k,n,s) unsigned long int k,n; float *s; { unsigned long int i,nbig=50; unsigned long int km,kk,t,xt,tt,ii; float *ss,*st,*mm,m,sol; unsigned long int med; unsigned long int is1=0,is2=0,is3=0; float fmed,*s1,*s3; if (k>n || k<1) { /* Input validation */ puts("Input validation failed -- Function selct\n"); exit(1); } /* Initialization */ ss=(float *) malloc(n * sizeof(float)); if(!ss) { puts("Memory request failed -- Function selct\n"); exit(1); } for(i=0;i=k) { /* Look in array s1 for the required element */ free(s3); sol=selct(k,is1,s1); free(s1); return sol; } else if (is1+is2 >= k) { /* The solution is simply equal to m */ free(s1); free(s3); return m; } else { /* Look in array s3 for the required element */ km=k-is1-is2; free(s1); sol=selct(km,is3,s3); free(s3); return sol; } } } /* End of function selct */ /* ** Functions: qqsort/qs (Single Precision version) ** Written by: Sherif Hashem - Purdue University - June 1990 ** Language: C ** Computer: Sun/Sparc workstations ** Revised: May 17, 1991 ** Purpose: To sort a given array of real numbers in a non-decreasing order ** Method: QuickSort ** Complexity: O(n log n) time, O(n) space. ** Usage: qqsort(a,ct) ** Function 'qqsort' acts as a driver function as it employs ** another function called 'qs' to do the actual sorting. ** 'Qqsort' passes to 'qs' the pointer to the array as ** well as the position of its first element, 0, and the ** position of the last element, (ct-1). ** Type: Void ** Arguments: ** a - real array (input/output) ** ct - dimension of a (input) */ void qqsort(a,ct) unsigned long int ct; float *a; { long int cct,zro=0; cct=ct-1; qs(a,zro,cct); return; } /* End of function qqsort */ void qs(item,lft,rght) /* Quick Sort */ float *item; long int lft,rght; { long int lr,i,j; float x,y; i=lft; j=rght; lr=(int) ((lft+rght)/2); x=item[lr]; do { while(item[i]x && j>lft) j--; if(i<=j) { y=item[i]; item[i]=item[j]; item[j]=y; i++; j--; } } while(i<=j); if(lftlv=x; root->mv=x; return; } if(!root->ps1) { /* Case of only one vertex in the tree */ root->ps1=create_ver(root->ps1); root->ps1->father=root; root->ps2=create_ver(root->ps2); root->ps2->father=root; if(x < root->lv) { root->ps1->lv=x; root->ps1->mv=x; root->ps2->lv=root->lv; root->ps2->mv=root->lv; root->lv=x; } else { root->ps2->lv=x; root->ps2->mv=x; root->ps1->lv=root->lv; root->ps1->mv=root->lv; root->mv=x; } root->n1=1; root->n2=1; return; } else { /* Case of more than one vertex in the tree */ f=in_search(x,root); /* Search for an appropriate place to store x */ if(!f->ps3) { /* f has only two sons */ if(f->lv > x) { /* Make x a left son of f */ f->ps3=f->ps2; f->n3=1; f->ps2=f->ps1; f->mv=f->lv; f->ps1=NULL; f->ps1=create_ver(f->ps1); f->lv=x; f->ps1->father=f; f->ps1->lv=x; f->ps1->mv=x; } else if(f->mv > x) { /* Make x a middle son of f */ f->ps3=f->ps2; f->n3=1; f->ps2=NULL; f->ps2=create_ver(f->ps2); f->mv=x; f->ps2->father=f; f->ps2->lv=x; f->ps2->mv=x; } else { /* Make x the third son of f */ f->ps3=create_ver(f->ps3); f->n3=1; f->ps3->father=f; f->ps3->lv=x; f->ps3->mv=x; } } else { /* f has already got 3 sons */ /* In this situation, x also become a son of f. However, since we ** ** allow at most 3 sons, function ADDSON is called to resolve ** ** the 4-son problem. Variable xv holds the value stored in the ** ** third son of f, and variable xxv holds the value stored in the ** ** fourth son of f */ if(f->lv > x) { /* Make x a left son of f */ f->psx=f->ps3; f->ps3=f->ps2; f->ps2=f->ps1; xv=f->mv; xxv=f->psx->lv; f->mv=f->lv; f->lv=x; f->ps1=NULL; f->ps1=create_ver(f->ps1); f->ps1->father=f; f->ps1->lv=x; f->ps1->mv=x; } else if(f->mv > x) { /* Make x a middle son of f */ f->psx=f->ps3; f->ps3=f->ps2; f->ps2=NULL; f->ps2=create_ver(f->ps2); xv=f->mv; xxv=f->psx->lv; f->mv=x; f->ps2->father=f; f->ps2->lv=x; f->ps2->mv=x; } else if(f->ps3->lv >x) { /* Make x the third son of f */ f->psx=f->ps3; xv=x; xxv=f->psx->lv; f->ps3=NULL; f->ps3=create_ver(f->ps3); f->ps3->father=f; f->ps3->lv=x; f->ps3->mv=x; } else { /* Make x the extra son of f */ f->psx=create_ver(f->psx); f->psx->father=f; f->psx->lv=x; f->psx->mv=x; xv=f->ps3->lv; xxv=x; } addson(f,xv,xxv); } } } /* End of function insert */ /* Function: create_ver ** Written by: Sherif Hashem - Purdue University - July 1990 ** Revised: May 29, 1991 ** Langauge: C ** Computer: Sun/Sparc workstations ** Purpose: Create an empty node for the tree ** Used By: Functions: INSERT, ADDSON ** Usage: create_ver(r) ** Type: Struct tree pointer ** Argument: ** Input: r: Pointer to structure tree (should be NULL when calling ** create_ver, this serves as a check before assigning a ** new dynamic memory space to r) ** Output: Upon RETURNing, a pointer to the created node is passed back ** to the calling program */ struct tree *create_ver(r) struct tree *r; { if(!r) { r=(struct tree *) malloc(sizeof(struct tree)); if(!r) { puts("Memory request failed -- Function create_ver\n"); exit(0); } r->father=NULL; r->lv=(-2.); /* Initialize 'lv' and 'mv' to (-2.0) is arbitrary */ r->mv=(-2.); r->n1=0; r->n2=0; r->n3=0; r->ps1=NULL; r->ps2=NULL; r->ps3=NULL; r->psx=NULL; } else puts("Logical error from function create_ver\n"); return r; } /* End of function create_ver */ /* Function: in_search ** Written by: Sherif Hashem - Purdue University - July 1990 ** Revised: May 29, 1991 ** Langauge: C ** Computer: Sun/Sparc workstations ** Purpose: Search the tree for the appropriate place to insert a given ** element x. All relevant information stored in the nodes ** along the search path are updated to reflect the effect of ** the insertion of x in the tree ** Used By: Function INSERT ** Usage: in_search(x,r) ** Type: Struct tree pointer ** Arguments: ** Input: x: the element to be added to the tree ** r: root of the tree ** Output: Upon RETURNing, a pointer to the appropriate father of x is ** passed back to the calling program */ struct tree *in_search(x,r) float x; struct tree *r; { if(!(r->ps1->ps1) ) return r; /* When r is the direct father of a leaf */ else { /* When r is not a direct father of a leaf */ if(x <= r->lv) { /* Search the left subtree of r */ (r->n1) ++; return(in_search(x,r->ps1)); } else { if(x <= r->mv) { /* Search the middle subtree of r */ (r->n2) ++; return(in_search(x,r->ps2)); } else if(!r->ps3) { /* Search the middle subtree of r and update mv */ r->mv=x; (r->n2) ++; return(in_search(x,r->ps2)); } else { /* Search the right subtree of r */ (r->n3) ++; return(in_search(x,r->ps3)); } } } } /* End of function in_search */ /* Function: addson ** Written by: Sherif Hashem - Purdue University - July 1990 ** Revised: May 29, 1991 ** Langauge: C ** Computer: Sun/Sparc workstations ** Purpose: Resolve the 4-sons problem that occur during the insertion ** Method: The effect of the insertion is propagated up towards the ** root of the tree, splitting more and more as necessary ** until the tree becomes a balanced 2-3 tree once more ** Uses: Functions: CREATE_VER, MAX4 ** Used By: Function INSERT ** Usage: addson(v,xv,xxv) ** Type: Void ** Arguments: ** Input: v: pointer to the father who currently has 4 sons ** xv: largest element in the third subtree of v ** xxv: largest element in the fourth subtree of v */ void addson(v,xv,xxv) struct tree *v; float xv,xxv; { struct tree *new,*f; new=NULL; new=create_ver(new); /* Create a new vertex, 'new' */ /* Give the 3rd and 4th sons of v to new */ new->ps1=v->ps3; new->ps2=v->psx; new->ps1->father=new; new->ps2->father=new; v->ps3=NULL; v->n3=0; v->psx=NULL; new->lv=xv; new->mv=xxv; new->n1=new->ps1->n1 + new->ps1->n2 + new->ps1->n3; if(new->n1 == 0) new->n1=1; /* Case new->ps1 is a leaf */ new->n2=new->ps2->n1 + new->ps2->n2 + new->ps2->n3; if(new->n2 == 0) new->n2=1; /* Case new->ps2 is a leaf */ /* Go upward the tree while performing any necessary splitting */ if(!v->father) { /* Case v is the root of the tree */ root=NULL; root=create_ver(root); root->ps1=v; root->ps2=new; v->father=root; new->father=root; root->n1=v->n1+v->n2+v->n3; root->n2=new->n1+new->n2+new->n3; root->lv=v->mv; /* Since v has two sons */ root->mv=new->mv; /* Since new has two sons only */ } else { /* Case v has a father */ f=v->father; new->father=f; /* Make f the father of new */ if(!f->ps3) { /* f has two sons */ if(v==f->ps1) { /* Make 'new' the second son of f */ f->ps3=f->ps2; f->n3=f->n2; f->ps2=new; f->mv=new->mv; f->n2=new->n1+new->n2; /* Since 'new' has two sons only */ f->n1=v->n1+v->n2; f->lv=v->mv; } else { /* Make 'new' the third son of f */ f->ps3=new; f->n3=new->n1+new->n2; f->n2=v->n1+v->n2; f->mv=v->mv; } } else { /* f has three sons */ if(v==f->ps1) { /* Case v the first son of f */ /* Make 'new' the second son of f */ f->psx=f->ps3; f->ps3=f->ps2; f->n3=f->n2; f->ps2=new; f->n2=new->n1+new->n2; xv=f->mv; f->n1=v->n1+v->n2; f->lv=v->mv; f->mv=new->mv; xxv=max4(f); /* Call function MAX4 to obtain the maximum value ** ************ stored in the fourth subtree of f */ } else if(v==f->ps2) { /* Case v the second son of f */ /* Make 'new' the third son of f */ f->psx=f->ps3; f->ps3=new; f->n3=new->n1+new->n2; f->n2=v->n1+v->n2; f->mv=v->mv; xv=new->mv; xxv=max4(f); /* Call function MAX4 to obtain the maximum value ** ************ stored in the fourth subtree of f */ } else { /* Case v the third son of f */ /* Make 'new' the extra son of f */ f->psx=new; f->n3=v->n1+v->n2; xv=v->mv; xxv=new->mv; /* here we don't need to call 'max4' */ } addson(f,xv,xxv); /* Recurrsively call ADDSON until no father has ** ************************************* 4 sons */ } } } /* End of function addson */ /* Function: max4 ** Written by: Sherif Hashem - Purdue University - July 1990 ** Revised: May 30, 1991 ** Langauge: C ** Computer: Sun/Sparc workstations ** Purpose: To find the largest element stored in the fourth subtree ** rooted at f ** Method: The recurrent nature of MAX4 causes it to go up towards the ** root of the tree and try to make use of the information ** stored in the nodes on the way to the root (lv or mv). ** This will always result in finding the required value ** before hitting the root unless the path from f to the root ** bounds the tree from the right with all the nodes on that ** path being 3rd sons. In such case, on hitting the root, ** function AIM is called to search downwards (towards the ** leaves) for the largest element in the tree which happens ** to be the required element for this case. ** The combined effect of this search technique with the fact ** that, function MAX4 is called from function ADDSON only ** if the node that has a 4-son problem happen to be the ** 1st or the 2nd (and not the 3rd) son, causes the execution ** time per complete insertion to be O(log(m)) = O(the height ** of the tree) ** Uses: Function AIM ** Used By: Function ADDSON ** Usage: max4(f) ** Type: Float ** Argument: ** Input: f: pointer to a node ** Output: Upon RETURNing, the value of the required element is passed ** back to the calling program */ float max4(f) struct tree *f; { struct tree *arrow; float xxv; if(!f->father) { /* Case f is the root of the tree */ arrow=f->psx; /* This takes care of the initial call of MAX4 with f ** ************************ being the root of the tree */ if(!arrow) arrow=f->ps3; /* For subsequent (recurrent) calls */ if(!arrow) { puts("Error in function 'max4' \n"); exit(0); } xxv=aim(arrow); /* Once we hit the main root, function AIM is used ** ******* to find the value of the required element */ return xxv; } else { /* Case f is not the root of the tree */ arrow=f->father; if(arrow->ps1==f) return (arrow->lv); else if (arrow->ps2==f) return (arrow->mv); else if (arrow->ps3==f) return(max4(arrow)); else { puts("Error in function 'max4' \n"); exit(0); return 0; /* To avoid false compilor-warnings */ } } } /* End of function max4 */ /* Function: aim ** Written by: Sherif Hashem - Purdue University - July 1990 ** Revised: May 30, 1991 ** Langauge: C ** Computer: Sun/Sparc workstations ** Purpose: To determine the value of the maximum element in a tree ** Method: Go in the rightmost path towards the leaves ** Used By: Functions: MAX4, DEL_VER ** Usage: aim(r) ** Type: Float ** Argument: ** Input: r: pointer to the root of the tree ** Output: Upon RETURNing, the required value is passed back to the ** calling program */ float aim(r) struct tree *r; { if(!r) { puts("Error in function 'aim' \n"); exit(0); } if(r->psx != NULL) return(aim(r->psx)); else if(r->ps3 != NULL) return(aim(r->ps3)); else if(r->ps2 != NULL) return(aim(r->ps2)); else return (r->lv); /* Hit a leaf */ } /* End of function aim */ /* Function: trank ** Written by: Sherif Hashem - Purdue University - July 1990 ** Revised: May 30, 1991 ** Langauge: C ** Computer: Sun/Sparc workstations ** Purpose: Find the Kth smallest element in the tree rooted at r ** Used By: Function XTREE ** Usage: trank(k,r) ** Type: Float ** Arguments: ** Input: k: The rank of the required element ** r: root of the tree ** Output: Upon RETURNing, the value of the required element is passed ** back to the calling program */ float trank(k,r) unsigned long int k; struct tree *r; { if(!r || k < 1) { /* Input Validation */ puts(" Invalid argument(s) passed to function 'trank' \n"); exit(0); } if (r->n1 > 0) { /* Case there is more than one element in the tree */ if(k <= r->n1) return(trank(k,r->ps1)); /* Search the left subtree */ else if(k <= (r->n1 + r->n2)) /* Search the middle subtree */ return(trank((k-(r->n1)),r->ps2)); else if(k > (r->n1 + r->n2 + r->n3)) { /* Rank validation */ puts("Invalid rank in function 'trank' \n"); exit(0); return 0; /* To avoid false compilor-warnings */ } else /* Search the right subtree */ return(trank((k-(r->n1)-(r->n2)),r->ps3)); } else { /* Case there is only one element in the tree */ if(k > 1) { /* Rank validation */ puts ("Invalid rank in function 'trank'\n"); exit(0); return 0; /* To avoid false compilor-warnings */ } return (r->lv); } } /* End of function trank */ /* Function: delete ** Written by: Sherif Hashem - Purdue University - July 1990 ** Revised: May 31, 1991 ** Langauge: C ** Computer: Sun/Sparc workstations ** Purpose: Delete an element x from the tree ** Method: A special search is conducted at first to locate x and ** to update the information stored along the path leading ** to the node where x is. For this reason (updating while ** searching) it is assumed that x is pre-stored in the tree. ** This assumption saves time since separating the search ** from the updating process would result in an additional ** O(log(m)) = O(height) time. However, the function will ** detect any violation of this assumption and will report it, ** but the values stored in the nodes will be no longer correct. ** If an initial check is required, function SEARCH may ** be called just before calling function DEL_SEARCH. ** The execution time of the deletion will still be ** O(log(m))=O(height of the tree). ** After the search/update process, balancing of the tree ** is then performed. ** Uses: Functions: BACK_TRACK, DEL_SEARCH, DEL_VER, SEARCH (opt.) ** Used By: Function XTREE ** Usage: delete(x) ** Type: Void ** Argument: ** Input: x: the element to be deleted from the tree */ void delete(x) float x; { struct tree *f, *ff,*ss,*gg; float fmax; /* Maximum value in the subtree rooted at f */ if(!root) { /* When the tree is already empty */ puts(" Error in function 'delete'- Tree empty!! \n"); exit(0); } if(!root->ps1) { /* Case of only one vertex in the tree */ if(x != root->lv) { printf("That element (%f) is not in the tree !!\n",x); return; } free(root); root=NULL; return; } /* ******************************************************************** */ /* This part is OPTIONAL as stated in the heading of this function **** */ /* f=search(x,root); Search for a candidate father to 'x' */ /* if((f->lv != x) && (f->mv != x) && (!f->ps3 || (f->ps3->lv != x))) { */ /* In case no son of 'f' contains x */ /* printf("That element (%f) is not in the tree !!\n",x); */ /* return; */ /* } */ /* ******************************************************************** */ f=del_search(x,root); /* Update the tree & search for f, x's father */ if(f->n3 > 0) { /* Case 'f' has three sons */ if(f->ps1->lv==x) { /* 'x' is the first son of 'f' */ free(f->ps1); f->ps1=f->ps2; f->ps2=f->ps3; f->ps3=NULL; f->n3=0; f->lv=f->ps1->lv; f->mv=f->ps2->lv; } else if(f->ps2->lv==x) { /* 'x' is the second son of 'f' */ free(f->ps2); f->ps2=f->ps3; f->ps3=NULL; f->n3=0; f->mv=f->ps2->lv; } else if(f->ps3->lv==x) { /* 'x' is the third son of 'f' */ free(f->ps3); f->ps3=NULL; f->n3=0; fmax=f->mv; back_track(f,fmax); } else { /* Error detection */ printf("That element (%f) is not in the tree !!\n",x); return; } } else { /* Case 'f' has two sons only */ if(f==root) { /* 'f' is the root */ if(f->lv==x) { /* x is the left son of f */ f->lv=f->mv; } else if(f->mv==x){ /* x is the right son of f */ f->mv=f->lv; } else { /* Error detection */ printf("That element (%f) is not in the tree !!\n",x); return; } f->n1=0; f->n2=0; free(f->ps1); free(f->ps2); f->ps1=NULL; f->ps2=NULL; return; } else { /* Case 'f' is not the root */ ff=f->father; if(f->lv==x) { /* x is the left son of f */ ss=f->ps2; /* ss points to the son of 'f' that has to be saved */ free(f->ps1); } else if(f->mv==x) { /* x is the right son of f */ ss=f->ps1; /* ss points to the son of 'f' that has to be saved */ free(f->ps2); /* Update information about the max of the subtree rooted at f ** ***************************************** using 'back_track' */ back_track(f,ss->lv); } else { /* Error detection */ printf("That element (%f) is not in the tree !!\n",x); return; } if (f==ff->ps1) { /* Case 'f' is a first son */ gg=ff->ps2; /* 'gg' is the right brother of 'f' */ if(!gg->ps3) { /* Case 'gg' has only two sons */ gg->ps3=gg->ps2; gg->n3=1; ff->n2++; gg->ps2=gg->ps1; gg->ps1=ss; gg->mv=gg->lv; gg->lv=ss->lv; ss->father=gg; del_ver(f); /* Arrange for vertex f to be removed from the tree */ } else { /* Case 'gg' has three sons */ f->ps1=ss; f->ps2=gg->ps1; f->lv=ss->lv; f->mv=f->ps2->lv; f->ps2->father=f; gg->ps1=gg->ps2; gg->ps2=gg->ps3; gg->ps3=NULL; gg->n3=0; gg->lv=gg->mv; gg->mv=gg->ps2->lv; ff->lv=f->mv; ff->n1++; ff->n2--; } } else if(f==ff->ps2) { /* Case 'f' is the second son */ gg=ff->ps1; /* 'gg' is the left brother if 'f' */ if(gg->ps3 != NULL) { /* Case 'gg' has three sons */ f->ps1=gg->ps3; f->lv=f->ps1->lv; f->ps2=ss; f->mv=ss->lv; gg->n3=0; gg->ps3=NULL; f->ps1->father=f; ff->n1--; ff->n2++; ff->lv=gg->mv; ff->mv=f->mv; return; } if(ff->ps3 != NULL && ff->ps3->ps3 != NULL) { /* Case 'f' has a right brother having three sons */ gg=ff->ps3; /* let 'gg' be that right brother */ f->ps1=ss; f->ps2=gg->ps1; f->lv=ss->lv; f->mv=f->ps2->lv; f->ps2->father=f; gg->ps1=gg->ps2; gg->ps2=gg->ps3; gg->ps3=NULL; gg->n3=0; gg->lv=gg->mv; gg->mv=gg->ps2->lv; ff->mv=f->mv; ff->n2++; ff->n3--; return; } /* Case f has no left or right brother with three son ==> Merge f ** **************************************** and its left brother */ gg->ps3=ss; gg->n3++; ss->father=gg; ff->n1++; ff->n2--; ff->lv=ss->lv; del_ver(f); /* Arrange for vertex f to be removed from the tree */ return; } else { /* Case 'f' is the third son */ gg=ff->ps2; /* 'gg' is the left brother if 'f' */ if(gg->ps3 != NULL) { /* Case 'gg' has three sons */ f->ps1=gg->ps3; f->lv=f->ps1->lv; f->ps2=ss; f->mv=ss->lv; gg->n3=0; gg->ps3=NULL; f->ps1->father=f; ff->n2--; ff->n3++; ff->mv=gg->mv; return; } else { /* Case 'gg' has only two sons */ /* Merge f and its left brother ,gg, then remove 'f' as its ** *************************** father already has two more sons */ gg->ps3=ss; gg->n3++; ss->father=gg; ff->n2++; ff->mv=ss->lv; ff->ps3=NULL; ff->n3=0; free(f); return; } } } } } /* End of function delete */ /* Function: del_search ** Written by: Sherif Hashem - Purdue University - July 1990 ** Revised: May 30, 1991 ** Langauge: C ** Computer: Sun/Sparc workstations ** Purpose: Search the tree for the appropriate place to delete a given ** element x. Along the search path, all the relevant ** stored information that is affected by the removal of x ** from the tree is updated (Except the information about ** the maximum element which is stored along that path. ** Function BACK_TRACK will take care of that later). ** x is assumed to be in the tree. ** Used By: Function DELETE ** Usage: del_search(x,r) ** Type: Struct tree pointer ** Arguments: ** Input: x: the element to be removed from the tree ** r: root of the tree ** Output: Upon RETURNing, a pointer to the appropriate father of x is ** passed back to the calling program */ struct tree *del_search(x,r) float x; struct tree *r; { if(!(r->ps1->ps1) ) return r; /* When r is the direct father of a leaf */ else { /* When r is not a direct father of a leaf */ if(x <= r->lv) { /* Search the left subtree of r */ (r->n1) --; return(del_search(x,r->ps1)); } else { if(x <= r->mv) { /* Search the middle subtree of r */ (r->n2) --; return(del_search(x,r->ps2)); } else if(!r->ps3) { /* Error detection */ /* This Case is impossible since x must be in the tree */ puts(" Error in function 'del_search' \n"); exit(0); return NULL; /* To avoid false compilor-warnings */ } else { /* Search the right subtree of r */ (r->n3) --; return(del_search(x,r->ps3)); } } } } /* End of function del_search */ /* Function: back_track ** Written by: Sherif Hashem - Purdue University - July 1990 ** Revised: May 30, 1991 ** Langauge: C ** Computer: Sun/Sparc workstations ** Purpose: Update the information about the max element in the ** subtree rooted at f which is affected by a deletion process. ** Method: Going up towards the root, the relevant information about ** the maximum element stored along the path from f to the root ** is updated to reflect the effect of removing x from the tree ** Used By: Function DELETE ** Usage: back_track(f,fmax) ** Type: Void ** Arguments: ** Input: f: pointer to struct tree ** fmax: maximum element stored in the subtree rooted at f */ void back_track(f,fmax) struct tree *f; float fmax; { struct tree *ff; while (f->father != NULL) { /* Loop for updating the values of lv, lm */ ff=f->father; /* ff: father of 'f' */ if(ff->ps1==f) { /* Case f is the first son of ff */ ff->lv=fmax; break; /* Since for sure 'ff' has a second son and so the effect ** **** of the deletion will stop propagating at this stage */ } if(ff->ps2==f) { /* Case f is the second son of ff */ ff->mv=fmax; if(ff->ps3 != NULL) break; /* No further updating necessary */ } /* Case 'f' is the third son ==> no changes to 'ff' ==> proceed on */ f=ff; } } /* End of function back_track */ /* Function: del_ver ** Written by: Sherif Hashem - Purdue University - July 1990 ** Revised: May 31, 1991 ** Langauge: C ** Computer: Sun/Sparc workstations ** Purpose: Remove a (non-root) vertex from the tree ** Method: This removal process results during the balancing of the ** tree which occur after the deletion of an element (leaf). ** The removal of a vertex involves updating the information ** stored in its ancestors. It might also require further ** balancing by removing more and more vertices from the tree ** Uses: Function AIM ** Used By: Function DELETE ** Usage: del_ver(r) ** Type: Void ** Argument: ** Input: r: pointer to the required vertex */ void del_ver(r) struct tree *r; { struct tree *f,*ss,*ff,*gg; float ssx; unsigned long int ssn; if(!r || !(r->father)) { /* Input validation */ puts("Error in function del_ver \n"); exit(0); } f=r->father; /* 'f' is the father of 'r' */ if(f->ps3 != NULL) { /* Case 'f' has three sons */ /* ==> Remove vertex 'r' ==> Return */ if(f->ps1==r) { /* 'r' is the first son of 'f' */ f->ps1=f->ps2; f->ps2=f->ps3; f->ps3=NULL; f->lv=f->mv; f->mv=aim(f->ps2); /* To update f->mv */ f->n1=f->n2; f->n2=f->n3; f->n3=0; } else if(f->ps2==r) { /* 'r' is the second son of 'f' */ f->ps2=f->ps3; f->ps3=NULL; f->mv=aim(f->ps2); /* To update f->lm */ f->n2=f->n3; f->n3=0; } else { /* 'r' is the third son of 'f' */ f->ps3=NULL; f->n3=0; } free(r); return; } else { /* Case 'f' has only two sons */ if(f->ps1==r) { /* 'r' is the first son of 'f' */ ss=f->ps2; /* 'ss' points to the subtree to be saved */ ssx=f->mv; /* 'ssx' holds the value of the max. element in the ** ************************** subtree rooted at 'ss' */ ssn=f->n2; /* 'ssn' holds the number of leaves in the subtree rooted * ********************************************* at 'ss' */ } else { /* 'r' is the second son of 'f' */ ss=f->ps1; /* 'ss' points to the subtree to be saved */ ssx=f->lv; /* 'ssx' holds the value of the max. element in the ** ************************** subtree rooted at 'ss' */ ssn=f->n1; /* 'ssn' holds the number of leaves in the subtree rooted * ********************************************* at 'ss' */ } free(r); /* Physically remove the vertex 'r' */ if(f==root) { /* Case 'f' is the root */ free(f); root=ss; root->father=NULL; } else { /* Case 'f' is not the root */ ff=f->father; /* Let 'ff' be the father of 'f' */ if (f==ff->ps1) { /* Case 'f' is the first son */ gg=ff->ps2; /* Let'gg' be the right brother of 'f' */ if(!gg->ps3) { /* 'gg' has only two sons */ /* Give the subtree 'ss' to 'gg' and delete vertex 'f' */ gg->ps3=gg->ps2; gg->ps2=gg->ps1; gg->ps1=ss; gg->n3=gg->n2; gg->n2=gg->n1; gg->n1=ssn; gg->mv=gg->lv; gg->lv=ssx; ss->father=gg; ff->n2=gg->n1+gg->n2+gg->n3; del_ver(f); } else { /* 'gg' has three sons */ /* Move the 1st son of 'gg' to become a 2nd son of 'f' */ f->ps1=ss; f->ps2=gg->ps1; f->lv=ssx; f->mv=gg->lv; f->n1=ssn; f->n2=gg->n1; f->ps2->father=f; gg->ps1=gg->ps2; gg->ps2=gg->ps3; gg->ps3=NULL; gg->n1=gg->n2; gg->n2=gg->n3; gg->n3=0; gg->lv=gg->mv; gg->mv=aim(gg->ps2); ff->lv=f->mv; ff->n1=ssn+f->n2; ff->n2-=f->n2; } } else if(f==ff->ps2) { /* Case 'f' is the second son */ gg=ff->ps1; /* Let 'gg' be the left brother of 'f' */ if(gg->ps3 != NULL) { /* 'gg' has three sons */ /* Take the 3rd son of 'gg' to be the 1st son of 'f' */ f->ps1=gg->ps3; f->lv=ff->lv; /* same as = aim(f->ps1) */ f->n1=gg->n3; f->ps2=ss; f->mv=ssx; f->n2=ssn; gg->n3=0; gg->ps3=NULL; f->ps1->father=f; ff->lv=gg->mv; ff->mv=f->mv; ff->n1-=f->n1; ff->n2=f->n1+ssn; return; } if(ff->ps3 != NULL && ff->ps3->ps3 != NULL) { /* Case 'f' has a right brother having three sons */ gg=ff->ps3; /* Let 'gg' be that right brother */ /* Move the 1st son of 'gg' to become the 2nd son of 'f' */ f->ps1=ss; f->ps2=gg->ps1; f->lv=ssx; f->mv=gg->lv; f->n1=ssn; f->n2=gg->n1; f->ps2->father=f; gg->ps1=gg->ps2; gg->ps2=gg->ps3; gg->ps3=NULL; gg->n1=gg->n2; gg->n2=gg->n3; gg->n3=0; gg->lv=gg->mv; gg->mv=aim(gg->ps2); ff->mv=f->mv; ff->n2=ssn+f->n2; ff->n3-=f->n2; return; } /* Case f has no left or right brother with three son */ /* ==> Merge f and its left brother */ gg->ps3=ss; gg->n3=ssn; ff->lv=ssx; ff->n1+=ssn; ff->n2=0; ss->father=gg; del_ver(f); return; } else { /* Case 'f' is the third son */ gg=ff->ps2; /* 'gg' is the left brother of 'f' */ if(gg->ps3 != NULL) { /* 'gg' has three sons */ /* Move the 3rd son of 'gg' to be the 1st son of 'f' */ f->ps1=gg->ps3; f->lv=ff->mv; f->ps2=ss; f->mv=ssx; f->n1=gg->n3; f->n2=ssn; gg->n3=0; gg->ps3=NULL; f->ps1->father=f; ff->n2-=f->n1; ff->n3=f->n1+ssn; ff->mv=gg->mv; return; } else { /* 'gg' has only two sons */ /* Merge f and its left brother then remove 'f' as its father ** ******************************** already has two more sons */ gg->ps3=ss; gg->n3=ssn; ss->father=gg; ff->n2+=ssn; ff->mv=ssx; ff->ps3=NULL; ff->n3=0; free(f); return; } } } } } /* End of function del_ver */ /* Function: search ** Written by: Sherif Hashem - Purdue University - May 31, 1991 ** Revised: May 31, 1991 ** Langauge: C ** Computer: Sun/Sparc workstations ** Purpose: Check the membership of a given element x in the tree rooted ** at r ** Used By: Function DELETE (optional) ** Usage: search(x,r) ** Type: Struct tree pointer ** Arguments: ** Input: x: the element to be removed from the tree ** r: root of the tree ** Output: Upon RETURNing, a value of zero is passed to back to the ** calling program if x is not in the tree */ struct tree *search(x,r) float x; struct tree *r; { if(!(r->ps1->ps1) ) return r; /* When r is the direct father of a leaf */ else { /* When r is not a direct father of a leaf */ if(x <= r->lv) return(search(x,r->ps1)); /* Search the left subtree of r */ else if(x <= r->mv || !r->ps3) return(search(x,r->ps2)); /* Search the middle subtree of r */ else return(search(x,r->ps3)); /* Search the right subtree of r */ } } /* End of function search */