רוטציות לאחר הכנסה שכוללות את השורש

מנהל: TA_Isana

שלח תגובה
סטרז'
הודעות: 28
הצטרף: 23:25 26/10/2009

רוטציות לאחר הכנסה שכוללות את השורש

שליחה על ידי סטרז' » 00:23 26/04/2010

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

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

Re: רוטציות לאחר הכנסה שכוללות את השורש

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

אתה צריך לעדכן את המשתנה root מתוך המחלקה שלו AVLSearchTree, וזה עדכון שאתה צריך לבצע אחרי שסיימת את כל הרוטציות וכו'.
יש בדיקה מאוד פשוט לעניין, פשוט תזכור שתמיד בכל זמן נתון יש רק צומת אחת שאבא שלה הוא null, ואם שינית את השורש אז הוא פשוט יהיה מתחתיו איפשהו.
את הרוטציות אתה מבצע כרגיל, זו אותה רוטינה בלי קשר לאיזה צמתים סובבת.

סטרז'
הודעות: 28
הצטרף: 23:25 26/10/2009

Re: רוטציות לאחר הכנסה שכוללות את השורש

שליחה על ידי סטרז' » 00:52 26/04/2010

הבנתי , תודה רבה!

ilyal
הודעות: 63
הצטרף: 10:27 30/03/2009

Re: רוטציות לאחר הכנסה שכוללות את השורש

שליחה על ידי ilyal » 01:26 26/04/2010

יש הגבלה על מאיפה לבצע את הרוטציות?
כלמר אני למשל מבצע את הרוטציות ב AVLSearchTree או שזה אסור?

תודה.

שלח תגובה

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