탐색

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

트리가 항상 유효한 이진 탐색 트리이기 때문에 (균형 조정은 순서를 깨뜨리지 않습니다), 이를 검색하는 것은 일반적인 BST를 검색하는 것과 정확히 같습니다: root에서 시작하여, 각 노드에서 대상이 더 작으면 왼쪽으로, 더 크면 오른쪽으로 이동하거나, 일치하면 멈춥니다. null 포인터에 도달하면 해당 값이 트리에 없음을 의미합니다.

값이 어떻게 삽입되든 균형 조정을 통해 높이를 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;
}