דף 1 מתוך 1

שאלה 4

נשלח: 13:32 10/06/2009
על ידי yaariy
למישהו יש רעיון איך מחזירים את ההפרש המינימלי?
האם צריך 2 עצים בשביל זה?

תודה

נשלח: 16:54 12/06/2009
על ידי itaigar
אני בהוספה בודק אם השורש הוא עלה ואם כן אני מגדיר את ההפרש המינימלי להיות ההפרש בין השורש לאיבר שאני מוסיף, אבל אני די תקוע בבדיקה תכלס מה הוא ההפרש המינימלי.. חשבתי פשוט לבדוק הפרשים בין איבר שאני מוסיף להורה שלו, אבל יכול להיות שההפרש בין האיבר להורה שלו יהיה גבוה מההפרש בין האיבר להורה של ההורה (או ההורה של ההורה של ההורה...)

יש למישהו רעיון?

נשלח: 17:41 12/06/2009
על ידי roie
רמז, מציאת העוקב והקודם של כל צומת לוקחת logn
עכשיו צריך לדעת מהו ההפרש המינימלי בין כל העוקבים/קודמים...

נשלח: 17:39 15/06/2009
על ידי orankap
אחלה, ואיך אתה מתמודד עם המחיקה? ברגע שמחקת את הפער הקטן אתה צריך לרוץ על כל העץ מחדש ולבצע n-1 השוואות, מה שלא עומד בדרישות השאלה...
אם מישהו עלה על פתרון נשמח לשמוע :D

נשלח: 18:55 15/06/2009
על ידי roie
אם תשמור במבנה נתונים (מבנה שצריך כמובן עדכון אחרי הוצאה/הכנסה) את כל ההפרשים בין כל העוקבים/קודמים תוכל למצוא את האיבר המינימלי בזמן הנדרש