Validate Binary Search Tree

Q: למה בדיקת כל צומת מול ילדיו אינה מספיקה כדי לאמת עץ חיפוש בינארי (BST)?

הכלל חל על תתי־עצים שלמים. צומת שנמצא עמוק בתת־העץ הימני של השורש חייב להיות גדול מהשורש, גם אם הוא הילד השמאלי של צומת גדול ממנו בהרבה. ב־ [10, 5, 15, -1, -1, 6, 20] , ה־ 6 הוא ילד שמאלי תקין של 15 , אבל הוא נמצא מימין ל־ 10 , ולכן העץ אינו עץ חיפוש. צריך להתחשב בגבולות של כל אחד מאבות הצומת, ולא רק של ההורה.

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

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

Q: האם אפשר לאמת עץ חיפוש בינארי באמצעות מעבר בסדר האמצעי בלי לאחסן כל ערך?

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

Q: האם עץ חיפוש בינארי יכול להכיל ערכים כפולים?

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

בינוניעץ חיפוש בינארי סריקת עצים

+10

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

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

פונקציה

isValidBST(tree: integer-array) → boolean

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

אילוצים

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

דוגמאות

קלט: tree = [8, 3, 12, 1, 6, 10, 15]
פלט: true
הסבר: כל צומת נמצא בצד הנכון של כל צומת שמעליו. בקריאה לפי הסדר (תת־העץ השמאלי, הצומת, תת־העץ הימני), הערכים מתקבלים כך: 1, 3, 6, 8, 10, 12, 15, בסדר עולה ממש, וזה מה שעץ חיפוש מספק.

קלט: tree = [10, 5, 15, -1, -1, 6, 20]
פלט: false
הסבר: כל צומת גדול מהצומת השמאלי שלו וקטן מהצומת הימני שלו, ובכל זאת העץ אינו תקין. הערך 6 באינדקס 5 נמצא בתת־העץ הימני של השורש 10, ולכן הוא חייב להיות גדול מ־10, והוא אינו כזה.

קלט: tree = [12, 7, 12]
פלט: false
הסבר: הבן הימני של השורש מכיל את 12, אותו ערך כמו השורש. תת-העץ הימני חייב להיות גדול יותר ממש, ולכן ערך זהה מפר את הכלל.

+16 בדיקות נסתרות בשליחה

שאלת המשך

ההורה של הצומת באינדקס i נמצא ב-(i-1)/2, בעיגול כלפי מטה. האם תוכל לעבור על העץ לפי הסדר עם מקום נוסף של O(1), תוך מעבר דרך ההורים במקום להשתמש במחסנית או ברקורסיה?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

השוו כל צומת עם תתי-העצים שלו

האינטואיציה

ראשית, איך לנוע במערך. לצומת באינדקס i יש בן שמאלי באינדקס 2*i+1 ובן ימני באינדקס 2*i+2. בן הוא צומת ממשי רק אם האינדקס שלו נמצא בתוך המערך והערך שם אינו -1. ב־[10, 5, 15, -1, -1, 6, 20], לשורש 10 יש את 5 ואת 15 באינדקסים 1 ו־2, ול־15 יש את 6 ואת 20 באינדקסים 5 ו־6.

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

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

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

אלגוריתם

עבור על כל אינדקס i שהערך שלו אינו -1.
מצא את הערך הגדול ביותר בתת־העץ השמאלי שמתחיל ב־2*i+1, או -1 אם המקום הזה ריק.
מצא את הערך הקטן ביותר בתת־העץ הימני שמתחיל ב־2*i+2, או 100001 אם המקום הזה ריק.
אם הערך הגדול ביותר גדול או שווה ל־tree[i], או שהערך הקטן ביותר קטן או שווה ל־tree[i], החזר false.
אחרי הצומת האחרון, החזר true.

def isValidBST(tree):
    n = len(tree)

    def largest(i):
        # Largest value in the subtree at index i, or -1 when that spot is empty.
        if i >= n or tree[i] == -1:
            return -1
        return max(tree[i], largest(2 * i + 1), largest(2 * i + 2))

    def smallest(i):
        # Smallest value in the subtree at index i, or 100001 when that spot is empty.
        if i >= n or tree[i] == -1:
            return 100001
        return min(tree[i], smallest(2 * i + 1), smallest(2 * i + 2))

    for i in range(n):
        if tree[i] == -1:
            continue
        # Everything on the left must be smaller, everything on the right larger.
        if largest(2 * i + 1) >= tree[i] or smallest(2 * i + 2) <= tree[i]:
            return False
    return True

ערכי מעבר בסדר תוכי חייבים לעלות באופן ממש strict

האינטואיציה

בסריקה בסדר-תוך מבקרים בתת-העץ השמאלי, אחר כך בצומת, ואז בתת-העץ הימני. בעץ חיפוש בינארי הסדר הזה ממוין: כל מה שנמצא משמאל קטן יותר, ולכן מופיע קודם, וכל מה שנמצא מימין גדול יותר, ולכן מופיע אחר כך. הדוגמה הראשונה נקראת 1, 3, 6, 8, 10, 12, 15.

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

לכן סרקו את העץ לפי הסדר, אספו את הערכים ובדקו כל ערך מול הערך שלפניו. הדוגמה השנייה נקראת 5, 10, 6, 15, 20: הירידה מ-10 ל-6 חושפת צומת שנמצא בצד הלא נכון. הדוגמה השלישית נקראת 7, 12, 12, וה-12 החוזר נכשל בבדיקה המחמירה. מבקרים בכל צומת פעם אחת, בזמן O(n), והרשימה תופסת מקום O(n).

אלגוריתם

