Successore di un valore

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

Il successore in ordine di un valore è il valore più piccolo nell’albero che è strettamente maggiore di esso, il valore che verrebbe subito dopo in un elenco ordinato. Se il valore è il massimo nell’albero, non ha un successore.

Puoi trovarlo in un solo passaggio senza mai ordinare nulla: scendi dalla radice e, ogni volta che vai a destra oltre un valore troppo piccolo, ricorda l’ultimo nodo da cui sei andato a sinistra come miglior candidato finora.

Sfida

Facile

Scrivi una funzione successor(tree, value) che restituisca il valore più piccolo nell’albero strettamente maggiore di value, oppure -1 se non esiste.

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 result = successor(tree, p0);
    printf("%d\n", result);
    return 0;
}