مجموع النطاق
الدرس 13 من 16 في دورة شجرة AVL - سلسلة هياكل البيانات #10 على Coddy.
بما أن الشجرة تحافظ على ترتيب كل قيمة، فلست بحاجة إلى فحص كل عقدة على حدة لجمع نطاق معين: فكلما كانت قيمة العقدة أقل من low، فإن شجرتها الفرعية اليسرى بالكامل تكون أيضاً أقل من low ويمكن تخطيها، وينطبق المنطق نفسه على الشجرة الفرعية اليمنى عندما تكون قيمة العقدة أعلى من high.
يكفي إجراء عملية مرور بسيطة بالترتيب (in-order walk) تنتقل بشكل متكرر فقط إلى الأشجار الفرعية التي قد تحتوي على قيم ضمن النطاق، على الرغم من أن إجراء عملية مرور كاملة مع استخدام مرشح (filter) سيعمل أيضاً في هذا التحدي.
التحدي
سهلاكتب دالة 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;
}