Ara

Coddy'nin AVL Tree - Veri Yapıları Serisi #10 kursunda ders 10 / 16.

Ağaç her zaman geçerli bir ikili arama ağacı olduğu için (dengeleme sıralamayı asla bozmaz), içinde arama yapmak tıpkı düz bir BST'de arama yapmak gibidir: root düğümünden başlayın ve her düğümde hedef daha küçükse sola, daha büyükse sağa gidin veya eşleşirse durun. Bir null işaretçiye ulaşmak, değerin ağaçta olmadığı anlamına gelir.

Değerler nasıl eklenirse eklensin, dengeleme yüksekliği log(n) civarında tuttuğu için, bu arama, sıralı girdiden oluşturulmuş dengesiz bir BST'nin aksine hiçbir zaman yavaş bir doğrusal taramaya dönüşmez.

Görev

Başlangıç

AVLTree üzerinde, eğer value ağacın herhangi bir yerinde mevcutsa true, aksi takdirde false döndüren bir search(value) metodu yazın.

Kendin dene

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