AVL Tree הומצא על ידי GM Adelson - Velsky and EM Landis בשנת 1962. העץ נקרא AVL לכבוד ממציאיו.
AVL Tree יכול להיות מוגדר כעץ חיפוש בינארי מאוזן בגובה שבו כל צומת משויך לגורם איזון אשר מחושב על ידי הפחתת הגובה של תת העץ הימני שלו מזה של תת העץ השמאלי שלו.
אומרים שהעץ מאוזן אם גורם האיזון של כל צומת הוא בין -1 ל-1, אחרת, העץ יהיה לא מאוזן וצריך להיות מאוזן.
מקדם איזון (k) = גובה (שמאל (k)) - גובה (ימין (k))
אם גורם האיזון של כל צומת הוא 1, זה אומר שתת העץ השמאלי גבוה ברמה אחת מתת העץ הימני.
אם גורם האיזון של כל צומת הוא 0, זה אומר שתת העץ השמאלי ותת העץ הימני מכילים גובה שווה.
אם גורם האיזון של כל צומת הוא -1, זה אומר שתת-העץ השמאלי נמוך ברמה אחת מתת-העץ הימני.
עץ AVL ניתן באיור הבא. אנו יכולים לראות שגורם האיזון הקשור לכל צומת הוא בין -1 ל-+1. לכן, זוהי דוגמה לעץ AVL.
כיצד להמיר מחרוזת למספר שלם ב-java
מוּרכָּבוּת
| אַלגוֹרִיתְם | מקרה ממוצע | במקרה הגרוע ביותר |
|---|---|---|
| מֶרחָב | עַל) | עַל) |
| לחפש | o(לוג n) | o(לוג n) |
| לְהַכנִיס | o(לוג n) | o(לוג n) |
| לִמְחוֹק | o(לוג n) | o(לוג n) |
פעולות על עץ AVL
בשל העובדה שעץ AVL הוא גם עץ חיפוש בינארי ולכן, כל הפעולות מבוצעות באותו אופן כפי שהן מבוצעות בעץ חיפוש בינארי. חיפוש ומעבר אינם מובילים להפרת רכוש עץ AVL. עם זאת, הוספה ומחיקה הן הפעולות שעלולות להפר את המאפיין הזה, ולכן יש לבדוק אותן מחדש.
| SN | מבצע | תיאור |
|---|---|---|
| 1 | הַכנָסָה | ההכנסה בעץ AVL מתבצעת באותו אופן כפי שהיא מבוצעת בעץ חיפוש בינארי. עם זאת, היא עלולה להוביל להפרה בנכס עץ AVL ולכן העץ עשוי להזדקק לאיזון. ניתן לאזן את העץ על ידי הפעלת סיבובים. |
| 2 | מְחִיקָה | מחיקה יכולה להתבצע גם באותו אופן שבו היא מבוצעת בעץ חיפוש בינארי. המחיקה עלולה גם להפר את איזון העץ ולכן, נעשה שימוש בסוגים שונים של סיבובים לאיזון מחדש של העץ. |
למה AVL Tree?
עץ AVL שולט בגובה עץ החיפוש הבינארי בכך שהוא לא נותן לו להיות מוטה. הזמן שלוקח לכל הפעולות בעץ חיפוש בינארי בגובה h הוא O(h) . עם זאת, ניתן להרחיב אותו ל עַל) אם ה-BST הופך להיות מוטה (כלומר במקרה הגרוע ביותר). על ידי הגבלת גובה זה ללוג n, עץ AVL מטיל גבול עליון על כל פעולה שתהיה O(לוג n) כאשר n הוא מספר הצמתים.
AVL Rotations
אנו מבצעים סיבוב בעץ AVL רק במקרה ש-Balance Factor הוא אחר מ -1, 0 ו-1 . ישנם בעצם ארבעה סוגים של סיבובים שהם כדלקמן:
- סיבוב L L: הצומת המוכנס נמצא בתת העץ השמאלי של תת העץ השמאלי של A
- סיבוב R R: הצומת שהוכנס נמצא בתת העץ הימני של תת העץ הימני של A
- סיבוב L R: הצומת המוכנס נמצא בתת העץ הימני של תת העץ השמאלי של A
- סיבוב R L: הצומת המוכנס נמצא בתת העץ השמאלי של תת העץ הימני של A
כאשר צומת A הוא הצומת שגורם האיזון שלו שונה מ-1, 0, 1.
שני הסיבובים הראשונים LL ו-RR הם סיבובים בודדים ושני הסיבובים הבאים LR ו-RL הם סיבובים כפולים. כדי שעץ לא יהיה מאוזן, הגובה המינימלי חייב להיות לפחות 2, בואו נבין כל סיבוב
1. סיבוב RR
כאשר BST הופך לא מאוזן, בגלל שצומת מוכנס לתת-העץ הימני של תת-העץ הימני של A, אז אנו מבצעים סיבוב RR, סיבוב RR הוא סיבוב נגד כיוון השעון, המופעל על הקצה מתחת לצומת בעל גורם איזון -2
בדוגמה לעיל, לצומת A יש גורם איזון -2 מכיוון שצומת C מוכנס בתת-עץ הימני של תת-עץ ימני. אנו מבצעים את סיבוב ה-RR בקצה מתחת ל-A.
מחזור החיים של sdlc
2. סיבוב LL
כאשר BST הופך לא מאוזן, בגלל שצומת מוכנס לתוך תת-העץ השמאלי של תת-העץ השמאלי של C, אז אנו מבצעים סיבוב LL, סיבוב LL הוא סיבוב בכיוון השעון, אשר מוחל על הקצה מתחת לצומת בעל גורם איזון 2.
בדוגמה לעיל, לצומת C יש גורם איזון 2 מכיוון שצומת A מוכנס בתת העץ השמאלי של תת העץ השמאלי C. אנו מבצעים את סיבוב LL בקצה מתחת ל-A.
3. סיבוב LR
סיבובים כפולים הם קצת יותר קשים מסיבוב בודד שכבר הוסבר לעיל. סיבוב LR = סיבוב RR + סיבוב LL, כלומר, סיבוב RR ראשון מבוצע על תת-עץ ולאחר מכן סיבוב LL מבוצע על עץ מלא, בעץ מלא אנו מתכוונים לצומת הראשון מהנתיב של הצומת המוכנס שגורם האיזון שלו שונה מ-1 , 0 או 1.
בואו נבין כל שלב ושלב בצורה ברורה מאוד:
| מדינה | פעולה |
|---|---|
 | צומת B הוכנס לתוך תת-העץ הימני של A תת-העץ השמאלי של C, בגללו C הפך לצומת לא מאוזן בעל גורם איזון 2. מקרה זה הוא סיבוב L R כאשר: הצומת המוכנס נמצא בתת-העץ הימני של תת-העץ השמאלי של ג |
 | כאשר סיבוב LR = סיבוב RR + LL, לפיכך RR (נגד כיוון השעון) על תת-עץ המושרש ב-A מבוצע תחילה. על ידי ביצוע סיבוב RR, צומת א , הפך לתת-עץ השמאלי של ב . |
 | לאחר ביצוע סיבוב RR, צומת C עדיין לא מאוזן, כלומר, בעל גורם איזון 2, מכיוון שצומת A שהוכנס נמצא משמאל לשמאל של ג |
 | כעת אנו מבצעים סיבוב LL בכיוון השעון על עץ מלא, כלומר על צומת C. צומת ג הפך כעת לתת-העץ הימני של צומת B, A הוא תת-העץ השמאלי של B |
 | גורם האיזון של כל צומת הוא כעת -1, 0 או 1, כלומר BST מאוזן כעת. |
