שאלה 4

מנהל: TA_Isana

שאלה 4

הודעהעל ידי yaariy » 12:32 10/06/2009

למישהו יש רעיון איך מחזירים את ההפרש המינימלי?
האם צריך 2 עצים בשביל זה?

תודה
yaariy
 
הודעות: 14
הצטרף: 14:40 15/12/2008

הודעהעל ידי itaigar » 15:54 12/06/2009

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

יש למישהו רעיון?
itaigar
 
הודעות: 20
הצטרף: 03:55 16/12/2008

הודעהעל ידי roie » 16:41 12/06/2009

רמז, מציאת העוקב והקודם של כל צומת לוקחת logn
עכשיו צריך לדעת מהו ההפרש המינימלי בין כל העוקבים/קודמים...
roie
 
הודעות: 32
הצטרף: 21:35 15/12/2008

הודעהעל ידי orankap » 16:39 15/06/2009

אחלה, ואיך אתה מתמודד עם המחיקה? ברגע שמחקת את הפער הקטן אתה צריך לרוץ על כל העץ מחדש ולבצע n-1 השוואות, מה שלא עומד בדרישות השאלה...
אם מישהו עלה על פתרון נשמח לשמוע :D
orankap
 
הודעות: 67
הצטרף: 14:23 02/12/2008

הודעהעל ידי roie » 17:55 15/06/2009

אם תשמור במבנה נתונים (מבנה שצריך כמובן עדכון אחרי הוצאה/הכנסה) את כל ההפרשים בין כל העוקבים/קודמים תוכל למצוא את האיבר המינימלי בזמן הנדרש
roie
 
הודעות: 32
הצטרף: 21:35 15/12/2008


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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ו 2 אורחים