כתוב את walk(i): אם המקום ריק, עצור; אחרת עבור אל 2*i+1, הוסף את tree[i], ואז עבור אל 2*i+2.
קרא ל־walk(0) כדי לאסוף את הערכים לפי הסדר.
עבור כל מיקום k החל מ־1, אם values[k-1] ≥ values[k], החזר false.
החזר true.

def isValidBST(tree):
    n = len(tree)
    values = []

    def walk(i):
        # Left subtree, then the node, then the right subtree.
        if i >= n or tree[i] == -1:
            return
        walk(2 * i + 1)
        values.append(tree[i])
        walk(2 * i + 2)

    walk(0)
    # A search tree read in order gives strictly increasing values.
    for k in range(1, len(values)):
        if values[k - 1] >= values[k]:
            return False
    return True

העבר את הטווח המותר מטה לאורך העץ

האינטואיציה

התבוננו בכלל מנקודת המבט של צומת. כל אחד מאבותיו מציב לו גבול אחד. אם הצומת נמצא בתת־העץ השמאלי של אב שמכיל את a, הערך שלו חייב להיות קטן מ־a; אם הוא נמצא בתת־העץ הימני, הוא חייב להיות גדול מ־a. כל הגבולות האלה יחד יוצרים טווח פתוח אחד (low, high), והצומת נמצא במקום הנכון בדיוק כאשר הערך שלו נמצא ממש בתוך הטווח הזה.

אפשר לבנות את הטווח בדרך למטה. לשורש אין גבול. כשעוברים מצומת שמכיל את v לילד השמאלי שלו, משאירים את low כפי שהוא ומורידים את high ל־v; כשעוברים לילד הימני, משאירים את high כפי שהוא ומעלים את low ל־v. הגבול החדש תמיד הדוק יותר מזה שהוא מחליף, כי v עצמו עבר את הבדיקה מול הטווח הקודם.

בדוגמה השנייה, 15 מקבל את הטווח (10, no limit) ומעביר אותו לילד השמאלי שלו בתור (10, 15). 6 קטן מ־10, ולכן הבדיקה נכשלת מיד, בלי לבדוק אף צומת אחר. הערכים נמצאים בין 0 ל־10^5, ולכן -1 ו־100001 משמשים בתור "ללא גבול".

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

אלגוריתם

הכניסו למחסנית את (0, -1, 100001): את האינדקס של השורש ואת הטווח הפתוח ללא גבול ממשי.
הוציאו מהמחסנית את (i, low, high). אם tree[i] אינו נמצא ממש בין low לבין high, החזירו false.
אם הילד השמאלי 2*i+1 קיים, הכניסו אותו למחסנית עם הטווח (low, tree[i]).
אם הילד הימני 2*i+2 קיים, הכניסו אותו למחסנית עם הטווח (tree[i], high).
כשהמחסנית ריקה, החזירו true.

def isValidBST(tree):
    n = len(tree)
    # Each entry: a node index and the open range (low, high) its value must fall in.
    # -1 and 100001 lie outside every allowed value, so they mean "no limit".
    stack = [(0, -1, 100001)]
    while stack:
        i, low, high = stack.pop()
        value = tree[i]
        if not (low < value < high):
            return False
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append((left, low, value))  # the left side must stay below value
        if right < n and tree[right] != -1:
            stack.append((right, value, high))  # the right side must stay above value
    return True

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

רוב התשובות השגויות בודקות מעט מדי, או בודקות את הדבר הנכון באמצעות השוואה שגויה.

השוואת צומת רק לילדים שלו. ב-[10, 5, 15, -1, -1, 6, 20] כל זוג של הורה וילד נראה תקין, אבל ה-6 עדיין חורג מהגבול שנקבע על ידי השורש שתי רמות מעליו.
מתן אפשרות לערכים שווים. הסדר קשיח בשני הצדדים, לכן [12, 7, 12] אינו תקין. השתמשו ב-low < v < high וב-values[k-1] < values[k], ולעולם לא ב-≤.
העברת הערך של ההורה בלבד כלפי מטה. ילד שמאלי זקוק לשני הגבולות: מתחת להורה שלו ומעל כל גבול תחתון שהיה להורה. העבירו את הטווח המלא.
בחירת ערך של „ללא גבול” שצומת יכול להכיל. הערכים מתחילים ב-0, לכן גבול תחתון של 0 ידחה צומת תקין שמכיל 0, כמו ב-[0]. התחילו מתחת לכל הערכים המותרים.
קריאה מעבר לסוף המערך. בדקו 2*i+1 < tree.length לפני קריאת ילד, והתייחסו ל--1 כאילו אין ילד.
בלבול בהיסט ב-Lua וב-R, שבהן מערכים מתחילים ב-1. השאירו את אינדקסי הצמתים מבוססי 0 עבור החישוב 2*i+1, וקראו את tree[i + 1].

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

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

הכלל חל על תתי־עצים שלמים. צומת שנמצא עמוק בתת־העץ הימני של השורש חייב להיות גדול מהשורש, גם אם הוא הילד השמאלי של צומת גדול ממנו בהרבה. ב־[10, 5, 15, -1, -1, 6, 20], ה־6 הוא ילד שמאלי תקין של 15, אבל הוא נמצא מימין ל־10, ולכן העץ אינו עץ חיפוש. צריך להתחשב בגבולות של כל אחד מאבות הצומת, ולא רק של ההורה.

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

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

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

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

האם עץ חיפוש בינארי יכול להכיל ערכים כפולים?

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

Python

def isValidBST(tree):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

tree = [8, 3, 12, 1, 6, 10, 15]

צפוי

true

Validate Binary Search Tree

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

השוו כל צומת עם תתי-העצים שלו

ערכי מעבר בסדר תוכי חייבים לעלות באופן ממש strict

העבר את הטווח המותר מטה לאורך העץ

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

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

בעיות דומות