איך לאזן עץ AVL (מבנה נתונים)

Steps

1. 1

   Step 1

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

   Step 2

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

   Step 3

   
   כעת נכניס איבר נוסף (13) וניצור עץ שאינו מאוזן. העץ הזה אינו מאוזן מכיוון שהפרש מספר הבנים של 14 מימין ומשמאל אינו שווה ל1. ההפרש בין תת העץ של 14 משמאל (2) לתת העץ הימני שלו (0) הינו 2 - כלומר , נוצר חוסר איזון. זוהי נקודת ההפרה. במקרה של חוסר איזון נעשה פעולה אשר תאזן את העץ תקרא גלגול או רוטציה.
4. 4

   Step 4

   
   אז בכדי לבצע גלגול עלינו למצוא את נקודת ההפרה ולסמן את הנתיב מנקודת ההפרה כלפי מטה ב X,Y,Z , לדוגמא:
5. 5

   Step 5

   קיימים 4 סוגים של גלגולים: 1. אם נתיב ההפרה (מלמעלה למטה) הינו שמאלה-שמאלה אנו נבצע גלגול לX לימין. 2. אם נתיב ההפרה (מלמעלה למטה) הינו ימינה-ימינה, נבצע גלגול לX לשמאל. 3. אם נתיב ההפרה (מלמעלה למטה) הינו ימינה-שמאלה, נבצע גלגול לY לימין ולאחר מכן נבצע גלגול לX לשמאל. 4. אם נתיב ההפרה (מלמעלה למטה) הינו שמאלה-ימינה, נבצע גלגול לY לשמאל ולאחר מכן נבצע גלגול לX לימין. לצורך פשטות נקרא כעת לימין R ולשמאל L. בקצרה:
6. 6

   Step 6

   RR -> L(X) LL -> R(X) LR -> L(Y)R(X) RL -> R(Y)L(X)
7. 7

   Step 7

   
   בואו נבצע איזון לדוגמא הקודמת. אנו רואים שנקודת ההפרה נמצאת ב10 ונתיב ההפרה הוא שמאל ימין, כלומר LR. לכן תחילה נבצע גלגול לY לשמאל - כלומר 12 ירד שמאלה ובמקומו יעלה ה13.
8. 8

   Step 8

   
   ונקבל:
9. 9

   Step 9

   
   כעת על פי הפעולות שעלינו לעשות, נשאר לבצע גלגול X לימין. ה14 ירד ימינה ובמקומו יעלה ה13 ובנו הימני יישאר 12.
10. 10

    Step 10

    
    ולבסוף נקבל עץ מאוזן. במידה והמקרה היה הפוך ונתיב ההפרה היה RL היינו מבצעים גלגול Y לימין וגלגול X לשמאל.
11. 11

    Step 11

    
    נעשה כעת דוגמא פשוטה יותר שבו נתיב ההפרה הוא RR. תחילה נסמן את הנתיב בX,Y,Z (מלמעלה למטה)
12. 12

    Step 12

    
    מכיוון שנתיב ההפרה הוא RR נבצע גלגול של X לשמאל. 13 ירד לשמאל, 14 יחליף את מקומו ו15 יישאר הבן מימין.
13. 13

    Step 13

    
    ונקבל: כמובן שבמקרה ההפוך של LL נעשה גלגול של X לימין.