שאלה 4

מנהל: TA_Isana

שלח תגובה
yaariy
הודעות: 14
הצטרף: 14:40 15/12/2008

שאלה 4

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

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

תודה

itaigar
הודעות: 20
הצטרף: 03:55 16/12/2008

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

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

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

roie
הודעות: 32
הצטרף: 21:35 15/12/2008

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

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

orankap
הודעות: 67
הצטרף: 14:23 02/12/2008

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

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

roie
הודעות: 32
הצטרף: 21:35 15/12/2008

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

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

שלח תגובה

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