Buscar

Lição 10 de 16 do curso Árvore AVL - Série de Estruturas de Dados #10 da Coddy.

Como a árvore é sempre uma árvore de busca binária válida (o balanceamento nunca quebra a ordenação), buscá-la é exatamente como buscar em uma BST comum: comece na root e, em cada nó, vá para a esquerda se o alvo for menor, para a direita se for maior, ou pare se houver uma correspondência. Alcançar um ponteiro nulo significa que o valor não está na árvore.

Como o balanceamento mantém a altura em torno de log(n), não importa como os valores sejam inseridos, esta busca nunca se degrada para uma varredura linear lenta, ao contrário de uma BST não balanceada construída a partir de uma entrada ordenada.

Desafio

Iniciante

Escreva um método search(value) na AVLTree que retorna true se value existir em qualquer lugar da árvore, false caso contrário.

Experimente você mesmo

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