Cerca

Lezione 10 di 16 del corso Albero AVL - Serie sulle strutture dati #10 di Coddy.

Poiché l’albero è sempre un albero di ricerca binario valido (il bilanciamento non altera mai l’ordinamento), cercarvi un valore è esattamente come cercarlo in un BST semplice: parti da root e, a ogni nodo, vai a sinistra se il valore cercato è minore, a destra se è maggiore oppure fermati se corrisponde. Raggiungere un puntatore null significa che il valore non è nell’albero.

Poiché il bilanciamento mantiene l’altezza intorno a log(n) indipendentemente da come vengono inseriti i valori, questa ricerca non degenera mai in una lenta scansione lineare, a differenza di un BST non bilanciato costruito a partire da dati ordinati.

Sfida

Principiante

Scrivi un metodo search(value) su AVLTree che restituisca true se value esiste in qualsiasi punto dell'albero, false altrimenti.

Provalo tu

#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;
}