נושא: שאלות קשות

נשלח בתאריך: 04 July 2005 בשעה 20:31 | IP רשוּם

שלום, 2 שאלות ממבחן שרציתי לדעת כיצד פותרים אותן..

1) יש למצוא מבנה נתונים S שתומך בפעולות הבאות:

הכנסה, חיפוש ומחיקה ב-O(logN, וגם בפעולה שנקראת count(s,k1,k2,

שצריכה לחשב ולספור את כל האיברים במבנה S שגדולים מ-k1, וקטנים מ-k2(אפשרי גם שיוויון), ברור שלחלק הראשון מתאים עץ AVL, אבל מה צריך להוסיף כדי לאפשר את count?

2) א)נתון עץ חיפוש בינארי בו בכל צומת z חוץ מהמפתח שלה נמצאים עוד 2 מפתחות, אחד מכיל את המינימום של תת העץ של z, ואחד את המקסימום, צריך לתאר כיצד ניתן לעדכן את הערכים הללו בפעולות של הכנסה ומחיקה, כאשר אסור שהעדכון ישנה את סיבוכיות הפעולות(כלומר O(logN).

ב) כיצד ישתנה העדכון אם במקום עץ חיפוש בינארי ניקח עץ AVL, האם הסיבוכיות תשתנה?

אשמח מאוד אם מנהל הפורום או מישהו אחר יוכל לעזור לי, כי אני לא יודע איך לגשת לשאלות הללו, בתודה,

רון

נשלח בתאריך: 05 July 2005 בשעה 13:24 | IP רשוּם

1) מה שאתה צריך כאן זה עץ דרגות שיורכב על ה-AVL - עבור כל צומת תשמור מידע על הבנים שלו. אתה מוזמן לקרוא את המסמך על מבני נתונים שבאתר בו מוסבר בפירוט כיצד לעשות זא.

נשלח בתאריך: 05 July 2005 בשעה 13:26 | IP רשוּם

2)

א) בעת הכנסה, בעץ הירידה בעץ, אם הערך שאנחנו מכניסים הולך לשנות את המקסימום או המינימום, נעדכן זאת בהתאם ב-o(1) עבור כל צומת במהלך הירידה.