סכום בטווח
שיעור 13 מתוך 16 בקורס עץ AVL – סדרת מבני נתונים מס' 10 של Coddy.
מכיוון שהעץ שומר על הסדר של כל הערכים, אין צורך לבדוק כל צומת וצומת כדי לסכם טווח: בכל פעם שהערך של צומת קטן מ־low, גם כל תת־העץ השמאלי שלו קטן מ־low ואפשר לדלג עליו, ואותו היגיון חל על תת־העץ הימני כשהערך של צומת גדול מ־high.
מעבר פשוט בסדר־תוכי, שמבצע קריאה רקורסיבית רק לתת־עצים שעשויים להכיל ערכים בטווח, מספיק; אם כי עבור האתגר הזה גם מעבר מלא עם מסנן יעבוד.
אתגר
קלכתבו פונקציה 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 אונליין