Lowest Common Ancestor of a BST
ניתן לך עץ חיפוש בינארי המאוחסן במערך tree לפי סדר רמות, ושני ערכים p ו-q שמופיעים בו. השורש נמצא באינדקס 0, הילדים של הצומת באינדקס i נמצאים באינדקסים 2*i+1 (שמאלי) ו-2*i+2 (ימני), -1 מציין מקום ריק, וייתכן שבסוף המערך יופיעו ערכי -1 נוספים. בעץ חיפוש בינארי, כל ערך בתת-העץ השמאלי של צומת קטן מערך הצומת, וכל ערך בתת-העץ הימני שלו גדול ממנו.
כתבו פונקציה בשם lowestCommonAncestor שמחזירה את הערך של האב הקדמון המשותף הנמוך ביותר של p ו-q: הצומת העמוק ביותר שיש את שניהם בתת-העץ שלו. צומת נחשב לחלק מתת-העץ של עצמו, ולכן אם p נמצא מעל q, התשובה היא p עצמו.
פונקציה
- treeinteger-array
- עץ החיפוש הבינארי לפי סדר הרמות, כאשר -1 מציין מקום ריק
- pinteger
- הערך הראשון שיש למצוא
- qinteger
- הערך השני שיש למצוא
- מחזירהinteger
- הערך של הצומת העמוק ביותר שיש לו גם את p וגם את q בתת־העץ שלו
אילוצים
1 ≤ tree.length ≤ 32767- כל
tree[i]הוא-1או ערך שמקיים0 ≤ tree[i] ≤ 105. tree[0]לעולם אינו-1, ולכן יש בעץ לפחות צומת אחד.- המערך עשוי להסתיים בערכי
-1נוספים אחרי הצומת האחרון. - שני הילדים של מקום ריק גם הם ריקים, והעומק הוא לכל היותר
14. - העץ הוא עץ חיפוש בינארי תקין, ולכן כל הערכים בו שונים זה מזה.
pו-qהם ערכים של צמתים בעץ. הם יכולים להופיע בכל סדר, וייתכן שהם יהיו שווים.
דוגמאות
- קלט
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
- פלט
- 8
- הסבר
3הוא הילד השמאלי של8, ו־15נמצא מתחת ל־12, מימינו של8. כשעולים מכל אחד מהם, הצומת הראשון ששניהם מגיעים אליו הוא8, ולכן זו התשובה; גם השורש20הוא אב קדמון משותף, אבל גבוה יותר.
- קלט
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
- פלט
- 12
- הסבר
10הוא הילד השמאלי של12. צומת נחשב לאב קדמון של עצמו, ולכן בתת-העץ של12נמצאים שני הערכים, ובשום צומת שמתחתיו הם אינם נמצאים: התשובה היא12. הערכים יכולים להגיע בכל סדר; כאןpהוא הגדול יותר.
- קלט
- tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
- פלט
- 70
- הסבר
- גם
55וגם80גדולים יותר מהשורש50, ולכן שניהם נמצאים בצד ימין שלו. ב־70הם נפרדים:55קטן יותר ונמצא בצד שמאל (מתחת ל־60), ואילו80גדול יותר ונמצא בצד ימין. לכן70הוא התשובה.
+12 בדיקות נסתרות בשליחה
שאלת המשך
מה היית משנה אם ייתכן ש-p או q לא יהיו בעץ, והפונקציה תצטרך להחזיר -1 במקרה כזה?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
עמוד בשורש. אם גם
pוגםqקטנים מהערך שלו, באיזה תת־עץ נמצאות שתי הצמתים?כל עוד שני הערכים נמצאים באותו צד של הצומת הנוכחי, גם כל אב קדמון משותף בהמשך נמצא באותו צד. הצומת הראשון שבו הם אינם נמצאים באותו צד, או שהצומת מכיל אחד מהם, הוא הצומת הרצוי.
התחל באינדקס
0. כל עוד שני הערכים קטנים מ־tree[i], עבור אל2*i+1; כל עוד שניהם גדולים, עבור אל2*i+2. אחרת, החזר אתtree[i].
פתרון
בעץ בינארי רגיל אי אפשר לדעת היכן נמצא ערך בלי לחפש בשני הצדדים של כל צומת. עץ חיפוש אומר לך בכל צומת: ערכים קטנים יותר נמצאים משמאל, וגדולים יותר מימין. לכן מתחילים בשורש ומתקדמים לכיוון הצד שמכיל את שני הערכים. הצומת הראשון שבו הם מפסיקים להיות באותו צד הוא התשובה, ומוצאים אותו באמצעות מעקב אחר מסלול אחד, בלי להסתכל בשאר העץ.
חפש בכל העץ, בלי להתחשב בסדר
האינטואיציה
ראשית, איך נעים במערך. לצומת באינדקס i יש בן שמאלי באינדקס 2*i+1 ובן ימני באינדקס 2*i+2. בן הוא ממשי רק אם האינדקס שלו נמצא בתוך המערך והערך שם אינו -1. ב־[20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15], לשורש 20 יש את 8 ואת 31 באינדקסים 1 ו־2, ול־12 באינדקס 4 יש את 10 ואת 15 באינדקסים 9 ו־10.
השיטה הראשונה הזו פועלת על כל עץ בינארי. קריאה רקורסיבית ל־find(i) מדווחת מה מכילה תת־העץ באינדקס i. מקום ריק מדווח על -1. צומת שמכיל את p או את q מדווח על עצמו: או שהערך האחר נמצא מתחתיו, ואז הוא התשובה, או שהערך האחר נמצא במקום אחר, ואז צומת גבוה יותר יראה את שניהם. אחרת, הצומת שואל את שני ילדיו. אם שני הצדדים מדווחים על משהו, p נמצא בצד אחד ו־q בצד האחר, ולכן זה הצומת שבו הם נפגשים. אם רק צד אחד מדווח על משהו, מעבירים את הדיווח הזה כלפי מעלה.
עבור p = 3 ו־q = 15, ה־8 מקבל את האינדקס 3 מהבן השמאלי שלו ואת האינדקס 10 מהבן הימני שלו, ולכן הוא מדווח על עצמו. השורש מקבל את זה מהבן השמאלי שלו ואת -1 מהבן הימני שלו, ומעביר את ה־8 כלפי מעלה.
היא נכונה, אבל היא עשויה לבקר בכל צומת, בזמן O(n), עם O(h) עבור הרקורסיה. היא לעולם אינה משתמשת בסדר הערכים, שהוא כל המטרה של עץ חיפוש.
אלגוריתם
- כתבו
find(i). אם המקום ב-iריק (מעבר לסוף או-1), החזירו-1. - אם
tree[i]הואpאוq, החזירוi. - קראו ל-
findעם2*i+1ועם2*i+2. אם שניהם מצאו משהו, החזירוi. - אחרת, החזירו את הצד שמצא משהו, או
-1. - החזירו
tree[find(0)].
def lowestCommonAncestor(tree, p, q):
n = len(tree)
def find(i):
# In the subtree at index i: the index of the answer if both values are
# inside, the index of the one that is, or -1 when neither is.
if i >= n or tree[i] == -1:
return -1
if tree[i] == p or tree[i] == q:
return i
left = find(2 * i + 1)
right = find(2 * i + 2)
if left != -1 and right != -1:
return i # one value on each side: this node is the answer
return left if left != -1 else right
return tree[find(0)]השוו בין שני מסלולי החיפוש
האינטואיציה
כעת השתמשו בסדר. אפשר למצוא ערך בדרך שבה אמורים לחפש בעץ חיפוש: מתחילים בשורש, פונים שמאלה כשהערך קטן מהצומת, ימינה כשהוא גדול יותר, ועוצרים כשמוצאים אותו. המסלול הזה עובר בכל אחד מאבותיו של הערך ולא בשום צומת אחר, כי המסלול מהשורש לצומת הוא יחיד.
תעדו את המסלול של p ואת המסלול של q. שניהם מתחילים בשורש ועוברים באותם צמתים עד שהערכים פונים לכיוונים שונים. תחילת המסלול המשותפת היא רשימת האבות המשותפים שלהם, ולכן הערך המשותף האחרון הוא הנמוך ביותר. עבור 3 ו-15 המסלולים הם 20, 8, 3 ו-20, 8, 12, 15: הם חולקים את 20, 8, והתשובה היא 8. עבור 12 ו-10 המסלולים הם 20, 8, 12 ו-20, 8, 12, 10, והתשובה היא 12.
כל מסלול דורש צעד אחד לכל רמה, ולכן זמן הריצה הוא O(h), עד 14 צעדים כאן, ללא קשר למספר הצמתים בעץ. שתי הרשימות דורשות O(h) מקום.
אלגוריתם
- כתבו
path(target): התחילו באינדקס0, תעדו אתtree[i], עצרו כשהוא שווה ל-target, אחרת עברו אל2*i+1אםtargetקטן יותר ואל2*i+2אם הוא גדול יותר. - בנו את המסלול אל
pואת המסלול אלq. - עברו על שתי הרשימות מההתחלה כל עוד הערכים שלהן תואמים, וזכרו את ההתאמה האחרונה.
- החזירו את הערך המשותף האחרון.
def lowestCommonAncestor(tree, p, q):
def path(target):
# The values met on the way from the root down to target.
values = []
i = 0
while True:
values.append(tree[i])
if tree[i] == target:
return values
i = 2 * i + 1 if target < tree[i] else 2 * i + 2
to_p, to_q = path(p), path(q)
# Both paths start at the root; the answer is the last value they share.
answer = to_p[0]
for a, b in zip(to_p, to_q):
if a != b:
break
answer = a
return answerרד במורד העץ עד שהערכים מתפצלים
האינטואיציה
שני המסלולים מסכימים כל עוד p ו־q מתקדמים באותו כיוון, לכן אין צורך לשמור אותם. מתקדמים בשניהם בו־זמנית. בצומת שמכיל את v, אם שני הערכים קטנים מ־v, שניהם נמצאים בתת־העץ השמאלי, וכך גם כל אב קדמון משותף שנמצא מתחת ל־v: פונים שמאלה. אם שניהם גדולים יותר, פונים ימינה.
אחרת הגעתם ליעד. או שאחד הערכים קטן מ־v והאחר גדול ממנו, כך שהם נמצאים בתתי־עצים שונים ואין ילד של v שמכיל את שניהם; או שאחד מהם שווה ל־v, וצומת הוא אב קדמון של עצמו. כך או כך, v הוא הצומת העמוק ביותר שנמצא מעל שניהם.
בדוגמה השלישית, השורש 50 קטן גם מ־55 וגם מ־80, לכן פונים ימינה אל 70. שם 55 קטן יותר ו־80 גדול יותר: התשובה היא 70. בדוגמה השנייה מתקדמים מ־20 אל 8 ואז אל 12, ששווה ל־p, ועוצרים.
עוברים במסלול יחיד מהשורש, עם זוג השוואות אחד בכל רמה, לכן זמן הריצה הוא O(h) והזיכרון הוא O(1). שאר העץ לעולם אינו נקרא.
אלגוריתם
- מתחילים באינדקס
i = 0. - קוראים את
v = tree[i]. - אם
p < vוגםq < v, עוברים אל2*i+1וחוזרים על הפעולה. - אם
p > vוגםq > v, עוברים אל2*i+2וחוזרים על הפעולה. - אחרת מחזירים את
v.
def lowestCommonAncestor(tree, p, q):
i = 0 # start at the root
while True:
value = tree[i]
if p < value and q < value:
i = 2 * i + 1 # both are smaller: the answer is on the left
elif p > value and q > value:
i = 2 * i + 2 # both are larger: the answer is on the right
else:
return value # they split here, or one of them is this node
מלכודות ומקרי קצה
ההליכה קצרה, ולכן רוב הבאגים נובעים מתנאי העצירה שלה.
- שימוש ב־
≤וב־≥בבדיקות המעבר. כאשרp = 12ו־q = 10, הבדיקהp ≤ 12וגםq ≤ 12עוברת מעבר לתשובה אל10, ומשם ההליכה מחזירה10או יוצאת מהעץ. עוברים רק כאשר שני הערכים נמצאים ממש באותו צד. - הנחה ש־
p < q. הערכים יכולים להופיע בכל סדר. בדקו את שניהם ביחס לצומת, או החליפו ביניהם קודם כך ש־pיהיה הקטן יותר. - שוכחים שערך אחד יכול להיות האב הקדמון של האחר. במקרה כזה, התשובה היא הערך הזה עצמו, ולא ההורה שלו.
- מחזירים את האינדקס במקום את הערך. הפונקציה מחזירה
tree[i], ולא אתi. - מחפשים בכל העץ. כך מתקבלת התשובה הנכונה, אבל עוברים עד על פני כל הצמתים, כאשר מספיק לעבור במסלול אחד.
- מתבלבלים בהיסט ב־Lua וב־R, שבהן מערכים מתחילים ב־1. השאירו את אינדקסי הצמתים מבוססי־0 לצורך החישוב
2*i+1, וקראו אתtree[i + 1].
שאלות נפוצות4
מהי סיבוכיות הזמן של מציאת האב הקדמון המשותף הנמוך ביותר בעץ חיפוש בינארי (BST)?
המעבר מהשורש עוקב אחר מסלול אחד, ולכן הוא נמשך O(h) זמן עבור עץ בעומק h ודורש O(1) מקום נוסף. בעץ מאוזן הסיבוכיות היא O(log n); בעץ שצורתו כמסלול יחיד הסיבוכיות היא O(n).
במה ה-LCA בעץ חיפוש בינארי שונה מה-LCA בעץ בינארי?
בעץ בינארי רגיל ערך יכול להימצא בכל מקום, לכן מחפשים בשני תתי־העצים של כל צומת, והעבודה היא O(n). בעץ חיפוש, השוואת שני הערכים לערך של צומת מגלה לך באיזה צד נמצא כל אחד מהם, ולכן עוקבים אחר נתיב אחד מהשורש. שיטת החיפוש הרקורסיבית לעץ כללי עדיין עובדת בעץ חיפוש, אבל היא מתעלמת מהמידע הזה.
האם צומת יכול להיות האב הקדמון המשותף הנמוך ביותר של עצמו?
כן. צומת נחשב לאב קדמון של עצמו, לכן כאשר p נמצא מעל q, התשובה היא p. אותו כלל מחזיר את p כאשר שני הערכים שווים. הסריקה מטפלת בשני המקרים: היא נעצרת ברגע שהצומת הנוכחי שווה לאחד מהערכים.
למה ההליכה נעצרת בצומת הראשון שבו p ו־q מתפצלים?
באותו צומת ערך אחד קטן יותר והאחר גדול יותר, ולכן הם נמצאים בתתי־עצים שונים. כל צומת שמתחתיו נמצא רק באחד מתתי־העצים האלה ואינו יכול להכיל את שניהם. צומת הפיצול מכיל את שניהם, ואף צומת עמוק יותר אינו מכיל אותם, וזו בדיוק ההגדרה של האב הקדמון המשותף הנמוך ביותר.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def lowestCommonAncestor(tree, p, q):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] p = 3 q = 15
צפוי
8