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

אם הצומת שיש למחוק קיים בתת העץ השמאלי של הצומת הקריטי, יש להחיל סיבוב L אחרת אם הצומת שיש למחוק קיים בתת העץ הימני של הצומת הקריטי , סיבוב R יוחל.

הבה ניקח בחשבון ש-A הוא הצומת הקריטי ו-B הוא צומת השורש של תת-העץ השמאלי שלו. אם יש למחוק את הצומת X, שנמצא בתת-עץ הימני של A, אז יכולים להיות שלושה מצבים שונים:

סיבוב R0 (לצומת B יש גורם איזון 0)

אם לצומת B יש מקדם איזון 0, ומקדם האיזון של צומת A מופר עם מחיקת הצומת X, אז העץ יאוזן מחדש על ידי סיבוב העץ באמצעות סיבוב R0.

הצומת הקריטי A מוזז לימינה והצומת B הופך לשורש העץ עם T1 כתת העץ השמאלי שלו. תתי העצים T2 ו-T3 הופכים לתת-עץ השמאלי והימני של הצומת A. התהליך המעורב בסיבוב R0 מוצג בתמונה הבאה.

דוגמא:

מחק את הצומת 30 מעץ ה-AVL המוצג בתמונה הבאה.

פִּתָרוֹן

במקרה זה, לצומת B יש גורם איזון 0, לכן העץ יסובב באמצעות סיבוב R0 כפי שמוצג בתמונה הבאה. הצומת B(10) הופך לשורש, בעוד הצומת A מוזז ימינה. הילד הימני של צומת B יהפוך כעת לילד השמאלי של צומת A.

מערכים ב-java

סיבוב R1 (לצומת B יש גורם איזון 1)

יש לבצע סיבוב R1 אם מקדם האיזון של צומת B הוא 1. בסיבוב R1, הצומת הקריטי A מועבר לימינו עם תתי-עצים T2 ו-T3 בתור הילד השמאלי והימני שלו, בהתאמה. יש למקם את T1 כתת-העץ השמאלי של הצומת B.

התהליך הכרוך בסיבוב R1 מוצג בתמונה הבאה.

דוגמא

מחק את צומת 55 מעץ ה-AVL המוצג בתמונה הבאה.

פתרון:

מחיקת 55 מעץ AVL מפריעה את גורם האיזון של הצומת 50 כלומר צומת A שהופך לצומת הקריטי. זהו המצב של סיבוב R1 שבו, הצומת A יוזז לימינה (מוצג בתמונה למטה). הימין של B הפך כעת לשמאל של A (כלומר 45).

התהליך הכרוך בפתרון מוצג בתמונה הבאה.

סיבוב R-1 (לצומת B יש מקדם איזון -1)

יש לבצע סיבוב R-1 אם לצומת B יש גורם איזון -1. מקרה זה מטופל באותו אופן כמו סיבוב LR. במקרה זה, הצומת C, שהוא הילד הימני של צומת B, הופך לצומת השורש של העץ כאשר B ו-A הם הילדים השמאלי והימני שלו, בהתאמה.

תתי העצים T1, T2 הופכים לתתי העצים השמאלי והימני של B ואילו, T3, T4 הופכים לתתי העצים השמאלי והימני של A.

חסום מודעות יוטיוב אנדרואיד

התהליך הכרוך בסיבוב R-1 מוצג בתמונה הבאה.

דוגמא

מחק את הצומת 60 מעץ ה-AVL המוצג בתמונה הבאה.

פִּתָרוֹן:

במקרה זה, לצומת B יש גורם איזון -1. מחיקת הצומת 60, מפריעה את גורם האיזון של הצומת 50 ולכן, יש לסובב אותו R-1. הצומת C כלומר 45 הופך לשורש העץ עם הצומת B(40) ו-A(50) בתור הילד השמאלי והימני שלו.