| /* |
| * Some basic 2-3 tree functions: |
| * 1. tinsert( &root , value , property ) ; |
| * TNODEPTR root ; |
| * int value , property ; |
| * |
| * 2. tdelete( &root , value , property ) ; |
| * TNODEPTR root ; |
| * int value , property ; |
| * |
| * 3. tpop( &root , &node , &value , &property ) ; |
| * TNODEPTR root , node ; |
| * int value , property ; |
| * |
| * 4. ttrim( &root , threshold ) ; |
| * TNODEPTR root ; |
| * int threshold ; |
| * |
| * 5. tprint( root ) ; |
| * TNODEPTR root ; |
| * |
| * 6. tdiscard( root , count ) |
| * TNODEPTR *root ; |
| * int count ; |
| * |
| * 7. int tprop( r , value ) --- returns FIRST property |
| * TNODEPTR r ; associated with: value of |
| * int value ; tree with root: r --- |
| * |
| * 8. PLISTPTR tplist( r , value ) ---- return ptr to FIRST |
| * TNODEPTR r ; property associated with |
| * int value ; value of tree with root r. |
| * |
| * To use the 2-3 tree implementation, compile the file: 23tree.c |
| * with your source files and include the line: #include "23tree.h" |
| * in any of your source files which use the 2-3 tree functions. |
| * You may have several 2-3 trees active at once. Each tree must |
| * given a "root", whose type is necessarily: TNODEPTR. That is, |
| * if you want 3 trees to be active, you must declare 3 roots in |
| * the following fashion: |
| * TNODEPTR root1 , root2 , root3 ; |
| * Finally, before you can use any of the functions, you must |
| * initialize the roots to NULL, as follows: |
| * root1 = (TNODEPTR) NULL ; |
| * root2 = (TNODEPTR) NULL ; |
| * root3 = (TNODEPTR) NULL ; |
| */ |
| #include "23tree.h" |
| |
| void tdump( TNODEPTR node ); |
| void tdelete( TNODEPTR *root , int value , int property ); |
| void tpatch( TNODEPTR v , int value ); |
| void makenode( TNODEPTR *v , int value , int property ); |
| void addplist( TNODEPTR v , int property ); |
| void tsubson( TNODEPTR *root , TNODEPTR l ); |
| |
| |
| void tprint( TNODEPTR v ) |
| { |
| |
| int qbot , qtop ; |
| TNODEPTR node , *q , f ; |
| |
| if( v == (TNODEPTR) NULL ) { |
| return ; |
| } |
| qtop = 0 ; |
| qbot = 0 ; |
| q = (TNODEPTR *) malloc( 10001 * sizeof(TNODEPTR) ) ; |
| q[0] = v ; |
| while( qtop >= qbot ) { |
| tdump( node = q[qbot++] ) ; |
| if( node != v ) { |
| f = node->father ; |
| if( f->son1 != node && f->son2 != node && f->son3 != node ) { |
| printf("Error Type 1\n"); |
| } |
| if( node->nsons != 0 ) { |
| if( node->son1->father->Lval != node->Lval ) { |
| printf("Error Type 2\n"); |
| } |
| if( node->son1->father->Mval != node->Mval ) { |
| printf("Error Type 3\n"); |
| } |
| } |
| } |
| if( node->nsons > 0 ) { |
| q[++qtop] = node->son1 ; |
| q[++qtop] = node->son2 ; |
| if( node->son3 != (TNODEPTR) NULL ) { |
| q[++qtop] = node->son3 ; |
| } |
| } |
| } |
| free(q) ; |
| /* |
| tmin( v, &node, &value, &property ); |
| printf("\n\nMinimum Tree Value: %d\n", value ); |
| */ |
| return ; |
| } |
| |
| |
| void tdump( TNODEPTR node ) |
| { |
| |
| PLISTPTR plptr ; |
| |
| printf("\n"); |
| if( node->nsons == 0 ) { |
| printf("value: %d ", node->value ); |
| plptr = node->plist ; |
| for( ; plptr != (PLISTPTR) NULL; plptr = plptr->pnext ) { |
| printf("%d ", plptr->property ) ; |
| } |
| printf("\n"); |
| } else{ |
| /* printf("Lval: %d Mval: %d\n", node->Lval , node->Mval ); |
| */ |
| } |
| return ; |
| } |
| |
| |
| |
| void tmin( TNODEPTR root , TNODEPTR *node , int *value , int *property ) |
| { |
| |
| TNODEPTR v ; |
| |
| v = root ; |
| if( v == (TNODEPTR) NULL ) { |
| *node = (TNODEPTR) NULL ; |
| } else { |
| while( v->son1 != (TNODEPTR) NULL ) { |
| v = v->son1 ; |
| } |
| *node = v ; |
| *value = v->value ; |
| *property = v->plist->property ; |
| } |
| |
| return; |
| } |
| |
| |
| |
| void tpop( TNODEPTR *root , TNODEPTR *node , int *value , int *property ) |
| { |
| |
| TNODEPTR v ; |
| |
| v = *root ; |
| if( v == (TNODEPTR) NULL ) { |
| *node = (TNODEPTR) NULL ; |
| } else { |
| while( v->son1 != (TNODEPTR) NULL ) { |
| v = v->son1 ; |
| } |
| *node = v ; |
| *value = v->value ; |
| *property = v->plist->property ; |
| tdelete( root , *value , *property ) ; |
| } |
| |
| return; |
| } |
| |
| |
| |
| void tmax( TNODEPTR *root , TNODEPTR *node , int *value , int *property ) |
| { |
| |
| TNODEPTR v ; |
| |
| v = *root ; |
| if( v == (TNODEPTR) NULL ) { |
| *node = (TNODEPTR) NULL ; |
| } else { |
| for( ; ; ) { |
| if( v->nsons == 3 ) { |
| v = v->son3 ; |
| } else if( v->nsons == 2 ) { |
| v = v->son2 ; |
| } else { |
| break ; |
| } |
| } |
| *node = v ; |
| *value = v->value ; |
| *property = v->plist->property ; |
| } |
| |
| return; |
| } |
| |
| |
| |
| void ttrim( TNODEPTR *root , int threshold ) |
| { |
| |
| TNODEPTR node ; |
| int property , value ; |
| |
| for( ; ; ) { |
| tmax( root , &node , &value , &property ) ; |
| if( node == (TNODEPTR) NULL ) { |
| break ; |
| } else if( value < threshold ) { |
| break ; |
| } else { |
| tdelete( root , value , property ) ; |
| } |
| } |
| |
| return; |
| } |
| |
| |
| |
| |
| void tdiscard( TNODEPTR *root , int count ) |
| { |
| |
| TNODEPTR node ; |
| int property , value , i ; |
| |
| for( i = 1 ; i <= count ; i++ ) { |
| tmax( root , &node , &value , &property ) ; |
| if( node == (TNODEPTR) NULL ) { |
| break ; |
| } else { |
| tdelete( root , value , property ) ; |
| } |
| } |
| return; |
| } |
| |
| |
| |
| |
| TNODEPTR tsearch( int val , TNODEPTR r ) |
| { |
| |
| if( r->son1->nsons == 0 ) { |
| return( r ) ; |
| } else { |
| if( val <= r->Lval ) { |
| return( tsearch( val , r->son1 ) ) ; |
| } else if( r->nsons == 2 || val <= r->Mval ) { |
| return( tsearch( val , r->son2 ) ) ; |
| } else { |
| return( tsearch( val , r->son3 ) ) ; |
| } |
| } |
| } |
| |
| |
| void taddson( TNODEPTR *root , TNODEPTR r ) |
| { |
| |
| TNODEPTR v , nr , f ; |
| |
| v = (TNODEPTR) malloc( sizeof( TNODE ) ) ; |
| v->son1 = r->son3 ; |
| v->son2 = r->son4 ; |
| v->son3 = (TNODEPTR) NULL ; |
| v->son4 = (TNODEPTR) NULL ; |
| v->father = r->father ; |
| v->nsons = 2 ; |
| r->nsons = 2 ; |
| r->son3 = (TNODEPTR) NULL ; |
| r->son4 = (TNODEPTR) NULL ; |
| v->son1->father = v ; |
| v->son2->father = v ; |
| |
| f = r->son1 ; |
| while( f->nsons == 3 ) { |
| f = f->son3 ; |
| } |
| if( f->nsons == 0 ) { |
| r->Lval = f->value ; |
| } else { |
| r->Lval = f->Mval ; |
| } |
| f = r->son2 ; |
| while( f->nsons == 3 ) { |
| f = f->son3 ; |
| } |
| if( f->nsons == 0 ) { |
| r->Mval = f->value ; |
| } else { |
| r->Mval = f->Mval ; |
| } |
| f = v->son1 ; |
| while( f->nsons == 3 ) { |
| f = f->son3 ; |
| } |
| if( f->nsons == 0 ) { |
| v->Lval = f->value ; |
| } else { |
| v->Lval = f->Mval ; |
| } |
| f = v->son2 ; |
| while( f->nsons == 3 ) { |
| f = f->son3 ; |
| } |
| if( f->nsons == 0 ) { |
| v->Mval = f->value ; |
| } else { |
| v->Mval = f->Mval ; |
| } |
| |
| if( r->father == (TNODEPTR) NULL ) { |
| nr = (TNODEPTR) malloc( sizeof( TNODE ) ) ; |
| nr->son1 = r ; |
| nr->son2 = v ; |
| nr->son3 = (TNODEPTR) NULL ; |
| nr->son4 = (TNODEPTR) NULL ; |
| nr->father = (TNODEPTR) NULL ; |
| nr->nsons = 2 ; |
| r->father = nr ; |
| v->father = nr ; |
| nr->Lval = r->Mval ; |
| nr->Mval = v->Mval ; |
| *root = nr ; |
| } else { |
| f = r->father ; |
| if( ++f->nsons == 4 ) { |
| if( f->son1 == r ) { |
| f->son4 = f->son3 ; |
| f->son3 = f->son2 ; |
| f->son2 = v ; |
| } else if( f->son2 == r ) { |
| f->son4 = f->son3 ; |
| f->son3 = v ; |
| } else { |
| f->son4 = v ; |
| } |
| taddson( root , f ) ; |
| } else { |
| if( f->son1 == r ) { |
| f->son3 = f->son2 ; |
| f->son2 = v ; |
| f->Lval = r->Mval ; |
| f->Mval = v->Mval ; |
| } else { |
| f->son3 = v ; |
| f->Mval = r->Mval ; |
| tpatch( f , v->Mval ) ; |
| } |
| } |
| } |
| return ; |
| } |
| |
| |
| |
| |
| |
| void tinsert( TNODEPTR *root , int value , int property ) |
| { |
| |
| TNODEPTR v , nr , f , node ; |
| |
| if( *root == (TNODEPTR) NULL ) { |
| makenode( &v , value , property ) ; |
| v->father = (TNODEPTR) NULL ; |
| *root = v ; |
| } else if( (*root)->nsons == 0 ) { |
| if( (*root)->value == value ) { |
| addplist( *root , property ) ; |
| } else { |
| makenode( &v , value , property ) ; |
| nr = (TNODEPTR) malloc( sizeof( TNODE ) ) ; |
| if( value <= (*root)->value ) { |
| nr->Lval = value ; |
| nr->Mval = (*root)->value ; |
| nr->son1 = v ; |
| nr->son2 = *root ; |
| nr->son3 = (TNODEPTR) NULL ; |
| nr->son4 = (TNODEPTR) NULL ; |
| } else { |
| nr->Mval = value ; |
| nr->Lval = (*root)->value ; |
| nr->son1 = *root ; |
| nr->son2 = v ; |
| nr->son3 = (TNODEPTR) NULL ; |
| nr->son4 = (TNODEPTR) NULL ; |
| } |
| nr->father = (TNODEPTR) NULL ; |
| nr->nsons = 2 ; |
| (*root)->father = nr ; |
| v->father = nr ; |
| *root = nr ; |
| } |
| } else { |
| f = tsearch( value , *root ) ; |
| node = tfind( value , f ) ; |
| if( node != (TNODEPTR) NULL ) { |
| addplist( node , property ) ; |
| } else { |
| makenode( &v , value , property ) ; |
| if( f->nsons == 2 ) { |
| if( value <= f->son1->value ) { |
| f->son3 = f->son2 ; |
| f->son2 = f->son1 ; |
| f->son1 = v ; |
| f->Mval = f->Lval ; |
| f->Lval = value ; |
| } else if( value <= f->son2->value ) { |
| f->son3 = f->son2 ; |
| f->son2 = v ; |
| f->Mval = value ; |
| } else { |
| f->son3 = v ; |
| tpatch( f , value ) ; |
| } |
| f->nsons = 3 ; |
| v->father = f ; |
| } else { |
| if( value <= f->son1->value ) { |
| f->son4 = f->son3 ; |
| f->son3 = f->son2 ; |
| f->son2 = f->son1 ; |
| f->son1 = v ; |
| } else if( value <= f->son2->value ) { |
| f->son4 = f->son3 ; |
| f->son3 = f->son2 ; |
| f->son2 = v ; |
| } else if( value <= f->son3->value ) { |
| f->son4 = f->son3 ; |
| f->son3 = v ; |
| } else { |
| f->son4 = v ; |
| } |
| v->father = f ; |
| taddson( root , f ) ; |
| } |
| } |
| } |
| return ; |
| } |
| |
| |
| |
| void tpatch( TNODEPTR v , int value ) |
| { |
| |
| TNODEPTR f ; |
| |
| f = v->father ; |
| if( f != (TNODEPTR) NULL ) { |
| if( f->son1 == v ) { |
| f->Lval = value ; |
| } else if( f->son2 == v ) { |
| f->Mval = value ; |
| if( f->son3 == (TNODEPTR) NULL ) { |
| tpatch( f , value ) ; |
| } |
| } else { |
| tpatch( f , value ) ; |
| } |
| } |
| return ; |
| } |
| |
| |
| |
| |
| void tdelete( TNODEPTR *root , int value , int property ) |
| { |
| |
| TNODEPTR f , l , g , s ; |
| PLISTPTR plptr , prevptr ; |
| |
| if( *root == (TNODEPTR) NULL ) { |
| } else if( (*root)->nsons == 0 ) { |
| plptr = pfind( *root , property , &prevptr ) ; |
| if( plptr != (PLISTPTR) NULL ) { |
| if( prevptr != (PLISTPTR) NULL ) { |
| prevptr->pnext = plptr->pnext ; |
| free( plptr ) ; |
| } else if( plptr->pnext != (PLISTPTR) NULL ) { |
| (*root)->plist = plptr->pnext ; |
| free( plptr ) ; |
| } else { |
| free( plptr ) ; |
| free( *root ) ; |
| *root = (TNODEPTR) NULL ; |
| } |
| } |
| } else { |
| l = tdsearch( value , *root ) ; |
| if( l != (TNODEPTR) NULL ) { |
| plptr = pfind( l , property , &prevptr ) ; |
| if( plptr != (PLISTPTR) NULL ) { |
| if( prevptr != (PLISTPTR) NULL ) { |
| prevptr->pnext = plptr->pnext ; |
| free( plptr ) ; |
| } else if( plptr->pnext != (PLISTPTR) NULL ) { |
| l->plist = plptr->pnext ; |
| free( plptr ) ; |
| } else { |
| free( plptr ) ; |
| f = l->father ; |
| if( f->nsons == 3 ) { |
| if( f->son1 == l ) { |
| f->son1 = f->son2 ; |
| f->son2 = f->son3 ; |
| f->son3 = (TNODEPTR) NULL ; |
| f->Lval = f->son1->value ; |
| f->Mval = f->son2->value ; |
| } else if( f->son2 == l ) { |
| f->son2 = f->son3 ; |
| f->son3 = (TNODEPTR) NULL ; |
| f->Mval = f->son2->value ; |
| } else { |
| f->son3 = (TNODEPTR) NULL ; |
| tpatch( f , value ) ; |
| } |
| free( l ) ; |
| f->nsons = 2 ; |
| } else { |
| if( f == *root ) { |
| if( (*root)->son1 == l ) { |
| (*root)->value = (*root)->son2->value ; |
| (*root)->plist = (*root)->son2->plist ; |
| } else { |
| (*root)->value = (*root)->son1->value ; |
| (*root)->plist = (*root)->son1->plist ; |
| } |
| free( (*root)->son1 ) ; |
| free( (*root)->son2 ) ; |
| (*root)->son1 = (TNODEPTR) NULL ; |
| (*root)->son2 = (TNODEPTR) NULL ; |
| (*root)->nsons = 0 ; |
| } else { |
| if( f->son1 == l ) { |
| s = f->son2 ; |
| } else { |
| s = f->son1 ; |
| } |
| if( f->father->son1 == f ) { |
| g = f->father->son2 ; |
| if( f->father->nsons == 2 ) { |
| if( g->nsons == 2 ) { |
| g->nsons = 3 ; |
| g->son3 = g->son2 ; |
| g->son2 = g->son1 ; |
| g->son1 = s ; |
| s->father = g ; |
| free( l ) ; |
| g->Lval = s->value ; |
| g->Mval = g->son2->value ; |
| tsubson( root , f ) ; |
| } else { |
| g->nsons = 2 ; |
| f->son1 = s ; |
| f->son2 = g->son1 ; |
| g->son1 = g->son2 ; |
| g->son2 = g->son3 ; |
| f->son2->father = f ; |
| g->son3 = (TNODEPTR) NULL ; |
| f->Lval = s->value ; |
| f->Mval = f->son2->value ; |
| g->Lval = g->son1->value ; |
| g->Mval = g->son2->value ; |
| g->father->Lval = f->Mval ; |
| free( l ) ; |
| } |
| } else { |
| if( g->nsons == 2 ) { |
| g->nsons = 3 ; |
| g->son3 = g->son2 ; |
| g->son2 = g->son1 ; |
| g->son1 = s ; |
| s->father = g ; |
| free( l ) ; |
| g->Lval = s->value ; |
| g->Mval = g->son2->value ; |
| f->father->son1 = f->father->son2 ; |
| f->father->son2 = f->father->son3 ; |
| f->father->son3 = (TNODEPTR) NULL ; |
| f->father->nsons = 2 ; |
| f->father->Lval = f->father->Mval ; |
| if( f->father->son2->nsons == 2 ) { |
| f->father->Mval = |
| f->father->son2->Mval ; |
| } else { |
| f->father->Mval = |
| f->father->son2->son3->value ; |
| } |
| free( f ) ; |
| } else { |
| g->nsons = 2 ; |
| f->son1 = s ; |
| f->son2 = g->son1 ; |
| g->son1 = g->son2 ; |
| g->son2 = g->son3 ; |
| f->son2->father = f ; |
| g->son3 = (TNODEPTR) NULL ; |
| f->Lval = s->value ; |
| f->Mval = f->son2->value ; |
| g->Lval = g->son1->value ; |
| g->Mval = g->son2->value ; |
| g->father->Lval = f->Mval ; |
| free( l ) ; |
| } |
| } |
| } else if( f->father->son2 == f ) { |
| if( f->father->nsons == 2 ) { |
| g = f->father->son1 ; |
| if( g->nsons == 2 ) { |
| g->nsons = 3 ; |
| g->son3 = s ; |
| s->father = g ; |
| free( l ) ; |
| f->father->Lval = s->value ; |
| tsubson( root , f ) ; |
| } else { |
| g->nsons = 2 ; |
| f->son1 = g->son3 ; |
| f->son2 = s ; |
| f->son1->father = f ; |
| g->son3 = (TNODEPTR) NULL ; |
| f->Lval = f->son1->value ; |
| f->Mval = s->value ; |
| f->father->Lval = g->Mval ; |
| f->father->Mval = f->Mval ; |
| tpatch( f->father , f->Mval ) ; |
| free( l ) ; |
| } |
| } else { |
| g = f->father->son3 ; |
| if( g->nsons == 2 ) { |
| g->nsons = 3 ; |
| g->son3 = g->son2 ; |
| g->son2 = g->son1 ; |
| g->son1 = s ; |
| s->father = g ; |
| free( l ) ; |
| g->Lval = s->value ; |
| g->Mval = g->son2->value ; |
| g->father->Mval = g->son3->value ; |
| free( f ) ; |
| g->father->son2 = g->father->son3 ; |
| g->father->son3 = (TNODEPTR) NULL ; |
| g->father->nsons = 2 ; |
| } else { |
| g->nsons = 2 ; |
| f->son1 = s ; |
| f->son2 = g->son1 ; |
| f->son2->father = f ; |
| g->son1 = g->son2 ; |
| g->son2 = g->son3 ; |
| g->son3 = (TNODEPTR) NULL ; |
| g->Lval = g->son1->value ; |
| g->Mval = g->son2->value ; |
| f->Lval = f->son1->value ; |
| f->Mval = f->son2->value ; |
| f->father->Mval = f->Mval ; |
| free( l ) ; |
| } |
| } |
| } else { |
| g = f->father->son2 ; |
| if( g->nsons == 2 ) { |
| g->nsons = 3 ; |
| g->son3 = s ; |
| s->father = g ; |
| free( l ) ; |
| g->father->Mval = s->value ; |
| tpatch( g->father , s->value ) ; |
| g->father->son3 = (TNODEPTR) NULL ; |
| g->father->nsons = 2 ; |
| free( f ) ; |
| } else { |
| g->nsons = 2 ; |
| f->son1 = g->son3 ; |
| f->son2 = s ; |
| f->son1->father = f ; |
| g->son3 = (TNODEPTR) NULL ; |
| f->Lval = f->son1->value ; |
| f->Mval = s->value ; |
| g->father->Mval = g->Mval ; |
| tpatch( f->father , s->value ) ; |
| free( l ) ; |
| } |
| } |
| } |
| } |
| } |
| } |
| } |
| } |
| return ; |
| } |
| |
| |
| void tsubson( TNODEPTR *root , TNODEPTR l ) |
| { |
| |
| TNODEPTR f , s , g ; |
| int LMval ; |
| |
| f = l->father ; |
| if( f == *root ) { |
| if( (*root)->son1 == l ) { |
| s = (*root)->son2 ; |
| } else { |
| s = (*root)->son1 ; |
| } |
| s->father = (TNODEPTR) NULL ; |
| free( l ) ; |
| free( *root ) ; |
| *root = s ; |
| } else { |
| if( f->son1 == l ) { |
| s = f->son2 ; |
| LMval = f->Mval ; |
| } else { |
| s = f->son1 ; |
| LMval = f->Lval ; |
| } |
| if( f->father->son1 == f ) { |
| g = f->father->son2 ; |
| if( f->father->nsons == 2 ) { |
| if( g->nsons == 2 ) { |
| g->nsons = 3 ; |
| g->son3 = g->son2 ; |
| g->son2 = g->son1 ; |
| g->son1 = s ; |
| s->father = g ; |
| free( l ) ; |
| g->Mval = g->Lval ; |
| g->Lval = LMval ; |
| tsubson( root , f ) ; |
| } else { |
| g->nsons = 2 ; |
| f->son1 = s ; |
| f->son2 = g->son1 ; |
| g->son1 = g->son2 ; |
| g->son2 = g->son3 ; |
| f->son2->father = f ; |
| g->son3 = (TNODEPTR) NULL ; |
| f->Lval = LMval ; |
| f->Mval = g->Lval ; |
| g->Lval = g->Mval ; |
| g->Mval = g->father->Mval ; |
| g->father->Lval = f->Mval ; |
| free( l ) ; |
| } |
| } else { |
| if( g->nsons == 2 ) { |
| g->nsons = 3 ; |
| g->son3 = g->son2 ; |
| g->son2 = g->son1 ; |
| g->son1 = s ; |
| s->father = g ; |
| free( l ) ; |
| g->Mval = g->Lval ; |
| g->Lval = LMval ; |
| f->father->son1 = f->father->son2 ; |
| f->father->son2 = f->father->son3 ; |
| f->father->son3 = (TNODEPTR) NULL ; |
| f->father->nsons = 2 ; |
| f->father->Lval = f->father->Mval ; |
| free( f ) ; |
| f = g->father->son2 ; |
| while( f->nsons == 3 ) { |
| f = f->son3 ; |
| } |
| if( f->nsons == 0 ) { |
| g->father->Mval = f->value ; |
| } else { |
| g->father->Mval = f->Mval ; |
| } |
| } else { |
| g->nsons = 2 ; |
| f->son1 = s ; |
| f->son2 = g->son1 ; |
| g->son1 = g->son2 ; |
| g->son2 = g->son3 ; |
| f->son2->father = f ; |
| g->son3 = (TNODEPTR) NULL ; |
| f->Lval = LMval ; |
| f->Mval = g->Lval ; |
| g->Lval = g->Mval ; |
| g->Mval = g->father->Mval ; |
| g->father->Lval = f->Mval ; |
| free( l ) ; |
| } |
| } |
| } else if( f->father->son2 == f ) { |
| if( f->father->nsons == 2 ) { |
| g = f->father->son1 ; |
| if( g->nsons == 2 ) { |
| g->nsons = 3 ; |
| g->son3 = s ; |
| s->father = g ; |
| free( l ) ; |
| f->father->Lval = LMval ; |
| tsubson( root , f ) ; |
| } else { |
| g->nsons = 2 ; |
| f->son1 = g->son3 ; |
| f->son2 = s ; |
| f->son1->father = f ; |
| g->son3 = (TNODEPTR) NULL ; |
| f->Lval = g->father->Lval ; |
| f->Mval = LMval ; |
| g->father->Lval = g->Mval ; |
| g->father->Mval = LMval ; |
| tpatch( f->father , f->Mval ) ; |
| free( l ) ; |
| } |
| } else { |
| g = f->father->son3 ; |
| if( g->nsons == 2 ) { |
| g->nsons = 3 ; |
| g->son3 = g->son2 ; |
| g->son2 = g->son1 ; |
| g->son1 = s ; |
| s->father = g ; |
| free( l ) ; |
| g->father->Mval = g->Mval ; |
| g->Mval = g->Lval ; |
| g->Lval = LMval ; |
| free( f ) ; |
| g->father->son2 = g->father->son3 ; |
| g->father->son3 = (TNODEPTR) NULL ; |
| g->father->nsons = 2 ; |
| } else { |
| g->nsons = 2 ; |
| f->son1 = s ; |
| f->son2 = g->son1 ; |
| f->son2->father = f ; |
| g->son1 = g->son2 ; |
| g->son2 = g->son3 ; |
| g->son3 = (TNODEPTR) NULL ; |
| f->Lval = LMval ; |
| f->Mval = g->Lval ; |
| g->Lval = g->Mval ; |
| g->father->Mval = f->Mval ; |
| f = g->son2 ; |
| while( f->nsons == 3 ) { |
| f = f->son3 ; |
| } |
| if( f->nsons == 0 ) { |
| g->Mval = f->value ; |
| } else { |
| g->Mval = f->Mval ; |
| } |
| free( l ) ; |
| } |
| } |
| } else { |
| g = f->father->son2 ; |
| if( g->nsons == 2 ) { |
| g->nsons = 3 ; |
| g->son3 = s ; |
| s->father = g ; |
| free( l ) ; |
| g->father->Mval = LMval ; |
| tpatch( g->father , LMval ) ; |
| g->father->son3 = (TNODEPTR) NULL ; |
| g->father->nsons = 2 ; |
| free( f ) ; |
| } else { |
| g->nsons = 2 ; |
| f->son1 = g->son3 ; |
| f->son2 = s ; |
| f->son1->father = f ; |
| g->son3 = (TNODEPTR) NULL ; |
| f->Lval = g->father->Mval ; |
| f->Mval = LMval ; |
| g->father->Mval = g->Mval ; |
| tpatch( f->father , LMval ) ; |
| free( l ) ; |
| } |
| } |
| } |
| return ; |
| } |
| |
| |
| |
| TNODEPTR tdsearch( int value , TNODEPTR r ) |
| { |
| |
| if( r == (TNODEPTR) NULL ) { |
| return( (TNODEPTR) NULL ) ; |
| } else if( r->nsons == 0 ) { |
| return( r ) ; |
| } else { |
| if( value <= r->Lval ) { |
| return( tdsearch( value , r->son1 ) ) ; |
| } else if( value <= r->Mval ) { |
| return( tdsearch( value , r->son2 ) ) ; |
| } else { |
| return( tdsearch( value , r->son3 ) ) ; |
| } |
| } |
| } |
| |
| |
| TNODEPTR tfind( int value , TNODEPTR r ) |
| { |
| |
| if( r->son1->value == value ) { |
| return( r->son1 ) ; |
| } else if( r->son2->value == value ) { |
| return( r->son2 ) ; |
| } else if( r->nsons == 3 ) { |
| if( r->son3->value == value ) { |
| return( r->son3 ) ; |
| } |
| } |
| return( (TNODEPTR) NULL ) ; |
| } |
| |
| |
| |
| void makenode( TNODEPTR *v , int value , int property ) |
| { |
| *v = (TNODEPTR) malloc( sizeof( TNODE ) ) ; |
| (*v)->son1 = (TNODEPTR) NULL ; |
| (*v)->son2 = (TNODEPTR) NULL ; |
| (*v)->son3 = (TNODEPTR) NULL ; |
| (*v)->son4 = (TNODEPTR) NULL ; |
| (*v)->value = value ; |
| (*v)->nsons = 0 ; |
| (*v)->plist = (PLISTPTR) malloc( sizeof( PLIST ) ) ; |
| (*v)->plist->property = property ; |
| (*v)->plist->pnext = (PLISTPTR) NULL ; |
| |
| return ; |
| } |
| |
| |
| |
| void addplist( TNODEPTR v , int property ) |
| { |
| |
| PLISTPTR plptr ; |
| |
| plptr = (PLISTPTR) malloc( sizeof( PLIST ) ) ; |
| plptr->pnext = v->plist ; |
| v->plist = plptr ; |
| v->plist->property = property ; |
| |
| return ; |
| } |
| |
| |
| |
| PLISTPTR pfind( TNODEPTR v , int property , PLISTPTR *prevptr ) |
| { |
| |
| PLISTPTR plptr ; |
| |
| *prevptr = (PLISTPTR) NULL ; |
| plptr = v->plist ; |
| while( plptr != (PLISTPTR) NULL ) { |
| if( plptr->property == property ) { |
| return( plptr ) ; |
| } |
| *prevptr = plptr ; |
| plptr = plptr->pnext ; |
| } |
| |
| return( (PLISTPTR) NULL ) ; |
| } |
| |
| |
| |
| int tprop( TNODEPTR r , int value ) |
| { |
| |
| TNODEPTR v , f ; |
| |
| if( r == (TNODEPTR) NULL ) { |
| return( -1 ) ; |
| } else if( r->nsons == 0 ) { |
| if( r->value == value ) { |
| return( r->plist->property ) ; |
| } else { |
| return( -1 ) ; |
| } |
| } else { |
| f = tsearch( value , r ) ; |
| if( f == (TNODEPTR) NULL ) { |
| return( -1 ) ; |
| } else { |
| v = tfind( value , f ) ; |
| if( v == (TNODEPTR) NULL ) { |
| return( -1 ) ; |
| } else { |
| return( v->plist->property ) ; |
| } |
| } |
| } |
| } |
| |
| |
| |
| PLISTPTR tplist( TNODEPTR r , int value ) |
| { |
| |
| TNODEPTR v , f ; |
| |
| if( r == (TNODEPTR) NULL ) { |
| return( (PLISTPTR) NULL ) ; |
| } else if( r->nsons == 0 ) { |
| if( r->value == value ) { |
| return( r->plist ) ; |
| } else { |
| return( (PLISTPTR) NULL ) ; |
| } |
| } else { |
| f = tsearch( value , r ) ; |
| if( f == (TNODEPTR) NULL ) { |
| return( (PLISTPTR) NULL ) ; |
| } else { |
| v = tfind( value , f ) ; |
| if( v == (TNODEPTR) NULL ) { |
| return( (PLISTPTR) NULL ) ; |
| } else { |
| return( v->plist ) ; |
| } |
| } |
| } |
| } |