Subtree of Another Tree

Q: מהי סיבוכיות הזמן של תת־עץ של עץ אחר?

השוואה מכל צומת עולה O(n·m) במקרה הגרוע ביותר, כאשר n ו- m הם הגדלים של שני העצים. השוואה רק בצמתים שגובהם שווה לגובה של subRoot מביאה את הסיבוכיות ל- O(n + m) , כי כך עוברים על כל צומת של root לכל היותר פעם אחת.

Q: האם אפשר לפתור את תת-העץ של עץ אחר באמצעות התאמת מחרוזות?

כן. כתבו כל עץ בסדר תחילי, עם # לכל ילד ריק ומפריד לפני כל ערך: ,2,1,#,#,3,#,# . subRoot הוא תת־עץ בדיוק כאשר המחרוזת שלו מופיעה בתוך המחרוזת של root , ו-KMP מוצא אותו ב- O(n + m) . ללא הסימונים, מבנים שונים נותנים את אותה מחרוזת; ללא מפרידים, 12 מכיל את 2 .

קלסריקת עצים רקורסיה

+10

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

החזר true אם לצומת כלשהו ב-root, יחד עם כל צאצאיו, יש בדיוק אותה צורה ואותם ערכים כמו ל-subRoot, ו-false אחרת. גם העץ כולו root נחשב.

פונקציה

isSubtree(root: integer-array, subRoot: integer-array) → boolean

rootinteger-array: העץ לחיפוש, בסדר רמות, כאשר ‎-1 מציין מקום ריק
subRootinteger-array: העץ שיש לחפש, באותו פורמט
מחזירהboolean: true אם subRoot מופיע ב-root כצומת עם כל הצאצאים שלו, false אחרת

אילוצים

1 ≤ root.length ≤ 32767 ו-1 ≤ subRoot.length ≤ 32767
כל ערך הוא -1 או ערך בטווח שבין 0 ל־10⁴.
root[0] ו-subRoot[0] לעולם אינם -1, ולכן בשני העצים יש לפחות צומת אחד.
כל אחד מהמערכים עשוי להסתיים ברשומות -1 נוספות אחרי הצומת האחרון שלו.
גם שני הילדים של מקום ריק ריקים, ועומקו של כל עץ הוא לכל היותר 14.
ערכים עשויים לחזור על עצמם.

דוגמאות

קלט: root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
פלט: true
הסבר: לצומת 2 באינדקס 1 יש ילדים 1 ו־3, ושניהם עלים. זה בדיוק subRoot.

קלט: root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
פלט: false
הסבר: ל־3 שמתחת לצומת 2 יש עכשיו ילד 0. תת־עץ כולל את כל הצאצאים, ולכן הצומת 2 מכיל ארבעה צמתים, לעומת שלושת הצמתים של subRoot, ואין צומת אחר שמכיל 2.

קלט: root = [5, 5, 7]subRoot = [5]
פלט: true
הסבר: לשורש 5 יש שני ילדים, ולכן הוא אינו תואם לצומת היחיד 5. ה־5 באינדקס 1 הוא עלה ומתאים.

שאלת המשך

האם אפשר ליצור טביעת אצבע לכל תת־עץ על סמך הערך שלו וטביעות האצבע של ילדיו, כך שהשוואה מול subRoot תעלה O(1)? מה עושים כשיש התנגשות בין טביעות האצבע של שני תתי־עצים שונים?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

השווה בכל צומת

האינטואיציה

מקום i הוא אמיתי כאשר i נמצא בתוך המערך והערך שם אינו -1. שני עצים זהים כאשר שניהם ריקים, או כאשר בראשיהם אותו ערך ותתי־העצים השמאליים והימניים שלהם זהים. same(i, j) מתקדם צעד־צעד ב־root החל מ־i וב־subRoot החל מ־j. אם subRoot מופיע ב־root, ראשו נמצא בצומת כלשהו, לכן נסה את same(i, 0) מכל i אמיתי.

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

אלגוריתם

