Lowest Common Ancestor of a BST

Q: מהי סיבוכיות הזמן של מציאת האב הקדמון המשותף הנמוך ביותר בעץ BST?

ההליכה מהשורש עוקבת אחר מסלול אחד, ולכן נדרש זמן O(h) עבור עץ שעומקו h ומקום נוסף O(1). בעץ מאוזן מדובר ב-O(log n); בעץ שצורתו היא מסלול יחיד מדובר ב-O(n).

Q: במה שונה ה-LCA בעץ חיפוש בינארי מה-LCA בעץ בינארי?

בעץ בינארי רגיל ערך יכול להימצא בכל מקום, ולכן ייתכן שתצטרכו לחפש בכל צומת, עבודה של O(n). בעץ חיפוש, השוואת שני הערכים לערך שבצומת אומרת לכם באיזה צד נמצא כל אחד מהם, ולכן אתם עוקבים אחר מסלול אחד מהשורש.

Q: האם צומת יכול להיות האב הקדמון המשותף הנמוך ביותר של עצמו?

כן. צומת נחשב לאב קדמון של עצמו, לכן כאשר p נמצא מעל q , התשובה היא p , וכאשר שני הערכים שווים, התשובה היא אותו ערך.

בינוניעץ חיפוש בינארי

+10

נתון לך עץ חיפוש בינארי המאוחסן בסדר ערימה במערך tree: השורש נמצא באינדקס 0, הילדים של האינדקס i נמצאים באינדקסים 2*i+1 (שמאל) ו־2*i+2 (ימין), ו־-1 מסמן מקום ריק. כל ערך בתת־העץ השמאלי של צומת קטן מערך הצומת, וכל ערך בתת־העץ הימני שלו גדול ממנו.

כתוב את lowestCommonAncestor, שמחזירה את הערך של האב הקדמון המשותף הנמוך ביותר של הערכים p ו־q, שניהם נמצאים בעץ: הצומת העמוק ביותר שבתת־העץ שלו נמצאים שניהם. צומת נחשב לחלק מתת־העץ של עצמו, ולכן אם p נמצא מעל q, התשובה היא p.

פונקציה

lowestCommonAncestor(tree: integer-array, p: integer, q: integer) → integer

treeinteger-array: עץ החיפוש הבינארי בסדר לפי רמות, עם ‎-1 עבור מקום ריק
pinteger: הערך הראשון שיש למצוא
qinteger: הערך השני שיש למצוא
מחזירהinteger: הערך של הצומת העמוק ביותר שבתת-העץ שלו נמצאים גם p וגם q

אילוצים

1 ≤ tree.length ≤ 32767
כל tree[i] הוא -1 או ערך המקיים 0 ≤ tree[i] ≤ 10⁵.
tree[0] לעולם אינו -1, ולכן יש לפחות צומת אחד בעץ.
המערך עשוי להסתיים בערכי -1 נוספים אחרי הצומת האחרון.
גם שני הצאצאים של מקום ריק ריקים, והעומק הוא לכל היותר 14.
העץ הוא עץ חיפוש בינארי תקין, ולכן כל הערכים בו שונים זה מזה.
p ו-q הם ערכים של צמתים בעץ. הם יכולים להופיע בכל סדר, וייתכן שיהיו שווים.

דוגמאות

קלט: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
פלט: 8
הסבר: בעלייה מ־3 ומ־15, הצומת הראשון ששניהם מגיעים אליו הוא 8: 3 הוא הילד השמאלי שלו, ו־15 נמצא מתחת ל־12 בצד הימני שלו. השורש 20 הוא גם אב קדמון משותף, אבל גבוה יותר.

קלט: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
פלט: 12
הסבר: 10 הוא הילד השמאלי של 12, וצומת נחשב לאב הקדמון של עצמו, לכן 12 מכיל את שני הערכים, ושום דבר מתחתיו לא מכיל אותם. כאן p הוא הערך הגדול יותר.

