overlapSearch

מנהל: TA_Isana

שלח תגובה
אורי
הודעות: 3
הצטרף: 14:46 26/04/2010

overlapSearch

שליחה על ידי אורי » 23:52 26/04/2010

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

ronenhe
הודעות: 182
הצטרף: 10:27 28/10/2009

Re: overlapSearch

שליחה על ידי ronenhe » 00:21 27/04/2010

הממ.. אני חושב שיש שני אפשרויות
אם הוא חופף בשני תתי העצים אז או שהוא חופף עם השורש
ואם לא זה לא כל כך משנה לך איפה הוא..
או ימין או שמאל..
תבחר אחד..
בהצלחה!

גל פלד
הודעות: 31
הצטרף: 20:15 27/10/2009

Re: overlapSearch

שליחה על ידי גל פלד » 02:52 27/04/2010

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

כמובן שמדובר בפונקציה רקורסיבית שתנאי העצירה שלה הוא
א)נמצאה איבר
ב)אין יותר איברים לבדיקה (הגנו לעלה והוא לא חופף)כלומר אין חפיפה בכל העץ
ג)מהצומת שאנחנו נמצאים בה ה max לשני הכיוונים קטן מה start של החיפוס (כלומר גם כאן אין חפיפה בכל העץ)

מקווה שעזרתי לכולם עם ה overlapSearch

זמן ריצה של פונקציה כזאת הוא כגובה העץ כי כל פעם מקבלים החלטה ימין אוו שמאל לא חוזרים אחורה וברגע שהגנו לעלה עוצרים כלומר עם מדובר ב עץ avl אזי זמן הריצה הוא log n

ronenhe
הודעות: 182
הצטרף: 10:27 28/10/2009

Re: overlapSearch

שליחה על ידי ronenhe » 08:42 27/04/2010

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

שלח תגובה

חזור אל “- מבני נתונים 2010”