כתבו same(i, j). אם גם המיקום i ב־root וגם המיקום j ב־subRoot ריקים, החזירו true; אם בדיוק אחד מהם ריק, החזירו false.
אם שני הערכים שונים, החזירו false. אחרת, החזירו same(2*i+1, 2*j+1) וגם same(2*i+2, 2*j+2).
החזירו true אם מתקיים same(i, 0) עבור אינדקס ממשי כלשהו i של root, ואחרת החזירו false.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    # Try every real node of root as the top of a match.
    for i in range(n):
        if root[i] != -1 and same(i, 0):
            return True
    return False

השווה רק במקומות שבהם הגבהים זהים

האינטואיציה

לעצים זהים יש אותו גובה, הנספר לפי מספר הצמתים במסלול הארוך ביותר כלפי מטה. לכן כדאי לבדוק רק את הצמתים של root שגובהם שווה לגובה של subRoot. בדוגמה הראשונה הגובה של subRoot הוא 2, ובעץ root רק הגובה של 2 ושל 8 שווה לו.

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

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

אלגוריתם

מלאו מערך גבהים עבור כל עץ, בסריקה מהאינדקס האחרון לאחור עד 0: מקום ריק מקבל 0, וצומת אמיתי מקבל 1 ועוד הגובה הגדול יותר מבין שני ילדיו.
עבור כל אינדקס i של root שגובהו שווה לגובה באינדקס 0 של subRoot, הפעילו את same(i, 0) והחזירו true אם התנאי מתקיים.
החזירו false.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    def heights(tree):
        # Children sit at larger indexes, so a backward scan finishes them first.
        h = [0] * len(tree)
        for i in range(len(tree) - 1, -1, -1):
            if tree[i] != -1:
                left = h[2 * i + 1] if 2 * i + 1 < len(tree) else 0
                right = h[2 * i + 2] if 2 * i + 2 < len(tree) else 0
                h[i] = 1 + max(left, right)
        return h

    target = heights(subRoot)[0]
    rootHeights = heights(root)
    # Only a node of the same height can match, and no two such nodes overlap.
    for i in range(n):
        if rootHeights[i] == target and same(i, 0):
            return True
    return False

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

קבלת התאמה חלקית, כמו בדוגמה השנייה. same חייבת להיכשל כאשר ל-root יש צומת במקום שבו ל-subRoot יש מקום ריק.
עצירה בצומת הראשון עם הערך הנכון. בדוגמה השלישית, שורש 5 נכשל, והעלה 5 שמתחתיו תואם.
השוואת פרוסות של שני המערכים. הצמתים של תת-עץ פרוסים על פני רמות רבות, וכל אחד מהמערכים עשוי להסתיים בערכי -1 נוספים. אינדקס שמעבר לסוף הוא מקום ריק, כמו -1.
ב-Lua וב-R, יש לשמור על אינדקסים של צמתים שמתחילים ב-0 עבור החישוב 2*i+1, ולקרוא את root[i + 1].

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

מהי סיבוכיות הזמן של תת־עץ של עץ אחר?

השוואה מכל צומת עולה O(n·m) במקרה הגרוע ביותר, כאשר n ו-m הם הגדלים של שני העצים. השוואה רק בצמתים שגובהם שווה לגובה של subRoot מביאה את הסיבוכיות ל-O(n + m), כי כך עוברים על כל צומת של root לכל היותר פעם אחת.

האם אפשר לפתור את תת-העץ של עץ אחר באמצעות התאמת מחרוזות?

כן. כתבו כל עץ בסדר תחילי, עם # לכל ילד ריק ומפריד לפני כל ערך: ,2,1,#,#,3,#,#. subRoot הוא תת־עץ בדיוק כאשר המחרוזת שלו מופיעה בתוך המחרוזת של root, ו-KMP מוצא אותו ב-O(n + m). ללא הסימונים, מבנים שונים נותנים את אותה מחרוזת; ללא מפרידים, 12 מכיל את 2.

האם צומת שתואם ל־subRoot אך יש לו ילדים נוספים נחשב?

לא. תת-עץ הוא צומת יחד עם כל הצאצאים שלו, ולכן כל צומת שמתחת להתאמה חייב להופיע גם ב-subRoot. בדוגמה השנייה, ה-0 הנוסף שמתחת ל-3 הופך את התשובה ל-false.

def isSubtree(root, subRoot):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

root = [6, 2, 8, 1, 3, -1, 9]
subRoot = [2, 1, 3]

הפלט הצפוי

true