Range Sum of BST
עץ חיפוש בינארי מאוחסן במערך tree לפי סדר רמות: השורש נמצא באינדקס 0, הילדים של הצומת באינדקס i נמצאים ב-2*i+1 (משמאל) וב-2*i+2 (מימין), ו--1 מסמן מקום ריק. בעץ חיפוש בינארי, כל ערך בתת-העץ השמאלי של צומת קטן מערך הצומת, וכל ערך בתת-העץ הימני שלו גדול יותר.
החזר את סכום הערכים של כל הצמתים v שעבורם low ≤ v ≤ high, או 0 אם אין כאלה.
פונקציה
- treeinteger-array
- עץ החיפוש הבינארי בסדר רמות, עם -1 עבור מקום ריק
- lowinteger
- הערך הקטן ביותר שיש לספור
- highinteger
- הערך הגדול ביותר לספירה
- מחזירהinteger
- סכום ערכי הצמתים בין low ל-high, כולל שניהם
אילוצים
1 ≤ tree.length ≤ 32767- כל
tree[i]הוא-1או ערך שמקיים0 ≤ tree[i] ≤ 105. tree[0]לעולם אינו-1, ולכן יש בעץ לפחות צומת אחד.- המערך עשוי להסתיים בערכי
-1נוספים אחרי הצומת האחרון. - גם שני הילדים של מקום ריק ריקים, והעומק הוא לכל היותר
14. - העץ הוא עץ חיפוש בינארי תקין, ולכן כל הערכים בו שונים זה מזה.
0 ≤ low ≤ high ≤ 105- התשובה נכנסת למספר שלם signed של 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.
שאלת המשך
אם היית צריך לענות על אלפי שאילתות שונות של (low, high) באותו עץ, איך היית יכול לענות על כל אחת מהן בזמן O(log n)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
מעבר בכל צומת וחיבור הערכים בטווח נותנים את התשובה הנכונה. מה סדר עץ החיפוש אומר לך על הערכים שמתחת לצומת?
כל מה שנמצא בתת־העץ השמאלי של צומת קטן מהצומת, וכל מה שנמצא בתת־העץ הימני שלו גדול ממנו. אם ערך הצומת הוא לכל היותר
low, האם ייתכן שמשהו בצד השמאלי שלו יהיה בטווח?עברו לאורך העץ בעזרת מחסנית של אינדקסים מהשורש. הוסיפו את הערך של צומת כשהוא בטווח, דחפו את הילד השמאלי שלו באינדקס
2*i+1רק כשהערך גדול מ־low, ואת הילד הימני שלו באינדקס2*i+2רק כשהערך קטן מ־high.
פתרון
מעבר בכל צומת וחיבור הערכים שנמצאים בטווח הוא נכון. סדר עץ החיפוש מאפשר לך לבצע פחות עבודה: הערך של צומת מציין לך באיזה צד נמצאים הערכים הקטנים יותר והגדולים יותר, ולכן לא פותחים תת־עץ שלא יכול להגיע לטווח.
בקרו בכל צומת
האינטואיציה
ילד הוא צומת אמיתי רק אם האינדקס שלו נמצא בתוך המערך והערך שם אינו -1. בדוגמה הראשונה, ל-12 באינדקס 4 יש את 10 ואת 15 באינדקסים 9 ו-10, ול-31 באינדקס 2 יש מקום שמאלי ריק באינדקס 5.
כל ערך בטווח נמצא בצומת כלשהו, ולכן מעבר עם מחסנית שמגיע לכל צומת ומוסיף את הערכים שעבורם low ≤ v ≤ high מחזיר את הסכום הנכון. הוא מתעלם מסדר עץ החיפוש, ולכן נוגע בכל n הצמתים גם כשהטווח מכיל רק כמה ערכים.
אלגוריתם
- דחוף את אינדקס השורש
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, אף אחד מהם אינו בטווח, ולכן מדלגים על עץ המשנה הזה. אם v ≥ high, לעץ המשנה הימני יש רק ערכים גדולים מ־high, ולכן מדלגים עליו. בדוגמה הראשונה, 31 שווה ל־high, ולכן הילד הימני שלו, 40, לעולם אינו נדחף. 8 קטן מ־low, ולכן מדלגים על הילד השמאלי שלו, 3, אבל מבקרים בילד הימני שלו, 12, משום שערכים שבין 8 ל־20 יכולים להיות בטווח.
מבקרים ב־k הערכים שבטווח, ובצמתים שבכל היותר שני מסלולים מהשורש: זמן ריצה של O(h + k) עבור עומק h. כאשר הטווח מכסה את העץ כולו, זמן הריצה עדיין O(n).
אלגוריתם
- דחפו את אינדקס השורש
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 = 4, חייבת לכלול את4. - גיזום צעד אחד מוקדם מדי. כאשר
v = lowאפשר לוותר על תת-העץ השמאלי, אבל כאשרv = low + 1ייתכן שהוא מכיל אתlowעצמו. - ויתור על שני הצדדים של צומת שמחוץ לטווח. הערך
8בדוגמה הראשונה קטן מ-low, אך תת-העץ הימני שלו מכיל את10,12ו-15. - קריאת צומת ילד מעבר לסוף המערך. יש לבדוק
2*i+1 < tree.lengthלפני הקריאה, ולהתייחס אל-1כאילו אין צומת ילד. - ב-Lua וב-R המערכים מתחילים ב-1: יש להשאיר את האינדקסים של הצמתים מבוססי 0 לצורך החישוב
2*i+1, ולקרוא אתtree[i + 1].
שאלות נפוצות3
מהי סיבוכיות הזמן של סכום טווחים בעץ חיפוש בינארי?
המעבר המצומצם מבקר בצמתים k שבטווח, וכן בצמתים שנמצאים לכל היותר בשני מסלולים מהשורש: זמן O(h + k) עבור עץ בעומק h, ו-O(n) כאשר כל הערכים נמצאים בטווח. המחסנית או הרקורסיה דורשות מקום O(h).
האם אפשר לפתור את סכום הטווח ב-BST באמצעות מעבר בסדר עולה?
כן. מעבר בסדר עולה מציג את הערכים בסדר עולה, לכן מוסיפים ערכים כשהם מגיעים ל־low ועוצרים בערך הראשון שגדול מ־high. העצירה המוקדמת חוסכת עבודה בצד ימין של העץ; גיזום חוסך עבודה בשני הצדדים.
האם כדאי להשתמש ברקורסיה או במחסנית כדי לחשב את סכום הטווח בעץ חיפוש בינארי?
שניהם עובדים. כאן העומק הוא לכל היותר 14, כך שהרקורסיה נשארת רדודה. מחסנית מפורשת מונעת חריגה ממגבלת הרקורסיה בעץ גבוה עם אלפי רמות.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def rangeSumBST(tree, low, high):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15] low = 9 high = 31
הפלט הצפוי
88