Menu
Coddy logo textTech
flag Ar iconالعربيةdown icon

بحث

الدرس 10 من 16 في دورة شجرة AVL - سلسلة هياكل البيانات #10 على Coddy.

بما أن الشجرة هي دائماً شجرة بحث ثنائية صالحة (الموازنة لا تكسر الترتيب أبداً)، فإن البحث فيها يشبه تماماً البحث في شجرة بحث ثنائية (BST) عادية: ابدأ من root، وعند كل عقدة اتجه يساراً إذا كان الهدف أصغر، ويميناً إذا كان أكبر، أو توقف إذا كان مطابقاً. الوصول إلى مؤشر فارغ (null pointer) يعني أن القيمة غير موجودة في الشجرة.

بما أن الموازنة تحافظ على الارتفاع حول log(n) بغض النظر عن كيفية إدخال القيم، فإن هذا البحث لا يتدهور أبداً إلى مسح خطي بطيء، على عكس شجرة البحث الثنائية غير المتوازنة التي يتم بناؤها من مدخلات مرتبة.

challenge icon

التحدي

مبتدئ

اكتب طريقة 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;
}

جميع دروس شجرة AVL - سلسلة هياكل البيانات #10