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

[odedlei]

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

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

[Shahar]

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

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

this.getLeft().insert(blah)

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

[בר כהן]

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

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

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