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

[MasterDK]

שלום לכולם.

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

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

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

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

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

[binyamin1001]

למרות שלמדתי על עצי AVL, אני לא זוכר את החומר יותר מדי.

נסה לבדוק אם יהיה לך משהו שימושי באתר הזה:

http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html

התוצאה הראשונה לחיפוש "avl tree c++" בגוגל.

[Eviljelly]

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

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

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

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

[MasterDK]

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