האב הקדמון המשותף הנמוך ביותר
שיעור 14 מתוך 16 בקורס עץ AVL – סדרת מבני נתונים מס' 10 של Coddy.
האב הקדמון המשותף הנמוך ביותר של שני ערכים הוא הצומת העמוק ביותר שבתת-העץ שלו נמצאים שניהם. בעץ חיפוש בינארי אפשר למצוא אותו בלי להשוות ישירות בין תתי-עצים: מתחילים מהשורש, ואם שני הערכים קטנים מהצומת הנוכחי, התשובה נמצאת איפשהו בתת-העץ השמאלי; אם שניהם גדולים ממנו, היא נמצאת בתת-העץ הימני.
ברגע ששני הערכים נמצאים בצדדים שונים (או שאחד מהם שווה לצומת הנוכחי), מצאת את נקודת הפיצול: הצומת הזה הוא האב הקדמון המשותף הנמוך ביותר.
אתגר
קלכתבו פונקציה lca(tree, p, q) שמחזירה את הערך של האב הקדמון המשותף הנמוך ביותר של p ושל q. אפשר להניח ששני הערכים קיימים בעץ.
נסו בעצמכם
#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 p1 = atoi(strtok(NULL, " \n"));
int result = lca(tree, p0, p1);
printf("%d\n", result);
return 0;
}
כל השיעורים ביחידה עץ AVL – סדרת מבני נתונים מס' 10
3אתגרי תרגול
האיבר הקטן ביותר במקום ה־Kסכום בטווחהאב הקדמון המשותף הנמוך ביותרמעבר לפי רמותהיורש של ערךתרגלו בעצמכם: קומפיילר C אונליין