Buscar

Lección 10 de 16 del curso Árbol AVL - Serie de Estructuras de Datos #10 de Coddy.

Debido a que el árbol es siempre un árbol de búsqueda binaria válido (el equilibrado nunca rompe el orden), buscar en él es exactamente igual que buscar en un BST simple: comienza en root, y en cada nodo ve a la izquierda si el objetivo es menor, a la derecha si es mayor, o detente si coincide. Llegar a un puntero nulo significa que el valor no está en el árbol.

Dado que el equilibrado mantiene la altura alrededor de log(n) sin importar cómo se inserten los valores, esta búsqueda nunca se degrada a un escaneo lineal lento, a diferencia de un BST no equilibrado construido a partir de una entrada ordenada.

Desafío

Principiante

Escribe un método search(value) en AVLTree que devuelva true si value existe en cualquier lugar del árbol, false de lo contrario.

Pruébalo tú mismo

#include <stdio.h>
#include <string.h>
#include "avltree.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line[256];
    while (fgets(line, sizeof(line), stdin) != NULL) {
        line[strcspn(line, "\r\n")] = '\0';
        char cmd[32];
        int arg;
        int parsed = sscanf(line, "%31s %d", cmd, &arg);
        if (parsed >= 1 && strcmp(cmd, "insert") == 0) {
            AVLTree_insert(tree, arg);
        }
        if (parsed >= 1 && strcmp(cmd, "search") == 0) {
            if (AVLTree_search(tree, arg)) {
                printf("true\n");
            }
            if (!AVLTree_search(tree, arg)) {
                printf("false\n");
            }
        }
    }
    return 0;
}