קלט: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
פלט: 70
הסבר: שני הערכים גדולים יותר מהשורש 50, ולכן שניהם נמצאים מימינו. ב־70 הם מתפצלים: 55 קטן יותר ונמצא משמאל, מתחת ל־60, ו־80 גדול יותר.

שאלת המשך

מה היית משנה אם p או q עשויים להיות חסרים בעץ, והפונקציה צריכה להחזיר -1 במקרה כזה?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

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

חפשו בכל העץ, בלי להתחשב בסדר

האינטואיציה

השיטה הזאת עובדת על כל עץ בינארי. קריאה רקורסיבית ל־find(i) מדווחת מה מכילה תת־העץ שב־i. צומת שמכיל את p או את q מדווח על עצמו: אם הערך השני נמצא מתחתיו, הוא התשובה, ואם לא, צומת שנמצא גבוה יותר רואה את שניהם. כל צומת אחר שואל את שני ילדיו. אם שניהם מדווחים על משהו, p ו־q נמצאים בצדדים שונים, והצומת הזה הוא המקום שבו הם נפגשים; אם רק אחד מהם מדווח על משהו, מעבירים את הדיווח שלו כלפי מעלה.

עבור 3 ו־15, הצומת 8 מקבל את האינדקס 3 מהצד השמאלי ואת האינדקס 10 מהצד הימני, ומדווח על עצמו. ייתכן שהוא יבקר בכל צומת: זמן הריצה הוא O(n), ועומק הרקורסיה הוא O(h).

אלגוריתם

כתבו find(i). אם המקום ב-i ריק (מעבר לסוף או -1), החזירו -1.
אם tree[i] הוא p או q, החזירו i.
קראו ל-find עם 2*i+1 ועם 2*i+2. אם שניהם מצאו משהו, החזירו i.
אחרת, החזירו את הצד שמצא משהו, או -1.
החזירו tree[find(0)].

def lowestCommonAncestor(tree, p, q):
    n = len(tree)

    def find(i):
        # In the subtree at index i: the index of the answer if both values are
        # inside, the index of the one that is, or -1 when neither is.
        if i >= n or tree[i] == -1:
            return -1
        if tree[i] == p or tree[i] == q:
            return i
        left = find(2 * i + 1)
        right = find(2 * i + 2)
        if left != -1 and right != -1:
            return i  # one value on each side: this node is the answer
        return left if left != -1 else right

    return tree[find(0)]

השוו בין שני מסלולי החיפוש

האינטואיציה

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

תעד את שני המסלולים. הם חולקים צמתים עד שהערכים פונים לכיוונים שונים, ולכן תחילת המסלולים המשותפת מציגה את האבות המשותפים, והערך האחרון בה הוא הנמוך ביותר. עבור 3 ו-15 המסלולים הם 20, 8, 3 ו-20, 8, 12, 15: הם חולקים את 20, 8, ולכן התשובה היא 8. כל מעבר לוקח צעד אחד בכל רמה: זמן O(h), ומקום O(h) עבור הרשימות.

אלגוריתם

כתבו path(target): מתחילים באינדקס 0, מתעדים את tree[i], עוצרים כשהוא שווה ל־target, אחרת עוברים ל־2*i+1 אם target קטן יותר, ול־2*i+2 אם הוא גדול יותר.
בנו את הנתיב אל p ואת הנתיב אל q.
עברו על שתי הרשימות מההתחלה והחזירו את הערך האחרון שמשותף להן.

def lowestCommonAncestor(tree, p, q):
    def path(target):
        # The values met on the way from the root down to target.
        values = []
        i = 0
        while True:
            values.append(tree[i])
            if tree[i] == target:
                return values
            i = 2 * i + 1 if target < tree[i] else 2 * i + 2

    to_p, to_q = path(p), path(q)
    # Both paths start at the root; the answer is the last value they share.
    answer = to_p[0]
    for a, b in zip(to_p, to_q):
        if a != b:
            break
        answer = a
    return answer

רד למטה עד שהערכים מתפצלים

