Balanced Binary Tree

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

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

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

+10

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

החזר true אם העץ מאוזן בגובה, כלומר בכל צומת ההבדל בין הגבהים של תתי-העץ השמאלי והימני הוא לכל היותר 1, ואחרת החזר false. גובה של תת-עץ הוא מספר הצמתים במסלול הארוך ביותר כלפי מטה; גובה של תת-עץ ריק הוא 0.

פונקציה

isBalanced(root: integer-array) → boolean

rootinteger-array: העץ הבינארי לפי סדר רמות, עם ‎-1‎ עבור מקום ריק
מחזירהboolean: true אם הגבהים של שתי תתי-העץ של כל צומת נבדלים לכל היותר ב־1, ו־false אחרת

אילוצים

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

דוגמאות

קלט: root = [5, 2, 9, -1, -1, 7, 11]
פלט: true
הסבר: תת-העץ השמאלי של השורש הוא הצומת היחיד 2, שגובהו 1. לתת-העץ הימני שלו, 9, 7, 11, יש גובה 2. ההפרש ביניהם הוא 1, ולכל צומת אחר יש שני תתי-עצים שגובהם שווה.

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

קלט: root = [4, 2, -1, 1]
פלט: false
הסבר: לשורש יש שרשרת של 2, 1 משמאלו, בגובה 2, ואין דבר מימינו, בגובה 0. הפרש של 2 גדול מדי.

שאלת המשך

האם תוכל לבדוק את העץ ללא רקורסיה, באמצעות מחסנית מפורשת?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

חשב מחדש את הגבהים בכל צומת

האינטואיציה

הפכו את ההגדרה לקוד. height(i) הוא 0 במקום ריק, ובכל מקום אחר גדול ב־1 מגובהו של הילד הגבוה יותר. השוו בין הגבהים של שני הילדים בכל צומת ממשי; הצומת הראשון שבו הם שונים ביותר מ־1 הופך את התשובה ל־false.

כל בדיקה עוברת על כל תת־העץ שמתחת לצומת שלה, ולכן עוברים על צומת פעם אחת עבור כל צומת שמעליו: O(n·h). בעץ עם 14 רמות לכל היותר, עץ מלא של 16,383 צמתים דורש כ־2 × 10^5 צעדים. שרשרת של n צמתים תדרוש O(n²).

אלגוריתם

הגדירו את height(i) כ־0 עבור אינדקס שמעבר לסוף או עבור -1, וכ־1 + max(height(2*i+1), height(2*i+2)) עבור צומת ממשי.
עברו על כל אינדקס i שמכיל צומת ממשי.
אם height(2*i+1) ו־height(2*i+2) שונים ביותר מ־1, החזירו false.
אם הלולאה מסתיימת ללא כשל, החזירו true.

def isBalanced(root):
    n = len(root)

    def height(i):
        # The number of nodes on the longest downward path from index i.
        if i >= n or root[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    # Check every real node, measuring both subtrees from scratch.
    for i in range(n):
        if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
            return False
    return True

מעבר אחד בסדר פוסט־סדרי שמדווח על גובה או על כישלון

האינטואיציה

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

כשל למטה חייב גם הוא לעבור כלפי מעלה. גובה אמיתי לעולם אינו שלילי, לכן השתמש ב־-1 עבורו: קריאה מחזירה -1 כאשר אחד הילדים החזיר -1 או כאשר הגבהים של הילדים שונים ביותר מ־1. בדוגמה השנייה, ה־3 רואה את הגבהים 2 ו־0 ומחזיר -1, והשורש מעביר אותו הלאה בלי לבקר בצד ימין שלו.

לא נכנסים לאף צומת פעמיים, לכן זמן הריצה הוא O(n), עם O(h) קריאות במחסנית.

אלגוריתם

כתבו check(i). עבור אינדקס שחורג מהסוף או עבור -1, החזירו 0.
חשבו left = check(2*i+1). אם הוא -1, החזירו -1.
חשבו right = check(2*i+2). אם הוא -1, או שההפרש בין left ל-right גדול מ-1, החזירו -1.
אחרת, החזירו 1 + max(left, right).
החזירו אם check(0) אינו -1.

def isBalanced(root):
    n = len(root)

    def check(i):
        # The height of the subtree at index i, or -1 if it is not balanced.
        if i >= n or root[i] == -1:
            return 0
        left = check(2 * i + 1)
        if left == -1:
            return -1
        right = check(2 * i + 2)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(0) != -1

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

בדיקה של השורש בלבד. בדוגמה השנייה לשני צדי השורש יש גובה 3, ובכל זאת הצומת 3 חורג ב־2.
השוואה בין העלה הרדוד ביותר לעלה העמוק ביותר. בעץ המאוזן הקטן ביותר שגובהו 6 יש עלים בעומקים 4 ו־6, וכל צומת בו עובר את הבדיקה.
אובדן של כישלון בדרך למעלה. אם ילד מחזיר -1 וההורה מחשב 1 + max(-1, 2), הכישלון הופך שוב לגובה.
שימוש באורך המערך כגובה. ערכי -1 בסוף גורמים למערך להיות ארוך יותר מעומק העץ.
ב־Lua וב־R, מערכים מתחילים ב־1. שמרו על אינדקסים של צמתים שמתחילים ב־0 עבור 2*i+1, וקראו את root[i + 1].

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

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

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

מה פירוש מאוזן בגובה עבור עץ בינארי?

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

האם עץ בינארי מלא תמיד מאוזן?

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

def isBalanced(root):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

root = [5, 2, 9, -1, -1, 7, 11]

הפלט הצפוי

true