Somme d'intervalle

Leçon 13 sur 16 du cours Arbre AVL - Série Structures de données n°10 de Coddy.

Parce que l'arbre conserve chaque valeur ordonnée, vous n'avez pas besoin d'inspecter chaque nœud pour additionner une plage : chaque fois que la valeur d'un nœud est inférieure à low, tout son sous-arbre gauche est également inférieur à low et peut être ignoré, et la même logique s'applique au sous-arbre droit lorsque la valeur d'un nœud est supérieure à high.

Un simple parcours en ordre qui ne descend par récursion que dans les sous-arbres pouvant contenir des valeurs dans la plage est suffisant, bien que pour ce défi, un parcours complet avec un filtre fonctionne également.

Défi

Facile

Écrivez une fonction rangeSum(tree, low, high) qui retourne la somme de chaque valeur dans l'arbre qui se situe entre low et high, inclusivement.

Essayez vous-même

#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;
}