שאלה 4

yaariy · שליחה על ידי **yaariy** » 13:32 10/06/2009

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

תודה

itaigar · שליחה על ידי **itaigar** » 16:54 12/06/2009

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

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

roie · שליחה על ידי **roie** » 17:41 12/06/2009

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

orankap · שליחה על ידי **orankap** » 17:39 15/06/2009

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

roie · שליחה על ידי **roie** » 18:55 15/06/2009

אם תשמור במבנה נתונים (מבנה שצריך כמובן עדכון אחרי הוצאה/הכנסה) את כל ההפרשים בין כל העוקבים/קודמים תוכל למצוא את האיבר המינימלי בזמן הנדרש