Dos caminos en vez de uno

Si cada nodo apunta a dos, buscar deja de ser recorrerlo todo.

1Por qué

Buscar un dato en una lista es recorrerla entera. Con un millón de nodos, un millón de pasos. Se puede hacer mucho mejor, y el truco es cambiar una sola cosa: que cada nodo apunte a dos, no a uno.

Si además guardas los menores a la izquierda y los mayores a la derecha, buscar deja de ser mirarlos todos. En cada nodo comparas y descartas la mitad. De un millón se pasa a unos veinte pasos.

Eso es un árbol binario de búsqueda, y es la estructura que sostiene medio ramo: índices de bases de datos, diccionarios, buscadores. El árbol de la ayudantía es exactamente esto.

El nodo cambia poco: en vez de un sig, un izq y un der. Y el que no tiene hijos apunta a NULL por los dos lados — un final por cada camino, en vez de uno solo.

La palabra que se usa para el primero es raíz. El dibujo, por si te ayuda, está al revés que un árbol de verdad: la raíz arriba y las ramas bajando.

2Míralo andar

Este programa funciona. Léelo, y después ejecútalo sin cambiar nada.

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Nodo {
    int valor;
    struct Nodo *izq;
    struct Nodo *der;
} Nodo;
 
Nodo *crear(int v)
{
    Nodo *n = malloc(sizeof(Nodo));
    n->valor = v;
    n->izq = NULL;
    n->der = NULL;
    return n;
}
 
int main(void)
{
    Nodo *raiz = crear(5);
    raiz->izq = crear(3);
    raiz->der = crear(8);
 
    printf("%d\n", raiz->izq->valor);
 
    free(raiz->izq);
    free(raiz->der);
    free(raiz);
    return 0;
}

línea 10
Una función que arma un nodo entero y lo devuelve. Sin ella habría que repetir cuatro líneas por cada uno.
línea 14
Los dos lados empiezan en NULL: un nodo recién creado no tiene hijos todavía.
línea 22
El 3 es menor que el 5, así que va a la izquierda. Esa regla es lo que después permite descartar media búsqueda.
línea 28
Los hijos se sueltan antes que la raíz: después de soltar la raíz ya no habría forma de llegar a ellos.

3Ahora tú

Coloca el 2 en su sitio dentro del árbol y haz que el programa lo escriba

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Nodo {
    int valor;
    struct Nodo *izq;
    struct Nodo *der;
} Nodo;
 
Nodo *crear(int v)
{
    Nodo *n = malloc(sizeof(Nodo));
    n->valor = v;
    n->izq = NULL;
    n->der = NULL;
    return n;
}
 
int main(void)
{
    Nodo *raiz = crear(5);
    raiz->izq = crear(3);
 
    
 
    printf("%d\n", raiz->izq->izq->valor);
 
    free(raiz->izq->izq);
    free(raiz->izq);
    free(raiz);
    return 0;
}

↖︎ Tu línea va aquí. Mira la línea que escribe: te dice por qué camino tiene que quedar colgado el 2.

Dos caminos en vez de uno

1Por qué

2Míralo andar

3Ahora tú

Ejecutar

Lo que dice tu programa

Qué pasó

4Qué guarda tu programa

Memoria