מהו עץ AVL?

שיעור 2 מתוך 16 בקורס עץ AVL – סדרת מבני נתונים מס' 10 של Coddy.

כל צומת בעץ AVL עוקב אחר הגובה שלו: מספר הקשתות במסלול הארוך ביותר עד לעלה. גובהו של עלה הוא 1, ותת־עץ ריק נחשב כבעל גובה 0. לפי הגובה של שני ילדיו של צומת, אפשר לחשב את מקדם האיזון שלו: height(left) - height(right).

צומת מאוזן כאשר מקדם האיזון שלו הוא -1, 0 או 1. הכלל של עץ AVL פשוט: כל צומת חייב להישאר מאוזן, כל הזמן. בכל פעם שהוספה או מחיקה גורמות למקדם האיזון של צומת להגיע ל־2 או ל־-2, העץ מבצע סיבוב: סידור מחדש מקומי של כמה מצביעים, שמחזיר את האיזון בזמן קבוע בלי להפר את סדר עץ החיפוש.

יש ארבעה מקרי סיבוב (שמאל-שמאל, ימין-ימין, שמאל-ימין, ימין-שמאל), אבל את כולם אפשר לבנות משתי אבני יסוד: סיבוב יחיד שמאלה וסיבוב יחיד ימינה. בשיעורים הבאים תבנו את שניהם מאפס.

נסו בעצמכם

השיעור הזה לא כולל אתגר קוד.