값의 후속자

Coddy의 AVL 트리 - 자료구조 시리즈 #10 코스 레슨 — 16개 중 16번째.

어떤 값의 중위 후속자(in-order successor)는 트리에서 해당 값보다 엄격하게 큰 값 중 가장 작은 값이며, 정렬된 리스트에서 해당 값 바로 다음에 오는 값입니다. 만약 그 값이 트리의 최댓값이라면 후속자는 없습니다.

정렬을 하지 않고도 한 번의 탐색으로 이를 찾을 수 있습니다. 루트에서부터 내려가면서, 너무 작은 값을 지나쳐 오른쪽으로 이동할 때마다 왼쪽으로 이동하기 직전의 마지막 노드를 현재까지의 최적의 후보로 기억하세요.

챌린지

쉬움

value보다 엄격히 크면서 트리 내에서 가장 작은 값을 반환하거나, 그러한 값이 존재하지 않으면 -1을 반환하는 successor(tree, value) 함수를 작성하세요.

직접 해보기

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