בעצי המחשב, עץ AVL הוא עץ חיפוש בינארי מאוזן. עץ חיפוש בינארי הוא מבנה שבו לכל צומת יש עד שני בנים, והערכים בצד השמאלי קטנים מהערך בצומת והערכים בצד הימני גדולים ממנו. עץ AVL שומר שבכל צומת הפרש הגובה בין תת-העץ השמאלי לימני הוא לכל היותר 1. תכונה זו מאפשרת חיפוש, הכנסת והסרת נתונים בזמן O(log n) במקרה הגרוע, כאשר n הוא מספר הצמתים.
עץ זה נקרא על שמם של גאורגי אדלסון-ולסקי ויבגני לנדיס. הם הציגו אותו ב-1962, והוא היה עץ החיפוש הראשון שהבטיח איזון בעלות של O(log n).
בכל צומת שומרים בנוסף למפתח גם "גורם האיזון" (Balance factor). זהו ההפרש בין גובה תת-העץ השמאלי לגובה תת-העץ הימני: BF(X) = Height(LeftSubtree(X)) - Height(RightSubtree(X)). בעץ AVL ערך זה תמיד 1, 0 או -1. זה שומר שהעץ מאוזן בקירוב, ולכן עומקו מוגבל (ניתן להראות גבול של כ-1.44·log2(n+2) - 0.328).
חיפוש בעץ AVL זהה לחיפוש בעץ חיפוש בינארי. מתחילים מהשורש ומשווים את המפתח:
- אם המפתח מתאים, מצאנו את הנתון.
- אם המפתח בצומת גדול מהמפתח המבוקש, ממשיכים לבן השמאלי.
- אם המפתח בצומת קטן מהמפתח המבוקש, ממשיכים לבן הימני.
- אם אין עוד צמתים המתאימים, הנתון לא נמצא.
כיוון שהעץ מאוזן בקירוב, החיפוש לוקח O(log n).
הוספה או הסרה יכולות להוביל לכך שגורם האיזון בצומת יגיע ל-2 או ל-2-. כדי לתקן זאת מבצעים "גלגולים" (rotations). גלגול משנה מקומית את מבנה העץ מבלי לשבור את סדר המפתחות. יש ארבעה סוגי גלגולים: RR, LL, RL ו-LR. כל גלגול ניתן למימוש בעזרת שתי פעולות בסיסיות (סיבוב ימינה/שמאלה). כל גלגול נעשה בזמן קבוע O(1).
הכנסת צומת נעשית כמו בעץ חיפוש בינארי. לאחר ההכנסה בודקים את המסלול מהצומת החדש לשורש. אם נמצא צומת שערך גורם האיזון שלו מופר, מבצעים את הגלגול המתאים. גלגול כזה משחזר את הגובה של תת-העץ למה שהיה לפני ההוספה, ולכן העץ נשאר מאוזן. זמן ההכנסה הכולל הוא O(log n), כי יש עד O(log n) צמתים לעדכן ולא יותר מגלגול אחד דרוש.
המחיקה כוללת שלושה חלקים: מציאת הצומת, הוצאתו תוך שמירה על סדר העץ, ואיזון העץ לאחר ההוצאה.
המציאה נעשית כמו בחיפוש: מתחילים מהשורש וממשיכים לפי השוואות המפתח עד שמגיעים לצומת המתאים.
(פירוט ההוצאת הצומת אינו מפורט במקור זה.)
הוצאת צומת עלולה לגרום לאי־איזון. עוברים מעלה לאורך המסלול שהשתנה ומבצעים גלגולים בצמתים בעלי הפרת איזון. גם פעולה זו מתבצעת בזמן O(log n).
כדי לעבור על כל הנתונים משתמשים בסריקות רקורסיביות. הסדר התוכי (in-order) עובר על הצמתים מהקטן לגדול: סורקים את הבן השמאלי, מבצעים פעולה בצומת, ואז סורקים את הבן הימני. סריקה כזו עוברת על כל הצמתים בזמן Θ(n). קיימות גם סריקות נוספות: תחילית (pre-order) וסופית (post-order), גם הן בזמן Θ(n).
עץ AVL הוא סוג של עץ במחשבים. זהו "עץ חיפוש בינארי". זה אומר שלכל צומת יש עד שני בנים. בצד שמאל ערכים קטנים יותר. בצד ימין ערכים גדולים יותר.
עץ AVL שומר על איזון. לכל צומת יש מספר שנקרא "גורם האיזון". זהו ההפרש בין הגובה של הצד השמאלי לזה של הצד הימני. הגורם יכול להיות 1, 0 או -1 בלבד. כך העץ נשאר כמעט מאוזן.
בעץ כזה חיפוש, הוספה והסרה הם מהירים. זה כי העץ לא עושה זוויות עמוקות מדי.
כאשר העץ מתבלגן, עושים פעולה שנקראת "גלגול". גלגול משנה מקומית את הקשרים בין הצמתים. יש ארבעה סוגי גלגולים. הם מתקנים את האיזון בלי לשבור את הסדר.
חיפוש מתחיל מהשורש. משווים ומחליטים ללכת שמאלה או ימינה עד שמוצאים את מה שמחפשים. הכנסת צומת מתבצעת כמו בחיפוש. אחרי הכנסת צומת בודקים את האיזון ומתקנים בגלגולים אם צריך. גם מחיקה דורשת תיקון איזון בגלגולים.
כדי לקבל את כל הערכים בסדר, עוברים בעץ בשיטת "סדר תוכי". קודם שמאלה, אחר כך הצומת, ואחר כך ימינה. כך מקבלים את הערכים מהקטן לגדול.
תגובות גולשים