4. סיבוב RL
כפי שכבר דנו, שסיבובים כפולים הם קצת יותר קשים מסיבוב בודד שכבר הוסבר לעיל. סיבוב RL = סיבוב LL + סיבוב RR, כלומר, תחילה סיבוב LL מתבצע על תת-עץ ולאחר מכן סיבוב RR מבוצע על עץ מלא, בעץ מלא אנו מתכוונים לצומת הראשון מהנתיב של הצומת המוכנס שגורם האיזון שלו הוא אחר מ-1 , 0 או 1.
| מדינה | פעולה |
|---|---|
 | צומת ב הוכנס לתוך תת-העץ השמאלי של ג תת העץ הימני של א , שבגללו A הפך לצומת לא מאוזן בעל גורם איזון - 2. מקרה זה הוא סיבוב RL כאשר: הצומת שהוכנס נמצא בתת העץ השמאלי של תת העץ הימני של A |
 | כמו סיבוב RL = סיבוב LL + סיבוב RR, ומכאן, LL (בכיוון השעון) על תת-עץ המושרש ב- ג מבוצע תחילה. על ידי ביצוע סיבוב RR, צומת ג הפך להיות תת העץ הנכון של ב . |
 | לאחר ביצוע סיבוב LL, צומת א עדיין לא מאוזן, כלומר בעל גורם איזון -2, וזה בגלל תת-העץ הימני של צומת תת-העץ הימני A. |
 | כעת אנו מבצעים סיבוב RR (סיבוב נגד כיוון השעון) על עץ מלא, כלומר על צומת A. צומת ג הפך כעת לתת-העץ הימני של צומת B, וצומת A הפך להיות תת-העץ השמאלי של B. |
 | גורם האיזון של כל צומת הוא כעת -1, 0 או 1, כלומר, BST מאוזן כעת. |
