Поиск

Урок 10 из 16 курса AVL-дерево — Серия «Структуры данных» №10 на Coddy.

Поскольку дерево всегда является корректным двоичным деревом поиска (балансировка никогда не нарушает порядок), поиск в нем происходит точно так же, как и в обычном BST: начните с root и на каждом узле переходите влево, если искомое значение меньше, вправо, если оно больше, или остановитесь, если оно совпадает. Достижение нулевого указателя означает, что значения в дереве нет.

Поскольку балансировка поддерживает высоту около log(n) независимо от того, как вставляются значения, этот поиск никогда не превращается в медленное линейное сканирование, в отличие от несбалансированного BST, построенного на основе отсортированных входных данных.

Задание

Новичок

Напишите метод search(value) в классе AVLTree, который возвращает true, если value существует где-либо в дереве, и false в противном случае.

Попробуйте сами

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