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

مجموع النطاق

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

بما أن الشجرة تحافظ على ترتيب كل قيمة، فلست بحاجة إلى فحص كل عقدة على حدة لجمع نطاق معين: فكلما كانت قيمة العقدة أقل من low، فإن شجرتها الفرعية اليسرى بالكامل تكون أيضاً أقل من low ويمكن تخطيها، وينطبق المنطق نفسه على الشجرة الفرعية اليمنى عندما تكون قيمة العقدة أعلى من high.

يكفي إجراء عملية مرور بسيطة بالترتيب (in-order walk) تنتقل بشكل متكرر فقط إلى الأشجار الفرعية التي قد تحتوي على قيم ضمن النطاق، على الرغم من أن إجراء عملية مرور كاملة مع استخدام مرشح (filter) سيعمل أيضاً في هذا التحدي.

challenge icon

التحدي

سهل

اكتب دالة rangeSum(tree, low, high) تُرجع مجموع كل قيمة في الشجرة تقع بين low و high، بشكل شامل.

جرّب بنفسك

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avltree.h"
#include "solution.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line1[4096];
    fgets(line1, sizeof(line1), stdin);
    char* tok = strtok(line1, " \n");
    while (tok != NULL) {
        AVLTree_insert(tree, atoi(tok));
        tok = strtok(NULL, " \n");
    }
    char line2[256];
    fgets(line2, sizeof(line2), stdin);
    int p0 = atoi(strtok(line2, " \n"));
    int p1 = atoi(strtok(NULL, " \n"));
    int result = rangeSum(tree, p0, p1);
    printf("%d\n", result);
    return 0;
}

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