値の後継者

Coddyの「AVL Tree - データ構造シリーズ #10」コースのレッスン 16/16。

ある値のインオーダー後続ノード (in-order successor)とは、その値よりも厳密に大きく、木の中で最小の値、つまりソートされたリストでその直後に来る値のことです。その値が木の中の最大値である場合、後続ノードは存在しません。

何もソートすることなく、1回のパスで見つけることができます。ルートから下へ進み、小さすぎる値を通り過ぎて右に進むたびに、最後に左に進んだときのノードを、これまでの最良の候補として記録しておきます。

チャレンジ

簡単

関数 successor(tree, value) を記述してください。この関数は、木の中で value よりも厳密に大きい最小の値を返します。存在しない場合は -1 を返します。

自分で試してみよう

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