Menu
CoddyTech

Tìm kiếm

Bài học 10 trên 16 trong khóa học Cây AVL, chuỗi cấu trúc dữ liệu #10 của Coddy.

Vì cây luôn là cây tìm kiếm nhị phân hợp lệ, việc cân bằng không làm thay đổi thứ tự, nên cách tìm kiếm trong cây này giống hệt cách tìm trong cây tìm kiếm nhị phân thông thường: bắt đầu từ root, tại mỗi nút, đi sang trái nếu giá trị cần tìm nhỏ hơn, đi sang phải nếu giá trị đó lớn hơn, hoặc dừng lại nếu giá trị trùng khớp. Nếu gặp con trỏ null, nghĩa là giá trị đó không có trong cây.

Vì việc cân bằng giữ cho chiều cao của cây xấp xỉ log(n) bất kể các giá trị được chèn theo thứ tự nào, quá trình tìm kiếm này không bao giờ suy giảm thành việc duyệt tuyến tính chậm chạp, khác với cây tìm kiếm nhị phân không cân bằng được tạo từ dữ liệu đầu vào đã sắp xếp.

challenge icon

Thử thách

Người mới

Viết phương thức search(value) trên AVLTree, trả về true nếu value tồn tại ở bất kỳ đâu trong cây, nếu không thì trả về false.

Tự làm thử

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

Tất cả bài học trong Cây AVL, chuỗi cấu trúc dữ liệu #10

Tự luyện tập: Trình biên dịch C online