אב קדמון משותף

נתון עץ בינארי ושני צמתים בעץ.
המשימה היא למצוא את האב הקדמון המשותף הראשון לשני הצמתים.
איך אני עושה את זה?

אני אתחיל כרגיל מדוגמאות.

בהנחה ונתון לי העץ בדוגמא והצמתים D ו-E האב הקדמון המשותף הראשון לצמתים הוא B.
גם A הוא אב קדמון משותף ל-D ו-E, אבל B קודם לו.
מה הכוונה בכך ש-B הוא אב קדמון ראשון ו-A הוא אב קדמון שני? הכוונה היא שהמרחק מכל אחד מהצמתים D ו-E ל-B קטן יותר מהמרחק מהם ל-A, וזה יהיה הקריטריון שאני אבדוק כדי לקבוע אב קדום ראשון.

מה לגבי הצמתים D ו-B? מה האב הקדמון המשותף שלהם?
כיוון ש-B הוא לא אב של עצמו, האב הקדמון המשותף היחיד של D ו-B הוא A.

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

איך הפעולה הזו מיתרגמת לאלגוריתם?

באלגוריתם אני לא יכולה לעלות “בו זמנית” משני צמתים ולעצור כשהם נפגשים, כיוון שהמרחק משני הצמתים לאב הקדמון יכול להיות שונה, ואז אם אעלה באותו קצב משני הצמתים (למשל, כל פעם אעלה צומת אחד למעלה), סביר להניח ששני המסלולים לעולם לא יפגשו זה את זה.

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

לדוגמא, אם הייתי רוצה למצוא את האב הקדמון המשותף הראשון של D ו-E בעץ הזה –

אם הייתי מתחילה מ-D ומסמנת את המסלול שלו כלפי מעלה הייתי מסמנת את B ו-A.

לאחר מכן הייתי עולה מ-E למעלה, מגיעה ל-B ומחזירה אותו כאב הקדמון המשותף.

אם הייתי מתחילה מ-E הייתי מסמנת את D,B ו-A במסלול שלו כלפי מעלה. לאחר מכן הייתי עולה מ-D למעלה, מגיעה ל-B ומחזירה אותו כאב קדמון משותף.

כלומר, האלגוריתם עובד, וזה לא כל כך משנה מאיזה צומת מתחילים.

מה הסיבוכיות של הפתרון הזה?

בעבור הצומת ממנו הייתי מתחילה הייתי צריכה לבצע את כל המסלול מהצומת לשורש. הסיבוכיות של המסלול היא במקרה הגרוע N, כש-N הוא המרחק בין הצומת הנמוכה יותר לשורש.

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

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

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

