Suchen

Lektion 10 von 16 im Kurs AVL-Baum - Datenstrukturen-Serie #10 von Coddy.

Da der Baum immer ein gültiger binärer Suchbaum ist (Balancierung unterbricht niemals die Sortierung), ist das Suchen darin genau wie das Suchen in einem einfachen BST: Beginnen Sie bei root, und gehen Sie an jedem Knoten nach links, wenn das Ziel kleiner ist, nach rechts, wenn es größer ist, oder halten Sie an, wenn es übereinstimmt. Das Erreichen eines Null-Pointers bedeutet, dass der Wert nicht im Baum vorhanden ist.

Da die Balancierung die Höhe bei etwa log(n) hält, unabhängig davon, wie Werte eingefügt werden, degradiert diese Suche niemals zu einem langsamen linearen Scan, im Gegensatz zu einem unbalancierten BST, der aus sortierten Eingaben erstellt wurde.

Aufgabe

Anfänger

Schreiben Sie eine Methode search(value) für AVLTree, die true zurückgibt, wenn value irgendwo im Baum existiert, andernfalls false.

Probier es selbst

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