Range Sum of BST

Q: מהי סיבוכיות הזמן של Range Sum of BST?

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

Q: למה אפשר לדלג על תתי־עצים ב־Range Sum of BST?

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

Q: האם אפשר לפתור את סכום הטווח ב-BST באמצעות מעבר בסדר עולה?

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

Q: האם כדאי להשתמש ברקורסיה או במחסנית עבור Range Sum of BST?

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

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

+10

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

כתבו פונקציה בשם rangeSumBST שמחזירה את סכום כל ערכי הצמתים v שעבורם low ≤ v ≤ high, או 0 כאשר אין ערכים בטווח הזה.

פונקציה

rangeSumBST(tree: integer-array, low: integer, high: integer) → integer

treeinteger-array: עץ החיפוש הבינארי בסדר רמות, כאשר ‎-1 מציין מקום ריק
lowinteger: הערך הקטן ביותר שיש לספור
highinteger: הערך הגדול ביותר שיש לספור
מחזירהinteger: סכום ערכי הצמתים בין low ל-high, כולל שניהם

אילוצים

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

דוגמאות

קלט: tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
פלט: 88
הסבר: הערכים מ־9 עד 31 הם 10, 12, 15, 20 ו־31, שסכומם 88. הערכים 3, 8 ו־40 נמצאים מחוץ לטווח.

קלט: tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
פלט: 0
הסבר: העץ מכיל את 25, את 50 ואת 75, ואף אחד מהם אינו נמצא בין 60 ל־70, ולכן הסכום הוא 0. ארבעת הערכים -1 מציינים את מקומות הילדים הריקים של 25 ושל 75.

קלט: tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
פלט: 4
הסבר: כאשר low ו-high הם שניהם 4, רק צומת שערכו 4 נחשב. ה-4 באינדקס 4 הוא הילד הימני של 2, ולכן התשובה היא 4.

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

שאלת המשך

אם היית צריך לענות על אלפי שאילתות שונות של (low, high) באותו עץ, איך היית יכול לענות על כל אחת מהן בזמן O(log n)?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

בקרו בכל צומת

האינטואיציה

ראשית, איך נעים במערך. לצומת באינדקס i יש בן שמאלי באינדקס 2*i+1 ובן ימני באינדקס 2*i+2. בן נחשב לצומת ממשי רק אם האינדקס שלו נמצא בתוך המערך והערך שם אינו -1. בתוך [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15], לשורש 20 יש את 8 ואת 31 באינדקסים 1 ו-2, לצומת 12 באינדקס 4 יש את 10 ואת 15 באינדקסים 9 ו-10, ולצומת 31 יש מקום שמאלי ריק באינדקס 5.

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

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

אלגוריתם

דחפו את אינדקס השורש 0 למחסנית והגדירו total = 0.
הוציאו אינדקס i מהמחסנית. אם low ≤ tree[i] ≤ high, הוסיפו את tree[i] ל־total.
דחפו את 2*i+1 ואת 2*i+2 כאשר הם נמצאים בתוך המערך ואינם -1.
כשהמחסנית ריקה, החזירו את total.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append(left)
        if right < n and tree[right] != -1:
            stack.append(right)
    return total

גזמו לפי סדר עץ החיפוש

האינטואיציה

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

בדוגמה הראשונה, שבה הטווח הוא [9, 31], הערך 31 שווה ל-high, ולכן הילד הימני שלו, 40, לעולם לא נדחף למחסנית. הערך 8 קטן מ-low, ולכן הילד השמאלי שלו, 3, נדלג, בעוד שהילד הימני שלו, 12, עדיין ייבדק, כי ערכים שבין 8 ל-20 יכולים להיות בטווח.

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

אלגוריתם

דחפו את אינדקס השורש 0 למחסנית והגדירו total = 0.
הוציאו אינדקס i וקראו את v = tree[i]. אם low ≤ v ≤ high, הוסיפו את v ל-total.
אם v > low, דחפו את הילד השמאלי 2*i+1 אם הוא קיים.
אם v < high, דחפו את הילד הימני 2*i+2 אם הוא קיים.
כשהמחסנית ריקה, החזירו את total.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        # Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
        if value > low and left < n and tree[left] != -1:
            stack.append(left)
        if value < high and right < n and tree[right] != -1:
            stack.append(right)
    return total

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

רוב התשובות השגויות נובעות מהגבולות של הטווח או של המערך.

שימוש בהשוואות מחמירות. שני הקצוות כלולים, ולכן צומת ששווה ל־low או ל־high נחשב.
גיזום מוקדם מדי, בצעד אחד. כאשר v שווה ל־low, אפשר לדלג על תת־העץ השמאלי, אבל כאשר v הוא low + 1 אי אפשר: ייתכן שהוא מכיל את low עצמו.
עצירה בצומת שמחוץ לטווח. לצומת שמתחת ל־low עדיין עשוי להיות תת־עץ ימני מלא בערכים שבטווח, לכן יש לדלג רק על הצד שכללי הסדר שוללים.
קריאת אינדקס של צאצא מעבר לסוף המערך. בדקו 2*i+1 < tree.length לפני קריאת הערך, והתייחסו ל־-1 כאילו אין צאצא.
בלבול בהיסט ב־Lua וב־R, שבהן מערכים מתחילים ב־1. השאירו את אינדקסי הצמתים מבוססי־0 עבור החישוב 2*i+1, וקראו את tree[i + 1].

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

מהי סיבוכיות הזמן של Range Sum of BST?

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

למה אפשר לדלג על תתי־עצים ב־Range Sum of BST?

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

האם אפשר לפתור את סכום הטווח ב-BST באמצעות מעבר בסדר עולה?

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

האם כדאי להשתמש ברקורסיה או במחסנית עבור Range Sum of BST?

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

Python

def rangeSumBST(tree, low, high):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]
low = 9
high = 31

צפוי