Kth Smallest Element in a BST
מקבלים עץ חיפוש בינארי כמערך root בסדר ערימה: השורש נמצא באינדקס 0, הילדים של אינדקס i נמצאים באינדקסים 2*i+1 (שמאל) ו-2*i+2 (ימין), ו--1 מסמן מקום ריק. ייתכן שבסוף המערך יש ערכי -1 נוספים. בכל צומת, תת-העץ השמאלי מכיל רק ערכים קטנים יותר ותת-העץ הימני רק ערכים גדולים יותר.
יש להחזיר את הערך הקטן ה-k ביותר בעץ, בספירה החל מ-1.
פונקציה
- rootinteger-array
- עץ החיפוש הבינארי לפי סדר הרמות, כאשר -1 מציין מקום ריק
- kinteger
- המיקום שיש למצוא בסדר עולה, החל מ־1
- מחזירהinteger
- הערך ה־k הקטן ביותר בעץ
אילוצים
1 ≤ root.length ≤ 32767- כל
root[i]הוא-1או ערך שמקיים0 ≤ root[i] ≤ 105. root[0]לעולם אינו-1, ולכן יש בעץ לפחות צומת אחד.- ייתכן שבמערך יהיו ערכי
-1נוספים אחרי הצומת האחרון. - גם שני הצאצאים של מקום ריק ריקים, והעומק הוא לכל היותר
14. - כלל הסדר חל בכל צומת, ולכן שום ערך אינו מופיע פעמיים.
1 ≤ k ≤מספר הצמתים בעץ.
דוגמאות
- קלט
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- פלט
- 29
- הסבר
- הערכים בסדר עולה הם
6, 17, 22, 29, 41, 65, 90, והערך הרביעי הוא29. זהו הגדול ביותר מבין ארבעת הערכים בתת־העץ השמאלי של השורש.
- קלט
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- פלט
- 2
- הסבר
- הערך הקטן ביותר נמצא בקצה המסלול שממשיך שמאלה:
12,5,2. ה־7שמתחת ל־9והריפוד-1אינם משנים זאת.
שאלת המשך
אם העץ משתנה לעיתים קרובות ואתה מתבקש למצוא את הערך הקטן ה־k פעמים רבות, מה כל צומת יכול לשמור כדי שכל שאילתה תיקח O(h)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
איזה סוג מעבר בעץ חיפוש בינארי מציג את הערכים שלו מהקטן לגדול?
מעבר בתת-העץ השמאלי, לאחר מכן בצומת, ולאחר מכן בתת-העץ הימני מניב סדר ממוין. הערך ה־
kשמתקבל במעבר הזה הוא התשובה, ולכן אפשר לעצור שם.השתמש במחסנית. מהצומת הנוכחי, דחוף צמתים למחסנית תוך כדי מעבר לילד השמאלי. שלוף את האיבר העליון וספור אותו; עצור בשליפה ה־
k. אחרת, עבור לילד הימני של הצומת שנשלף במיקום2*i+2וחזור על הפעולה.
פתרון
מעבר בסדר (תת־העץ השמאלי, הצומת, תת־העץ הימני) קורא את הערכים בעץ חיפוש בינארי בסדר עולה, ולכן הערך ה־k שהוא מגיע אליו הוא התשובה. בצעו את המעבר בעזרת מחסנית משלכם ועצרו שם; אין צורך במיון.
אספו כל ערך ומיינו
האינטואיציה
התעלמו מהמבנה: השאירו כל איבר שאינו -1, מיינו והחזירו את המיקום k-1. בדוגמה הראשונה הרשימה הממוינת היא 6, 17, 22, 29, 41, 65, 90, ובמיקום 3 נמצא 29.
הפתרון נכון לכל עץ, מסודר או לא. וזה גם המחיר שלו: הוא מתעלם מהסדר שכבר קיים בעץ, ומשלם O(n log n) עבור המיון ו־O(n) זיכרון עבור ההעתקה.
אלגוריתם
- אסוף כל איבר של
rootשאינו-1. - מיין את הערכים שנאספו בסדר עולה.
- החזר את הערך במיקום
k-1.
def kthSmallest(root, k):
values = [v for v in root if v != -1] # every node, in any order
values.sort()
return values[k - 1]מעבר בסדר־תוך לרשימה
האינטואיציה
מתחת לכל צומת, תת־העץ השמאלי מכיל רק ערכים קטנים יותר, ותת־העץ הימני רק ערכים גדולים יותר. מבקרים בתת־העץ השמאלי, אחר כך בצומת, ואז בתת־העץ הימני, ועושים אותו הדבר בכל תת־עץ: כל צומת מופיע אחרי כל הערכים הקטנים ממנו ולפני כל הערכים הגדולים ממנו, ולכן הפלט ממוין. בדוגמה הראשונה הסריקה מניבה 6, 17, 22, 29, 41, 65, 90.
מעבר אחד מחליף את המיון: זמן O(n), ושטח O(n) עבור הרשימה. הוא עדיין מבקר בכל העץ, אפילו עבור k = 1, כשהתשובה נמצאת בקצה הנתיב השמאלי ביותר.
אלגוריתם
- כתבו את
inorder(i): החזירו ערך בנקודה ריקה (מעבר לסוף או-1). - אחרת, קראו ל־
inorder(2*i+1), הוסיפו אתroot[i]לרשימה, ואז קראו ל־inorder(2*i+2). - קראו ל־
inorder(0). - החזירו את האיבר ברשימה במיקום
k-1.
def kthSmallest(root, k):
n = len(root)
values = []
def inorder(i):
if i >= n or root[i] == -1:
return
inorder(2 * i + 1) # smaller values first
values.append(root[i])
inorder(2 * i + 2) # then larger ones
inorder(0)
return values[k - 1] # values is sortedמעבר איטרטיבי בסדר inorder שנעצר ב־k
האינטואיציה
מחסנית מפורשת מאפשרת לעצור את הסריקה באמצע. לכו שמאלה ככל האפשר, ודחפו כל צומת למחסנית. הצומת שבראש המחסנית הוא הערך הקטן ביותר שעדיין לא נספר, כי כל הערכים הקטנים ממנו נמצאים בתת-העץ השמאלי שלו, שהוא ריק או שכבר נספר. שלפו אותו וספרו אותו; תת-העץ הימני שלו הוא הבא בסדר הממויין.
עבור k = 4 בדוגמה הראשונה: דחפו את 41, את 17 ואת 6. שלפו את 6, ואז את 17, ועברו לילד הימני שלו: דחפו את 29 ואת 22. שלפו את 22, ואז את 29, הרביעי. הסריקה אינה מגיעה כלל אל 65 או אל 90.
המחסנית מכילה לכל היותר צומת אחד בכל רמה, ולכן המרחב הוא O(h). הסריקה יורדת פעם אחת ואז שולפת k פעמים: זמן של O(h + k).
אלגוריתם
- התחל עם מחסנית ריקה ועם
i = 0. - כל עוד
iהוא צומת אמיתי, דחוף אותו למחסנית ועבור אל2*i+1. - שלוף את האיבר העליון והצב אותו ב-
i, והפחת1מ-k. - אם
kהוא עכשיו0, החזר אתroot[i]. - אחרת עבור אל
2*i+2וחזור לשלב 2.
def kthSmallest(root, k):
n = len(root)
stack = [] # nodes whose left side is being visited, deepest on top
i = 0
while True:
while i < n and root[i] != -1: # go as far left as you can
stack.append(i)
i = 2 * i + 1
i = stack.pop() # the smallest value not counted yet
k -= 1
if k == 0:
return root[i]
i = 2 * i + 2 # then everything in its right subtree
מלכודות ומקרי קצה
- קריאת המערך לפי סדר האינדקסים. הסדר לפי רמות אינו ממוין: הדוגמה הראשונה מתחילה ב־
41, 17, 65. - טעות של אחד ב־
k. הספירה מתחילה מ־1: מחזירים את המיקוםk-1ברשימה, ומפסיקים את המעבר כשהספירה מגיעה ל־k. - דילוג על תת־העץ הימני אחרי הוצאה מהמחסנית. בדוגמה השנייה
9ו־7נמצאים בתת־העץ הימני של5, והמעבר לעולם לא יספור אותם. - התייחסות לילד חסר כאילו הוא קיים. ילד חסר אם האינדקס שלו מעבר לסוף או מכיל
-1:22נמצא באינדקס9, לכן הילדים שלו19ו־20נמצאים מעבר לסוף. - מערכים ב־Lua וב־R מתחילים ב־1. השאירו את אינדקסי הצמתים מבוססי 0 עבור
2*i+1וקראו אתroot[i + 1].
שאלות נפוצות3
מהי סיבוכיות הזמן למציאת האיבר ה־k הקטן ביותר ב־BST?
המעבר האיטרטיבי בסדר תוכי אורך O(h + k) זמן וצורך O(h) מקום נוסף עבור עץ בעומק h. במקרה הגרוע ביותר, כאשר k = n או כשהעץ בנוי בצורת מסלול, הסיבוכיות היא O(n).
איך מוצאים את האיבר ה־k בגודלו ב־BST?
שקפו את הסריקה: תת-העץ הימני, אחר כך הצומת, ואז תת-העץ השמאלי. כך מתקבלים הערכים בסדר יורד. התקדמו ימינה ככל האפשר תוך דחיפה, הוציאו איבר וספרו, ועברו לילד השמאלי אחרי כל הוצאה. ההוצאה ה-k היא הערך ה-k בגודלו.
איך עוצרים מעבר רקורסיבי בסדר־אמצעי בערך ה־k?
יש לשמור מונה מחוץ לרקורסיה, שמתחיל ב־k. יש להפחית 1 לאחר שתת־העץ השמאלי של צומת חוזר, ולתעד את ערך הצומת כשהמונה מגיע ל־0. לאחר כל קריאה, יש לחזור מיד אם התשובה תועדה. כך הרקורסיה תואמת לגרסת המחסנית: זמן O(h + k), מקום O(h).
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def kthSmallest(root, k):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
ארגומנטים
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
הפלט הצפוי
29