איזון עץ AVL: מדריך מקיף צעד אחר צעד למתכנתים | מבני נתונים

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

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

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

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

לדוגמה, אם צומת X בעל גורם איזון 2, ובן שמאלי Y בעל גורם איזון 1, נבצע גלגול שמאלה סביב Y.

לדוגמה, אם צומת X בעל גורם איזון -2, ובן ימני Y בעל גורם איזון -1, נבצע גלגול ימינה סביב Y.

זה מתרחש כאשר יש "ברך" שמאלה-ימינה.

זה מתרחש כאשר יש "ברך" ימינה-שמאלה.

אלגוריתם ההכנסה הבסיסי:

1. הכניסו את הצומת החדש כעלים (leaf node) בעץ, כמו בעץ חיפוש בינארי רגיל.

2. עברו במסלול מהצומת שהוכנס כלפי מעלה, לכיוון השורש.

3. עבור כל צומת במסלול, חשבו מחדש את גובהו ואת גורם האיזון שלו.

4. אם גורם האיזון של צומת כלשהו הופך ל-2 או -2, יש לבצע את פעולת הגלגול המתאימה (LL, RR, LR, או RL) כדי לאזן את העץ.

דוגמה מפורטת עם תרשימים (לצורך המחשה, נניח שהתרשימים מוצגים כאן):

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

אלגוריתם המחיקה הבסיסי:

1. מצאו את הצומת למחיקה. אם הצומת הוא עלה, פשוט הסירו אותו.

2. אם לצומת יש בן יחיד, החליפו את הצומת עם בנו היחיד.

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

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

דוגמה מפורטת עם תרשימים (לצורך המחשה, נניח שהתרשימים מוצגים כאן):

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

פונקציות עזר:

```pseudocode

Function GetHeight(node):

If node is null, return 0

Return node.height

Function GetBalanceFactor(node):

If node is null, return 0

Return GetHeight(node.left) - GetHeight(node.right)

Function UpdateHeight(node):

node.height = 1 + Max(GetHeight(node.left), GetHeight(node.right))

```

פסאודו-קוד עבור גלגולים:

```pseudocode

Function RotateRight(y):

x = y.left

T2 = x.right

x.right = y

y.left = T2

UpdateHeight(y)

UpdateHeight(x)

Return x

Function RotateLeft(x):

y = x.right

T2 = y.left

y.left = x

x.right = T2

UpdateHeight(x)

UpdateHeight(y)

Return y

```

פסאודו-קוד עבור הכנסה (הקטע המורחב שיכלול את האיזון):

```pseudocode

Function Insert(node, key):

// 1. Perform standard BST insertion

If node is null, create new node with key and height 1, return it

If key < node.key:

node.left = Insert(node.left, key)

Else if key > node.key:

node.right = Insert(node.right, key)

Else:

Return node // Duplicate keys not allowed

// 2. Update height of current node

UpdateHeight(node)

// 3. Get balance factor and balance if needed

balance = GetBalanceFactor(node)

// Left Left Case

If balance > 1 And key < node.left.key:

Return RotateRight(node)

// Right Right Case

If balance < -1 And key > node.right.key:

Return RotateLeft(node)

// Left Right Case

If balance > 1 And key > node.left.key:

node.left = RotateLeft(node.left)

Return RotateRight(node)

// Right Left Case

If balance < -1 And key < node.right.key:

node.right = RotateRight(node.right)

Return RotateLeft(node)

Return node

```

ניתוח סיבוכיות זמן ומקום:

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

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

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