האיבר הקטן ביותר במקום ה־K
שיעור 12 מתוך 16 בקורס עץ AVL – סדרת מבני נתונים מס' 10 של Coddy.
באתגרים הבאים תשתמשו במחלקה המוגמרת AVLTree שבניתם זה עתה, והיא מסופקת לכם כקובץ נעול. עם כל אתגר מגיע קובץ solution חדש, שבו תכתבו פונקציה שמשתמשת בעץ.
מעבר בסדר תוכי של כל עץ חיפוש בינארי (סיבובים לא משנים זאת) מבקר בערכים בסדר ממוין. לכן הערך הקטן ביותר ה־k הוא פשוט האיבר באינדקס k - 1 של המעבר הזה.
אתגר
קלכתוב פונקציה kthSmallest(tree, k) שמחזירה את הערך ה-k הקטן ביותר בעץ (האינדקס מתחיל ב-1). אפשר להניח ש-k תקין.
נסו בעצמכם
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avltree.h"
#include "solution.h"
int main(void) {
AVLTree* tree = AVLTree_create();
char line1[4096];
fgets(line1, sizeof(line1), stdin);
char* tok = strtok(line1, " \n");
while (tok != NULL) {
AVLTree_insert(tree, atoi(tok));
tok = strtok(NULL, " \n");
}
char line2[256];
fgets(line2, sizeof(line2), stdin);
int p0 = atoi(strtok(line2, " \n"));
int result = kthSmallest(tree, p0);
printf("%d\n", result);
return 0;
}
כל השיעורים ביחידה עץ AVL – סדרת מבני נתונים מס' 10
3אתגרי תרגול
האיבר הקטן ביותר במקום ה־Kסכום בטווחהאב הקדמון המשותף הנמוך ביותרמעבר לפי רמותהיורש של ערךתרגלו בעצמכם: קומפיילר C אונליין