Buscar sin mirarlo todo

Si los menores van a un lado, cada paso descarta la mitad.

1Por qué

Buscar un dato en una lista es recorrerla entera. Con un millón de nodos, un millón de pasos. Y eso pasa cada vez que buscas algo.

En la lección 18 armaste un árbol, pero todavía no hiciste lo que lo justifica. La gracia no es que tenga dos ramas: es la regla de dónde va cada cosa. Los menores a la izquierda, los mayores a la derecha, siempre.

Con esa regla puesta, buscar cambia de naturaleza. Llegas a un nodo, comparas una vez, y la mitad del árbol deja de importar. No la recorres: la descartas entera. Después repites con lo que queda.

De un millón de datos se pasa a unos veinte pasos. Ese salto —de un millón a veinte— es la razón por la que existen los árboles, y es lo que hace que un buscador te conteste antes de que sueltes la tecla.

La búsqueda se escribe con recursión, igual que el recorrido de la lección 19: si lo que buscas es menor, el problema se vuelve «búscalo en el árbol de la izquierda», que es el mismo problema más chico.

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 contiene(Nodo *n, int x)
{
    if (n == NULL) return 0;
    if (n->valor == x) return 1;
 
    if (x < n->valor) return contiene(n->izq, x);
    return contiene(n->der, x);
}
 
int main(void)
{
    Nodo *raiz = crear(5);
    raiz->izq = crear(3);
    raiz->der = crear(8);
 
    printf("%d %d\n", contiene(raiz, 8), contiene(raiz, 1));
 
    free(raiz->izq);
    free(raiz->der);
    free(raiz);
    return 0;
}

línea 21
Se acabó el camino sin encontrarlo. Devolver 0 aquí es lo que corta el descenso.
línea 22
Encontrado. Ni siquiera se mira el resto del árbol.
línea 24
Aquí está todo. Una comparación, y el lado derecho entero deja de importar. No se recorre: se descarta.
línea 25
Si no es menor, está a la derecha o no está. Mismo problema, árbol más chico.

3Ahora tú

A esta búsqueda le falta el paso hacia la izquierda, así que solo encuentra lo que está a la derecha. Escríbelo para que diga: 1 0

#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 contiene(Nodo *n, int x)
{
    if (n == NULL) return 0;
    if (n->valor == x) return 1;
 
    
    return contiene(n->der, x);
}
 
int main(void)
{
    Nodo *raiz = crear(5);
    raiz->izq = crear(3);
    raiz->der = crear(8);
 
    printf("%d %d\n", contiene(raiz, 3), contiene(raiz, 4));
 
    free(raiz->izq);
    free(raiz->der);
    free(raiz);
    return 0;
}

↖︎ Tu línea va aquí: qué hacer cuando lo que buscas es menor.

Ejecutar

Lo que dice tu programa

↖︎ Escribe tu parte y dale a Ejecutar

Qué pasó

Aquí te aviso si tu programa hace algo raro.

4Qué guarda tu programa

Memoria

↖︎ Ejecuta el programa para ver qué pasa por dentro