0votos

Igualdad de los bordes en C

por josejuan hace 6 años

Sin duda la más rápida. (Algún speedup es posible, como no usar atoi y mirar claves directamente, pero vamos...).

Decidir si dos árboles binarios tienen iguales los bordes; es decir, si tienen exactamente las mismas hojas leídas de izquierda a derecha, independientemente de los nodos interiores.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Ej: igualBorde("(1,(2,3))", "((1,2),3)"); 
int igualBorde(char *a, char *b) { 
    int ka, kb; 
    while(1) { 
#define SEARCH(c, kc) while(*c && !isdigit(*c)) c++; if(*c) {kc = atoi(c); while(isdigit(*c)) c++; } else kc = -1; 
        SEARCH(a, ka); 
        SEARCH(b, kb); 
        if(ka != kb) return 0; 
        if(ka == -1) return 1; 
 
/* 
 
Con un árbol (leído de disco) de 22 niveles (2^22 = 4.194.304 hojas), le toma 31 millisegundos, en un segundo revisará apróx hasta n = 27. 
 
(En un único hilo amd phenom a 2,7 GHz) 
 
*/ 
1 comentario
0votos

Escrito por josejuan hace 6 años

Por comparar, en un Atom a 1,7 GHz para n=22 le lleva 142 mS.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.