עץ AVL

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

 

עקרון האיזון

AVL Example

עץ מאוזן אומר שגובה התת עץ השמאלי פחות גובה התת עץ הימיני הוא 0 או 1 או 1-.

גבוהו של עץ בינארי T שווה לאורך המסלול הארוך ביותר מהשורש לאיזשהו עלה ב T. אם העץ ריק הגובה מוגדר כ-(1-). ואם העץ מכיל רק צומת יחיד, גבוהו מוגדר כ-0. לדוגמה: בתמונה משמאל, גורם האיזון של A הוא 1, וזאת משום שגובה התת עץ השמאלי  (2) פחות גובה התת עץ הימיני (1) הוא 1. גם גורם האיזון של B הוא 1, וגם של C. גורם האיזון של F, לדוגמה, הוא 1- (גורם האיזון של כל עלה בעץ הוא כמובן 0).

נשים לב כי הדרישה שהעץ יהיה מאוזן (ז”א שהגבהים של שני תת העצים שלו אינם נבדלים ביותר מ-1) קיימת לכל צומת בעץ, ולא רק לשורש. לא אלאה אתכם בחישוב, אך ניתן להגיע בקלות (יחסית) לכך שהחסם העליון (במקרה הגרוע ביותר) של גבוה העץ הוא (lg(n [כאשר ה log נכתב כ lg מדובר על log בבסיס 2) לעץ בעל n צמתים. 

 

ביצוע פעולות

קודם כל, צריך להבחין בין שאילתות לבין פעולות שמשנות את מבנה העץ. כאשר אנו מדברים על שאילתה (כמו Search, Minimum, Maximum, Successor וכ’ו), הפעולה תתבצע בדיוק באותו אופן שבו היא מתבצעת על עץ חיפוש בינארי רגיל (לכן לא נרחיב על פעולות אלה בפוסט זה). בנוסף, מאחר שידוע לנו שגובהו של עץ AVL הוא מקסימום (lg(n מובטח לנו שפעולות אלה יתבצעו מהר, ולפעמים, אף, מהר יותר מאשר על עץ חיפוש בינארי.

אך כאשר אנו מדברים על פעולות שמשנות את מבנה העץ (כמו Insert ו  Delete) המצב מסובך יותר, מכיוון שלאחר שנבצע את פעולת הכנסת איבר לעץ או מחיקת איבר מהעץ, העץ עלול להפוך להיות לא מאוזן. לדוגמה: אם נמחק את G מהעץ שלמעלה בצד שמאל, או שנכניס איבר כבן של E.

 

רוטציה על עץ AVL

Left Rotation

רוטציה (rotation) היא פעולה מקומית בעץ חיפוש בינארי, השומרת על הסדר התוכי של המפתחות. ישנם 2 סוגים של רוטציה: רוטציה שמאלית ורוטציה ימנית. כאשר מפעלים לדוגמה רוטציה, שמאלית על צומת x, שבנו הימיני הוא y, התת עץ שהיה מושרש ב x משתנה כך:

  • y הופך להיות השורש של התת עץ.
  • x הופך להיות בנו השמאלי של y.
  • התת עץ השמאלי של y הופך להיות התת עץ הימני של x.

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

פסאודו קוד של הרוטציה השמאלית:

y <- right[x]
right[x] <- left[y]
if (left[y] != NIL)
    then p[left[y]] <- x
p[y] <- p[x]
if (p[x] = NIL)
    then root[T] <- y
    else if (x == left[p[x]])
        then left[p[x]] <- y
        else right[p[x]] <- y
left[y] <- x
p[x] <- y

הסבר קצר: בשורה 1 מציבים ב y את בנו הימיני של x (ההנחה היא שיש ל x בן ימני). בשורה 2 התת עץ השמאלי של y הופך להיות התת עץ הימני של x. אם תת עץ זה איננו ריק, אביו של שורש התת עץ יהיה כעת x (שורות 4-3). בשורה 5 מעדכנים את אביו של y (הוא יהיה אביו שהיה אביו של x). אם אביו של x היה NIL, אז y הוא כעת השורש החדש של העץ (שורות 6-7). אחרת, דואגים לכך שאביו של x יצביע כעת על y, בנו החדש (שורות 8-10). ולבסוף, בשורות 11-12, x הופך להיות בנו השמאלי של y. כמובן שהקוד עבור רוטציה ימנית דומה, וזמן הריצה של הרוטציות (ימנית / שמאלית) הוא (O(1.

 

הכנסת איבר לעץ AVL (פעולת Insert)

תהליך ההכנסה מתחלק לשלושה שלבים:

  1. מכניסים את k כעלה לעץ, בדומה להכנסה של צומת לעץ חיפוש בינארי רגיל. ההבדל הוא, שהפעם נדאג לשמור מצביע לאב הקדום הנמוך ביותר של k, שגורם האיזון שלו לפני ההכנסה היה 1 או 1-. נסמן צומת זו ב A. הצומת A היא הצומת הקריטי, מפני שהוא הצומת הראשון שגורם האיזון שלו עלול להפוך להיות 2 או 2- בעקבות הכנסת k לעץ.
  2. בודקים אם בעקבות הכנסת k לעץ, העץ הפך להיות לא מאוזן. הנקודה החשובה היא שמספיק לבדוק רק את צומת A: אם גורם האיזון של A היה 1 ו k הוכנס לתת עץ הימני של A, או שגורם האיזון של A היה 1- ו k הוכנס לתת עץ השמאלי של A, אז גורם האיזון של A ישתנה ל-0, ובמקרה זה העץ נשאר מאוזן. אם לעומת זאת, גורם האיזון של A היה 1 ו k הוכנס לתת עץ השמאלי של A, אז גורם האיזון של A הפך להיות 2 וצריך לאזן את העץ. באופן דומה, אם לנפי הכנסת k גורם האיזון של A היה 1- ו k הוכנס לתת עץ הימני של A, אז גורם האיזון של A הפך להיות 2- וצריך לאזן את העץ (איזון העץ יתבצע באמצעות רוטציה אחת או שתיים, כפי שנתאר בהמשך).
  3. כעת נותר רק לעדכן את גורמי האיזון של שאר הצמתים בעץ שהושפעו מהכנסת האיבר החדש. יש לעדכן את גורמי האיזון של האבות הקדמונים של k, שהחל מהצומת הראשון מתחת ל A שלא היה מעורבת ברוטציה ועד לאביו של k. (במקרה שלא הייתה צומת קריטי, מבצעים את העדכון החל מהשורש.) כדי לבצע את העדכון הולכים לשוב לאורך המסלול שבו הלכנו כשהכנסנו את k לעץ, ומשנים כל אחד מגורמי האיזון של הצמתים מ-0 ל-1 או ל-(1-) בהתאם לכיוון ההכנסה של k.

סיבוכיות זמן ריצה: מאחר שגובה העץ הוא ((O(lg(n, ברור שהשלב הראשון (הכנסת k לעץ) והשלב השלישי (עדכון גורמי האיזון של האבות הקדומנים של k) מתבצעים בזמן ((O(lg(n. בשלב השני לעומת זאת מתבצעות לכל היותר שתי רוטציות ולכן זמן הריצה שלו הוא (O(1. ולכן כל תהליך ההכנסה מתבצע בזמן ((O(lg(n.

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

 

נבחין בין ארבעה מקרים אפשריים:

  1. k מוכנס לתת עץ השמאלי של A ולתת עץ השמאלי של B.
  2. k מוכנס לתת עץ השמאלי של A ולתת עץ הימני של B.
  3. k מוכנס לתת עץ המני של A ולתת עץ הימני של B.
  4. k מוכנס לתת עץ הימני של A ולתת עץ השמאלי של B.

אך מכיוון שמקרים 3 ו-4 הם סימטריים למקרים 1 ו-2 נדון במקרים 1 ו-2 בלבד (המקרים שבהם גורם האיזון של A לפני הכנסת k היה 1 ובעקבות ההכנסה הוא השתנה ל-2).

 

מקרה 1:

Right Rotation On A

כדי לתאר את תהליך איזון העץ נשתמש בסימונים אלה:

  • B – בנו של A בכיוון ההכנסה של k.
  • T1 ו T2 – שני התת עצים של B.
  • T3 – התת עץ של A בכיוון הנגדי לכיוון ההכנסה של k.

נסמן את גבוהו של T1 (התת עץ השמאלי של B) ב h. ומכאן ברור שגם גבוהו של T2 (התת עץ הימני של B) הוא h, כי האיזון של B לפני הכנסת k הוא 0. גבוהו של T3 (התת עץ הימני של A) הוא גם כן h, כי האיזון של A לפני ההכנסה הוא 1. הפעולה הנגדרשת היא רוטציה ימנית על A.

כפי שניתן לראות באיור משמאל, גורמי האיזון של A ו B  לאחר ביצוע הרוטציה הם 0, ויש לדאוג לעדכן אותם בהתאם. בנוסף, נשים לב שלפני ההכנסה של k גובה התת עץ המושרש ב A (התת עץ שהשורש שלו הוא A) היה h+2. לאחר ההכנסה של k ואיזון העץ, גבוה העץ נשאר h+2 (לאחר האיזון, B הוא השורש החדש של התת עץ). כלומר, גורמי האיזון של כל הצמתים שהיו אבות קדומנים של A לא השתנו בעקבות הכנסת k לעץ (והצמתים שאינם אבות קדומנים של k כלל לא הושפעו מהכנסת k לעץ).

 

מקרה 2:

Two Rotations

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

  • C – בנו של B בכיוון ההכנסה של k.
  • T2 – התת עץ השמאלי של C.
  • T3 – התת עץ הימני של C.
  • T4 – התת עץ הימני של A.
  • אם נסמן את גבוהם של T2 ושל T3 ב h, אז גבוהו של T1 הוא h+1 (משום שגורם האיזון של הצומת B לפני ההכנסה של k היא 0), וגבהו של T4 גם h+1 (משום שגורם האיזון של הצומת A לפני ההכנסה של K הוא 1).

במקרה זה, יש 3 תת מקרים אפשריים:

  1. k נכנס ל T2 (כמו באיור משמאל).
  2. k נכנס ל T3.
  3. הצומת B הוא עלה, ו k נכנס לעץ כבנו הימני של B.
Rotation left and right

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

בנוסף, נשים לב שלפני ההכנסה של K, גובה התת עץ המושרש ב A היה h+3, ולאחר ההכנסה והאיזון גובה התת עץ נשאר h+3 (לאחר האיזון C הוא השורש החדש של התת עץ). כלומר, גם הפעם גורמי האיזון של כל הצמתים שהיו אבות קדמונים של A לא השתנו בעקבות הכנסת k לעץ.

Delete AVL Example

 

מחיקת איבר מעץ AVL (פעולת Delete)

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

ז”א שישנם 3 מקרים אפשריים: שינוי בגורם האיזון מ-0 ל-(1+/-), שינוי מ-(1+/-) ל-0, או שינוי מ-(1+/-) ל-(2+/-). נדגים את שלושת המקרים באמצעות מחיקת איבר מהעץ שמשמאל.

 

Case A

מקרה א

גורם האיזון של האב היה 0 והוא משתנה ל-(1+/-). במקרה זה גובהו של התת עץ המושרש באב לא משתנה, ולכן צריך רק לעדכן את גורם האיזון של האב. זה המקרה הפשוט ביותר, מאחר שלשינוי בגורם האיזון של האב אין השפעה על צמתים אחרים בעץ.

גורם האיזון של D משתנה מ-0 ל-(1-), ובכך האלגוריתם מסתיים.

 

מקרה ב

Case B

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

אביו של הצומת שנמחק הוא P, וגורם האיזון של P משתנה מ-1 ל-0. בעקבות זאת יש לשנות גם את גורמי האיזון של הבאות הקדמונים של P, שהם כעת R ו-M. גורם האיזון של הסבא, R, משתנה מ-1 ל-0, וגורם האיזון של M, אביו של הסבא, משתנה מ-1 ל-0.

 

מקרה ג

Case C

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

אביו של הצומת שנמחק הוא R, וגורם האיזון שלו משתנה מ-1 ל-2. לאחר ביצוע רוטציה על R, גובהו של התת עץ ש R היה השורש שלו קטן ב-1, ויש לשנות את גורם האיזון של F מ-(1-) ל-0.

 

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

 

לסיכום

בפוסט זה למדנו על נגזרת של עצי חיפוש בינארים הנקראת עצי חיפוש בינארים מאוזנים. הבנו כיצד מבצעים פעולת הכנסה (4 אפשרויות שונות) ומחיקה (3 אפשרויות שונות) לעצים כאלו תוך שמירה על האיזון שלהם (איזון גבוה העץ). על מנת לשמור על איזון העץ למדנו כיצד לבצע רוטציה על העץ (לשנות את סדר המפתחות התוכי של העץ). 

עצי חיפוש בינארי מאוזנים מאפשרים לנו לבצע את פעולות המילון (הכנסה ומחיקה) בזמן (O(lgn (מה שאינו מובטח אם משתמשים בעצי חיפוש בינארי רגילים). לכן השימוש בעצי AVL כ”קופסה שחורה” יכול להועיל כאשר אנו מתכננים מבני נתונים שתומכים או בפעולות המילון או בפעולות פשוטות ושימושיות אחרות שנגזרות מהן.