חיפוש
שיעור 10 מתוך 16 בקורס עץ AVL – סדרת מבני נתונים מס' 10 של Coddy.
מכיוון שהעץ תמיד נשאר עץ חיפוש בינארי תקין (איזון לעולם אינו פוגע בסדר), החיפוש בו זהה בדיוק לחיפוש בעץ חיפוש בינארי רגיל: מתחילים ב־root, ובכל צומת פונים שמאלה אם ערך היעד קטן יותר, ימינה אם הוא גדול יותר, או עוצרים אם הוא תואם. הגעה למצביע null פירושה שהערך אינו נמצא בעץ.
מכיוון שהאיזון שומר על הגובה בסביבות 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;
}
כל השיעורים ביחידה עץ AVL – סדרת מבני נתונים מס' 10
תרגלו בעצמכם: קומפיילר C אונליין