Wyszukiwanie

Lekcja 10 z 16 w kursie Drzewo AVL – struktury danych, seria #10 w Coddy.

Ponieważ drzewo jest zawsze poprawnym binarnym drzewem wyszukiwania (równoważenie nigdy nie narusza porządku), wyszukiwanie w nim przebiega dokładnie tak samo jak w zwykłym BST: zacznij od root, a w każdym węźle idź w lewo, jeśli szukana wartość jest mniejsza, w prawo, jeśli jest większa, albo zakończ, jeśli pasuje. Dotarcie do pustego wskaźnika oznacza, że tej wartości nie ma w drzewie.

Ponieważ równoważenie utrzymuje wysokość na poziomie około log(n), niezależnie od kolejności wstawiania wartości, wyszukiwanie nigdy nie przeradza się w powolne liniowe przeszukiwanie, w przeciwieństwie do niezrównoważonego BST zbudowanego z posortowanych danych wejściowych.

Wyzwanie

Początkujący

Napisz metodę search(value) w klasie AVLTree, która zwraca true, jeśli value występuje w dowolnym miejscu drzewa, a w przeciwnym razie false.

Spróbuj swoich sił

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