#include #include enum {RED, BLACK}; typedef struct element { int br; int boja; struct element *l, *d, *r; } cvor; //2Д приказ стабла void razmak( char c, int n ) { while ( n -- ) putchar( c ); } void vizuelniPrikaz_( cvor *koren, int nivo ) { if ( !koren ) { razmak('\t', nivo ); puts("~"); } else { vizuelniPrikaz_( koren -> d, nivo + 1 ); razmak('\t', nivo ); printf("%d %c\n", koren -> br, koren -> boja == RED ? 'R' : 'B' ); vizuelniPrikaz_( koren -> l, nivo + 1 ); } } void vizuelniPrikaz( cvor *koren ) { vizuelniPrikaz_( koren, 0 ); } cvor *noviCvor( int x ) { cvor *novi = ( cvor * ) malloc( sizeof( cvor ) ); novi -> br = x; novi -> boja = RED; novi -> l = novi -> d = novi -> r = NULL; return novi; } void levaRotacija( cvor **koren ) { cvor *x = *koren; cvor *y = x -> d; x -> d = y -> l; if( y -> l ) y -> l -> r = x; y -> r = x -> r; if( x -> r ) if( x == x -> r -> l ) x -> r -> l = y; else x -> r -> d = y; y -> l = x; x -> r = *koren = y; } void desnaRotacija( cvor **koren ) { cvor *x = *koren; cvor *y = x -> l; x -> l = y -> d; if( y -> d ) y -> d -> r = x; y -> r = x -> r; if( x -> r ) if( x == x -> r -> d ) x -> r -> d = y; else x -> r -> l = y; y -> d = x; x -> r = *koren = y; } void fix( cvor **koren, cvor *c ) { cvor *ujak, *deda; while( c -> r && c -> r -> boja == RED ) { if( c -> r == c -> r -> r -> l ) { ujak = c -> r -> r -> d; if( ujak && ujak -> boja == RED ) { c -> r -> boja = ujak -> boja = BLACK; ujak -> r -> boja = RED; c = c -> r -> r; } else { if( c == c -> r -> d ) { c = c -> r; levaRotacija( &c ); if( !c -> r ) *koren = c; c = c -> l; } c -> r -> boja = BLACK; c -> r -> r -> boja = RED; deda = c -> r -> r; desnaRotacija( &deda ); if( !deda -> r ) *koren = deda; } } else { ujak = c -> r -> r -> l; if( ujak && ujak -> boja == RED ) { c -> r -> boja = ujak -> boja = BLACK; ujak -> r -> boja = RED; c = c -> r -> r; } else { if( c == c -> r -> l ) { c = c -> r; desnaRotacija( &c ); if( !c -> r ) *koren = c; c = c -> d; } c -> r -> boja = BLACK; c -> r -> r -> boja = RED; deda = c -> r -> r; levaRotacija( &deda ); if( !deda -> r ) *koren = deda; } } } ( *koren ) -> boja = BLACK; } void dodaj( cvor **koren, int x ) { cvor *c = noviCvor( x ); cvor *t = *koren; cvor *r = NULL; while( t ) { r = t; if( x < t -> br ) t = t -> l; else t = t -> d; } c -> r = r; if( !r ) *koren = c; else if( x < r -> br ) r -> l = c; else r -> d = c; fix( koren, c ); } cvor *napraviStablo() { cvor *koren = NULL; int x; scanf("%d", &x ); while ( x ) { dodaj( &koren, x ); scanf("%d", &x ); } return koren; } int main() { cvor *koren = napraviStablo(); vizuelniPrikaz( koren ); return 0; }