מה תהיה הסיבוכיות של האלגוריתם הזה?
הפעם הסיבוכיות תהיה (O(k כאשר k הוא המרחק בין הצומת המרוחק יותר לאב הקדמון המשותף.
במקרה הכי גרוע, המרחק בין הצומת המרוחק לאב הקדמון המשותף יכול להיות N-1 (למשל שיוצא ממנו שרוך אחד באורך N-1 וילד אחד נוסף, אבל הסיבוכיות תלויה רק במרחק ולא בגודל העץ.

מעולה, נראה כמו פתרון טוב, אפשר להתחיל לכתוב אלגוריתם.

def find_first_ancestor_recur(x,y):
	if x.visited:
		return x
	if y.visited:
		return y
	
	x.visited = True
	y.visited = True
	return find_first_ancestor_recur(x.parent,y.parent)

אני אנסה את האלגוריתם שלי על הדוגמא הראשונה –

find_first_ancestor_recur(D,E): D.visited = True E.visited = True return find_first_ancestor_recur(B,B) find_first_ancestor_recur(B,B): B.visited = True B.visited = True return find_first_ancestor_recur(A,A)

אוקי, הנה בעיה קטנה, האלגוריתם שלי דרך באותה נקודה ובכלל לא זיהה את זה.

אני אוסיף את הטיפול במקרה הזה לאלגוריתם.

def find_first_ancestor_recur(x,y):
	if x == y:
		return x
	if x.visited:
		return x
	if y.visited:
		return y
	
	x.visited = True
	y.visited = True
	return find_first_ancestor_recur(x.parent,y.parent)

אני אריץ את הדוגמא שוב –

find_first_ancestor_recur(D,E): D.visited = True E.visited = True return find_first_ancestor_recur(B,B) find_first_ancestor_recur(B,B): B == B → return B

אחלה, עכשיו אני אבדוק מה קורה בדוגמא השנייה –

find_first_ancestor_recur(D,E): D.visited = True E.visited = True return find_first_ancestor_recur(B,D) find_first_ancestor_recur(B,D): D.visited → return D

אוקי, הנה בעיה.

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

אם הצמתים הראשונות מסומנות כחלק מהמסלול, אז אחת מהן יכולה להחזור כהורה משותף.

כדי להימנע מהמצב הזה אני אכתוב פונקצייה עוטפת שעושה את הקריאה הראשונה לפונקציה הרקורסיבית.

def find_first_ancestor(x,y):
	return find_first_ancestor_recur(x.parent,y.parent)

מעולה.

עכשיו כדאי לבדוק קצת מקרי קיצון.

מה קורה אם שתי הצמתים המתקבלות הן אותה צומת? מה נרצה להחזיר במקרה כזה?

השאלה לא ממש מגדירה, אבל אני מניחה שלצומת יכול להיות אב קדום משותף עם עצמה – האב הישיר שלה.

אני אבדוק.

find_first_ancestor(E,E): find_first_ancestor_recur(D,D) find_first_ancestor_recur(D,D): D == D → return D

הדוגמא עובדת.

מה לגבי מקרה בו אחת הצמתים שלי היא השורש?

find_first_ancestor(A,E): find_first_ancestor_recur(None,D) find_first_ancestor_recur(D,D): None.visited → Failure

לא טוב.

אני אחשוב רגע מה אני רוצה שיקרה במקרה כזה – אם אחת הצמתים היא השורש אז אין לה אב, מכאן שגם אין לה אב קדמון משותף עם צומת אחרת.

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

def find_first_ancestor(x,y):
	if x.parent is None or y.parent is None:
		return
	return find_first_ancestor_recur(x.parent,y.parent)

האם יש עוד מקרי קיצון שאני יכולה לחשוב עליהם?

כן. מה קורה במקרה שבו אחת הצמתים מאוד קרובה לשורש והשנייה מאוד רחוקה? אני אגיע לשורש באמצע התהליך ואכשל באותה הנקודה בה נכשלתי מקודם.

כדאי להוסיף הגנה שעוצרת את העלייה במסלולים כשהגענו לשורש.

def find_first_ancestor_recur(x,y):
	if x is not None and y is not None and x == y:
		return x
	next_nodes = []
	for node in [x,y]:
		if node is not None:
			if node.visited:
				return node
			else:
				node.visited = True
		next_nodes.append(node.parent)
	return find_first_ancestor_recur(next_nodes[0],next_nodes[1])

אני אבדוק את התיקון שלי על דוגמא –

find_first_ancestor(C,E): find_first_ancestor_recur(A,D) find_first_ancestor_recur(A,D): None.visited → Failure next_nodes = [] node = A A.visited = True next_nodes = [None] node = D D.visited = True next_nodes = [None,B] return find_first_ancestor_recur(None,B) find_first_ancestor_recur(None,B): next_nodes = [] node = None next_nodes = [None] node = B B.visited = True next_nodes = [None,A] return find_first_ancestor_recur(None,A) find_first_ancestor_recur(None,A): next_nodes = [] node = None next_nodes = [None] node = A A.visited → return A

מה לגבי המקרה שבו find_first_ancestor_recur יקבל פעמיים None?

איך שהאלגוריתם בנוי עכשיו, אם גם x וגם y הם None אני אתקע בלולאה אינסופית שכל פעם תקרא לפונקציה הרקורסיבית עם x=None ו-y=None.

זה רע מאוד, אבל האם המצב הזה יכול לקרות?

הדרך היחידה בה המצב הזה יווצר יהיה אם הפונקציה תיקרא עם שני הורים ששניהם None, כלומר – עם פעמיים ההורה של השורש (הוא היחיד שההורה שלו הוא None).

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

*כמובן שבחיים האמתיים לא הייתי מסתמכת על זה ומוסיפה שכבת הגנה נוספת למקרה שמישהו שינה את הפונקציה העוטפת 🙂

הידד, נראה שיש לי אלגוריתם עובד.

אפשר לגשת לקודד.

קוד בגיט – https://github.com/mgershovitz/maya_solves/blob/master/first_ancestor.py