נושא: מבני נתונים

נשלח בתאריך: 01 December 2009 בשעה 00:48 | IP רשוּם

שלום,

אני נדרש לממש מבנה נתונים של מס' שלמים שיתמוך בפעולות הבאות:

א.                               Insert(x) – הכנס איבר x לתוך המבנה נתונים

ב.                               Delete(x)- מחיקת איבר x (אם הוא קיים) ממבנה הנתונים

ג.                                 DeleteIndex(i) – מחיקת האיבר ה i על פי סדר ההכנסה ממבנה הנתונים – אם האיבר נמחק אין צורך לעדכן את שאר האיברים במבנה.

ד.                               GetIndex(x)- מחזיר את המיקום של x אם הוא במבנה על פי סדר ההכנסה ,  לדוגמא אם בצעתי insert(3),insert(2),insert(7) ואחרי זה עשיתי GetrIndex(7) אני אקבל בפלט 3 , כי הוא הוכנס שלישי לפי סדר ההכנסה.

כל הפעולות חייבות להתבצע ב O(log(n)) זמן ריצה ו O(n) זכרון.

כבר ידוע לי עפ"י (נותן התרגיל גם) שיש להשתמש בעץ AVL, אבל עוד משהו, יותר מסתם עץ AVL.

מובן לי שצריך AVL כדי לחפש ב O(log(n)) מספרים, שהרי כך קל למצוא אותם על יחס של גדול/קטן. אבל צריך עוד משהו בנוסף ל-AVL שהרי צריך להחזיק גם את סדר ההכנסה של המספרים וכך גם למצוא דרך סדר ההכנסה את האיבר המבוקש.

תודה