検索

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

この木は常に有効な二分探索木であるため（リバランシングによって順序が崩れることはありません）、その探索は通常のBST（二分探索木）の探索と全く同じです。rootから開始し、各ノードでターゲットが小さければ左へ、大きければ右へ進み、一致すれば停止します。ヌルポインタに到達した場合は、その値が木の中に存在しないことを意味します。

値がどのように挿入されても、リバランシングによって高さがlog(n)程度に保たれるため、ソート済みの入力から構築されたバランスの取れていないBSTとは異なり、この探索が低速な線形スキャンに劣化することはありません。

チャレンジ

初心者

AVLTree に、value がツリー内のどこかに存在すれば true を、そうでなければ false を返すメソッド search(value) を作成してください。

自分で試してみよう

#include <stdio.h>
#include <string.h>
#include "avltree.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line[256];
    while (fgets(line, sizeof(line), stdin) != NULL) {
        line[strcspn(line, "\r\n")] = '\0';
        char cmd[32];
        int arg;
        int parsed = sscanf(line, "%31s %d", cmd, &arg);
        if (parsed >= 1 && strcmp(cmd, "insert") == 0) {
            AVLTree_insert(tree, arg);
        }
        if (parsed >= 1 && strcmp(cmd, "search") == 0) {
            if (AVLTree_search(tree, arg)) {
                printf("true\n");
            }
            if (!AVLTree_search(tree, arg)) {
                printf("false\n");
            }
        }
    }
    return 0;
}