Menu
Coddy logo textTech

האב הקדמון המשותף הנמוך ביותר

שיעור 14 מתוך 16 בקורס עץ AVL – סדרת מבני נתונים מס' 10 של Coddy.

האב הקדמון המשותף הנמוך ביותר של שני ערכים הוא הצומת העמוק ביותר שבתת-העץ שלו נמצאים שניהם. בעץ חיפוש בינארי אפשר למצוא אותו בלי להשוות ישירות בין תתי-עצים: מתחילים מהשורש, ואם שני הערכים קטנים מהצומת הנוכחי, התשובה נמצאת איפשהו בתת-העץ השמאלי; אם שניהם גדולים ממנו, היא נמצאת בתת-העץ הימני.

ברגע ששני הערכים נמצאים בצדדים שונים (או שאחד מהם שווה לצומת הנוכחי), מצאת את נקודת הפיצול: הצומת הזה הוא האב הקדמון המשותף הנמוך ביותר.

challenge icon

אתגר

קל

כתבו פונקציה 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

תרגלו בעצמכם: קומפיילר C אונליין