האינטואיציה

שני המסלולים מתקדמים באותו אופן כל עוד p ו־q הולכים באותו כיוון, לכן צועדים בשניהם בו־זמנית. בצומת שמכיל את v, אם שני הערכים קטנים יותר, שניהם נמצאים בתת־העץ השמאלי, וכך גם כל אב קדמון משותף שנמצא מתחת ל־v: הולכים שמאלה. אם שניהם גדולים יותר, הולכים ימינה.

אחרת, ערך אחד קטן יותר והאחר גדול יותר, ולכן אף אחד מהילדים של v אינו מכיל את שניהם, או שאחד מהם שווה ל־v, שהוא אב קדמון של עצמו. כך או כך, v הוא הצומת העמוק ביותר שנמצא מעל שניהם. בדוגמה השלישית, 50 קטן משני הערכים, לכן הולכים ימינה אל 70, שבו 55 קטן יותר ו־80 גדול יותר. זוג השוואות אחד בכל רמה נותן זמן O(h) ומקום O(1).

אלגוריתם

התחל באינדקס i = 0.
קרא את v = tree[i].
אם p < v וגם q < v, עבור אל 2*i+1 וחזור על הפעולה.
אם p > v וגם q > v, עבור אל 2*i+2 וחזור על הפעולה.
אחרת, החזר את v.

def lowestCommonAncestor(tree, p, q):
    i = 0  # start at the root
    while True:
        value = tree[i]
        if p < value and q < value:
            i = 2 * i + 1  # both are smaller: the answer is on the left
        elif p > value and q > value:
            i = 2 * i + 2  # both are larger: the answer is on the right
        else:
            return value  # they split here, or one of them is this node

מלכודות ומקרי קצה

שימוש ב-≤ וב-≥ בבדיקות התנועה. כאשר p = 12 ו-q = 10, ההליכה חולפת על פני 12 ומגיעה ל-10, ואז מחזירה את 10 או יוצאת מהעץ.
הנחה ש-p < q. בדוגמה השנייה p הוא הערך הגדול יותר. בדוק את שניהם מול הצומת, או החלף ביניהם תחילה.
החזרת האינדקס במקום הערך. התשובה היא tree[i], ולא i.
ב-Lua וב-R, מערכים מתחילים ב-1. השאר את אינדקסי הצמתים מבוססי-0 עבור החישוב 2*i+1 וקרא את tree[i + 1].

שאלות נפוצות3

מהי סיבוכיות הזמן של מציאת האב הקדמון המשותף הנמוך ביותר בעץ BST?

ההליכה מהשורש עוקבת אחר מסלול אחד, ולכן נדרש זמן O(h) עבור עץ שעומקו h ומקום נוסף O(1). בעץ מאוזן מדובר ב-O(log n); בעץ שצורתו היא מסלול יחיד מדובר ב-O(n).

במה שונה ה-LCA בעץ חיפוש בינארי מה-LCA בעץ בינארי?

בעץ בינארי רגיל ערך יכול להימצא בכל מקום, ולכן ייתכן שתצטרכו לחפש בכל צומת, עבודה של O(n). בעץ חיפוש, השוואת שני הערכים לערך שבצומת אומרת לכם באיזה צד נמצא כל אחד מהם, ולכן אתם עוקבים אחר מסלול אחד מהשורש.

האם צומת יכול להיות האב הקדמון המשותף הנמוך ביותר של עצמו?

כן. צומת נחשב לאב קדמון של עצמו, לכן כאשר p נמצא מעל q, התשובה היא p, וכאשר שני הערכים שווים, התשובה היא אותו ערך.

def lowestCommonAncestor(tree, p, q):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]
p = 3
q = 15

הפלט הצפוי

Lowest Common Ancestor of a BST

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

חפשו בכל העץ, בלי להתחשב בסדר

השוו בין שני מסלולי החיפוש

רד למטה עד שהערכים מתפצלים

מלכודות ומקרי קצה

שאלות נפוצות3

בעיות דומות