بحث
الدرس 10 من 16 في دورة شجرة AVL - سلسلة هياكل البيانات #10 على Coddy.
بما أن الشجرة هي دائماً شجرة بحث ثنائية صالحة (الموازنة لا تكسر الترتيب أبداً)، فإن البحث فيها يشبه تماماً البحث في شجرة بحث ثنائية (BST) عادية: ابدأ من root، وعند كل عقدة اتجه يساراً إذا كان الهدف أصغر، ويميناً إذا كان أكبر، أو توقف إذا كان مطابقاً. الوصول إلى مؤشر فارغ (null pointer) يعني أن القيمة غير موجودة في الشجرة.
بما أن الموازنة تحافظ على الارتفاع حول log(n) بغض النظر عن كيفية إدخال القيم، فإن هذا البحث لا يتدهور أبداً إلى مسح خطي بطيء، على عكس شجرة البحث الثنائية غير المتوازنة التي يتم بناؤها من مدخلات مرتبة.
التحدي
مبتدئاكتب طريقة search(value) في AVLTree تُرجع true إذا كانت value موجودة في أي مكان في الشجرة، و false بخلاف ذلك.
جرّب بنفسك
#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;
}