מבוא

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

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

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