Recherche

Leçon 10 sur 16 du cours Arbre AVL - Série Structures de données n°10 de Coddy.

Parce que l'arbre est toujours un arbre de recherche binaire valide (l'équilibrage ne rompt jamais l'ordre), le parcourir est exactement comme parcourir un BST classique : commencez à root, et à chaque nœud, allez à gauche si la cible est plus petite, à droite si elle est plus grande, ou arrêtez-vous si elle correspond. Atteindre un pointeur nul signifie que la valeur n'est pas dans l'arbre.

Puisque l'équilibrage maintient la hauteur autour de log(n) peu importe la façon dont les valeurs sont insérées, cette recherche ne se dégrade jamais en un balayage linéaire lent, contrairement à un BST non équilibré construit à partir d'une entrée triée.

Défi

Débutant

Écrivez une méthode search(value) sur AVLTree qui renvoie true si value existe n'importe où dans l'arbre, false sinon.

Essayez vous-même

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