Menu
Coddy logo textTech

סכום בטווח

שיעור 13 מתוך 16 בקורס עץ AVL – סדרת מבני נתונים מס' 10 של Coddy.

מכיוון שהעץ שומר על הסדר של כל הערכים, אין צורך לבדוק כל צומת וצומת כדי לסכם טווח: בכל פעם שהערך של צומת קטן מ־low, גם כל תת־העץ השמאלי שלו קטן מ־low ואפשר לדלג עליו, ואותו היגיון חל על תת־העץ הימני כשהערך של צומת גדול מ־high.

מעבר פשוט בסדר־תוכי, שמבצע קריאה רקורסיבית רק לתת־עצים שעשויים להכיל ערכים בטווח, מספיק; אם כי עבור האתגר הזה גם מעבר מלא עם מסנן יעבוד.

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

תרגלו בעצמכם: קומפיילר C אונליין