Bereichssumme

Lektion 13 von 16 im Kurs AVL-Baum - Datenstrukturen-Serie #10 von Coddy.

Da der Baum alle Werte geordnet hält, müssen Sie nicht jeden einzelnen Knoten untersuchen, um einen Bereich zu summieren: Wann immer der Wert eines Knotens unter low liegt, liegt auch sein gesamter linker Teilbaum unter low und kann übersprungen werden, und die gleiche Logik gilt für den rechten Teilbaum, wenn der Wert eines Knotens über high liegt.

Ein einfacher In-Order-Durchlauf, der nur in Teilbäume rekursiert, die Werte im Bereich enthalten könnten, ist ausreichend, obwohl für diese Herausforderung auch ein vollständiger Durchlauf mit einem Filter funktioniert.

Aufgabe

Einfach

Schreibe eine Funktion rangeSum(tree, low, high), die die Summe aller Werte im Baum zurückgibt, die zwischen low und high (einschließlich) liegen.

Probier es selbst

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