שאלה חשובה לגבי ה insert...

מנהל: TA_Isana

שלח תגובה
odedlei
הודעות: 32
הצטרף: 14:56 29/10/2009

שאלה חשובה לגבי ה insert...

שליחה על ידי odedlei » 18:49 28/04/2010

שלום.
בעקבות הדפסות ששמתי בבדיקות שלי בכניסה לכל שיטה, ראיתי שבכניסה ל insert מ AVLSearchNode :
1. השיטה מפעילה את ה insert של AVLSearchNode כי אני מפעיל אותה על השורש.
2. השיטה מפעילה את ה Insert של BinarySearchNode כי יש קריאה לשיטת ה super.
3. כאן טמונה הבעיה- כי insert היא פעולה רקורסיבית בBinarySearchNode כאשר התנאי עצירה הוא שמאל/ימין = null (בהתאם להשוואת המפתח עם הtoAdd).
כלומר- אם ה toAdd קטן מהמפתח למשל יש להכניסו לתתעץ השמאלי- אבל אם השמאלי אינו null- אז יש לבצע insert עבור התתעץ השמאלי עם אותה toAdd. כאן נקראת הinsert של הרמה החיצונית!!

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

Shahar
הודעות: 160
הצטרף: 16:49 29/10/2009

Re: שאלה חשובה לגבי ה insert...

שליחה על ידי Shahar » 19:01 28/04/2010

אבל כשאתה מפעיל את זה על התת עץ השמאלי לדוגמא, אתה אמור להשתמש ב:

קוד: בחירת הכל

this.getLeft().insert(blah)
ושים לב שgetLeft נדרס בכל מחלקה מחדש, כך שהוא יעשה קאסטינג לסוג המחלקה הדרוש.
ואז אין שום בעיה :)

בר כהן
הודעות: 146
הצטרף: 18:24 22/10/2009

Re: שאלה חשובה לגבי ה insert...

שליחה על ידי בר כהן » 19:15 28/04/2010

odedlei כתב: אני מאמין שזה משפיע על הזמן ריצה.
ניסיתי קאסטינג ואפילו הורדת פרטיות של שדות מסוימים. בבקשה עזרה או קצה חוט בנושא.
תודה.
למה שזה ישפיע לך על הזמן ריצה?
אם בהכנסה רגילה של עץ חיפוש בינארי הפונק' הייתה נקראית h פעמים, אז גם עכשיו היא תיקרא h פעמים, פשוט יהיו אותו מספר קריאות ל-insert של ה-AVLSearchNode, כלומר
מקסימום של 2h קריאות, וזה לא משפיע לך על הזמן ריצה.

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

שלח תגובה

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