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

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

עוד שאלה בסגנון דומה שאין לי ממש מושג כיצד מבצעים אותה היא זו :

ציטוט:

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

תודה

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

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

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

את ההסבר שלך לשאלה השנייה לא הבנתי....
מה זאת אומרת "והיא: לכל צומת במסלול, מסלול ארוך ביותר היוצא מצומת זו לימין ומסלול ארוך ביותר היוצא מצומת זו משמאל" ??

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

1. אתה יכול להוסיף בO(N) מצביע לאב ולכן זה לא משנה. בכל מקרה אתה לא ציינת בהודעה שמדובר בעץ ממויין. לכן נאלצתי להביא פיתרון כללי יותר שיעבוד על כל עץ בינארי.

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