ש: בנה עץ AVL בעל האלמנטים הבאים
H, I, J, B, A, E, C, F, D, G, K, L
הבדל בין אהבה ואהבה
1. הכנס H, I, J
בהכנסת האלמנטים לעיל, במיוחד במקרה של H, ה-BST הופך לא מאוזן מכיוון שגורם האיזון של H הוא -2. מכיוון שה-BST מוטה ימינה, נבצע RR Rotation בצומת H.
עץ האיזון שנוצר הוא:
2. הכנס B, A
בהכנסת האלמנטים לעיל, במיוחד במקרה של A, ה-BST הופך לא מאוזן מכיוון שגורם האיזון של H ו-I הוא 2, אנו רואים את הצומת הראשון מהצומת האחרון שהוכנס, כלומר H. מכיוון שה-BST מ-H מוטה שמאלה, נבצע LL Rotation בצומת H.
עץ האיזון שנוצר הוא:
3. הכנס E
בהכנסת E, BST הופך לא מאוזן מכיוון שגורם האיזון של I הוא 2, מכיוון שאם ניסע מ-E ל-I נמצא שהוא מוכנס בתת-העץ השמאלי של תת-העץ הימני של I, נבצע סיבוב LR בצומת I. LR = סיבוב RR + LL
3 א) תחילה אנו מבצעים סיבוב RR בצומת B
העץ שנוצר לאחר סיבוב RR הוא:
3ב) תחילה אנו מבצעים סיבוב LL על הצומת I
העץ המאוזן שנוצר לאחר סיבוב LL הוא:
4. הכנס C, F, D
נחש פיתון נגד אנקונדה
בהכנסת C, F, D, BST הופך לא מאוזן מכיוון שגורם האיזון של B ו-H הוא -2, מכיוון שאם ניסע מ-D ל-B נגלה שהוא מוכנס בתת-העץ הימני של תת-העץ השמאלי של B, נבצע סיבוב RL בצומת I. סיבוב RL = LL + RR.
4א) תחילה אנו מבצעים סיבוב LL בצומת E
העץ שנוצר לאחר סיבוב LL הוא:
4ב) לאחר מכן אנו מבצעים סיבוב RR בצומת B
העץ המאוזן שנוצר לאחר סיבוב RR הוא:
5. הכנס את G
בהכנסת G, BST הופך לא מאוזן מכיוון שגורם האיזון של H הוא 2, שכן אם ניסע מ-G ל-H, נגלה שהוא מוכנס בתת-העץ השמאלי של תת-העץ הימני של H, נבצע סיבוב LR בצומת I. סיבוב LR = RR + LL.
סנג'אי דאט ו
5 א) תחילה אנו מבצעים סיבוב RR בצומת C
העץ שנוצר לאחר סיבוב RR הוא:
5 ב) לאחר מכן אנו מבצעים סיבוב LL בצומת H
העץ המאוזן שנוצר לאחר סיבוב LL הוא:
6. הכנס K
בהכנסת K, BST הופך לא מאוזן מכיוון שגורם האיזון של I הוא -2. מכיוון שה-BST מוטה ימינה מ-I ל-K, לפיכך נבצע RR Rotation על הצומת I.
העץ המאוזן שנוצר לאחר סיבוב RR הוא:
7. הכנס את L
בהכנסת עץ L עדיין מאוזן מכיוון שגורם האיזון של כל צומת הוא כעת, -1, 0, +1. מכאן שהעץ הוא עץ AVL מאוזן
