עבור לתוכן

איזון עץ AVL. איך?

Featured Replies

פורסם

שלום לכולם.

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

כאשר ה balance factor מגיע ל+2 וא -2 אני מבצע את אחד מארבעת הסיבובים (נכון לעכשיו ממושים רק סיבובים RR ו LL, אבל אני לא רואה בעיה לממש גם RL ו LR). הבעיה שלי זה עידכון ה balance factor אחרי שאיזנתי את העץ.

נניח הוספתי איבר מסויים, אני מתחיל לסרוק לאחור ומעדכן את האיזון של כל איברי והופ! מגיע לאיזון של +2, קורה לפונקציה המתאימה שמקבלת את האיבר שהאיזון שלו הוא +2 ואזנת את התת עץ הזה. הכל טוב ויפה אבל איך אני קובע איזון מחדש של כל צומת בעץ? שמעתי לדוגמא שבאיזון RR ו LL ה balance factor של כל שלושת הצמתים שמשתתפים באיזון מתאפס.

איך אני אמור לקבוע את balance factor של התת עץ שהשתתף באחד הסיבובים?

תודה רבה מראש!

פורסם

כשאני הייתי צריך לממש עץ AVL נעזרתי באתר הזה :

http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm

יש שם המון אפשרויות למשחק עם העץ ולהציג נתונים (בפרט הצגת ה balance factors)

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

פורסם
  • מחבר

תודה רבה לשניכם!

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים