נושא: חוות דעת מבנה נתונים

נשלח בתאריך: 14 May 2008 בשעה 20:22 | IP רשוּם

שלום לכולם

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

התוכנית תקבלת מהמשתמש שם עובד ומספר שעות עבודה ביום.
התוכנית תיצור קבוצות אינטרבליות בהתאם לחוצצים שיוכנסו לאחר או תוך כדי הכנסה של העובדים. כלומר אם קיבלנו חוצץ 20 יווצרו 2 קבוצות : ערכים הגדולים מהחוצץ וערכים הקטנים מחוצץ. בהמשך במידה וקיבלנו עוד חוצץ נומר 30 יווצרו 3 קבוצות, ערכים הקטנים מ20, ערכים בין 20 ל30 וקבוצת ערכים שגדולים מ30.
כמובן שיש את הפעולות הבסיסיות של הוצאת איבר, הכנסת איבר וכו'....
סיבוכיות של כל האלגוריתמים היא כחיפוש בינארי תיפוסי   log m

הפתרון עליו חשבתי הוא -
עץ חיפוש בינארי רגיל לאיכסון זמני עובד, כל עוד לא יוכנס חוצץ בעצם ישמש לאיכסון כל הקבוצה
עץ 2,3 על מנת להחזיק את הקבוצות, בעצם אצטרך לפרק את עץ החיפוש המלא ולהתאים את הצמתים למצביעים.

הבעיה שאני רואה ולכן אשמח לקבל חוות דעת :
ברגע של פירוק העץ אצטרך ככל הנראה לבצע רוטציה בין האיברים על מנת לשמור על חוקיות עץ הבינארי ובכך לחרוג מזמן הסיבוכיות
בעת הוספת חוצץ שלישי בעצם אקבל 2 תתי צמתים שלכל אחד מהם יש 3 מצביעים ובכך אני עלול לחרוג ממספר הקבוצות.

אשמח לקבל חוות דעת ועזרה בנושא