Successeur d'une valeur

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

Le successeur infixe d'une valeur est la plus petite valeur de l'arbre qui lui est strictement supérieure, c'est-à-dire la valeur qui viendrait juste après elle dans une liste triée. Si la valeur est le maximum de l'arbre, elle n'a pas de successeur.

Vous pouvez le trouver en un seul passage sans jamais rien trier : descendez à partir de la racine et, chaque fois que vous vous déplacez vers la droite après une valeur trop petite, gardez en mémoire le dernier nœud à partir duquel vous vous êtes déplacé vers la gauche comme étant votre meilleur candidat jusqu'à présent.

Défi

Facile

Écrivez une fonction successor(tree, value) qui renvoie la plus petite valeur de l'arbre strictement supérieure à value, ou -1 si aucune n'existe.

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