Somma di intervallo

Lezione 13 di 16 del corso Albero AVL - Serie sulle strutture dati #10 di Coddy.

Poiché l’albero mantiene tutti i valori ordinati, non è necessario esaminare ogni singolo nodo per sommare un intervallo: ogni volta che il valore di un nodo è inferiore a low, anche tutto il suo sottoalbero sinistro è inferiore a low e può essere ignorato; la stessa logica si applica al sottoalbero destro quando il valore di un nodo è superiore a high.

È sufficiente una semplice visita in ordine simmetrico che ricorra solo nei sottoalberi che potrebbero contenere valori nell’intervallo, anche se per questa sfida va bene anche una visita completa con un filtro.

Sfida

Facile

Scrivi una funzione rangeSum(tree, low, high) che restituisce la somma di tutti i valori nell’albero compresi tra low e high, estremi inclusi.

Provalo tu

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