עץ AVL

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Gnome-colors-emblem-development-2.svg הערך נמצא בשלבי עבודה: כדי למנוע התנגשויות עריכה ועבודה כפולה אתם מתבקשים שלא לערוך ערך זה בטרם תוסר הודעה זו, אלא אם כן תיאמתם זאת עם מניחי התבנית.
אם הדף לא נערך במשך שבוע ניתן להסיר את התבנית ולערוך אותו, אך רצוי לתת קודם תזכורת בדף שיחת הכותבים.
דוגמה לעץ AVL

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

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

דרך פעולת העץ[עריכת קוד מקור | עריכה]

כל צומת בעץ שומר, פרט למידע הסטנדרטי של עץ חיפוש, גם מאפיין נוסף הנקרא "גורם האיזון" (Balance factor) . מאפיין זה הוא ההפרש בין גובהו של תת-העץ השמאלי של הצומת ותת העץ הימני של הצומת. מקפידים כי גורם האיזון יהיה תמיד בכל צומת 1, 0 או 1-. תכונה זו מבטיחה כי העץ יהיה מאוזן - כלומר עומקו לכל היותר לוגריתמי (ליתר דיוק \ 1.4404  \cdot \log n).

פעולת חיפוש[עריכת קוד מקור | עריכה]

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

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

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

פעולת החיפוש לא משנה את המבנה של העץ ולכן העץ נשמר כעץ חיפוש בינארי ומאוזן.

גלגולים[עריכת קוד מקור | עריכה]

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

ישנם ארבעה סוגים של גלגולים: RR, LL, RL ו-LR, כאשר על ידי ארבעתם ניתן לטפל בכל צומת שגורם האיזון שלו הופר ושווה ל2 או 2-, אבל הוא תקין בכל תת העץ שלו. הבחירה באיזה גלגול להשתמש נעשית על פי הכללים הבאים:

  • LL - גורם האיזון בצומת הופר ל2 וגורם האיזון בבן השמאלי הוא 0 או 1.
  • LR - גורם האיזון בצומת הופר ל2 וגורם האיזון בבן השמאלי הוא 1-.
  • RR - גורם האיזון בצומת הופר ל2- וגורם האיזון בבן הימני הוא 0 או 1-.
  • RL - גורם האיזון בצומת הופר ל2- וגורם האיזון בבן הימני הוא 1.

פעולת הכנסה[עריכת קוד מקור | עריכה]

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

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

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

פעולת מחיקה[עריכת קוד מקור | עריכה]

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

כל גלגול משנה רק מספר קבוע של צמתים, ולכן מתבצע בזמן קבוע. לכן פעולות ההוצאה וההכנסה מבוצעות בזמן \ \log n.

קישורים חיצוניים[עריכת קוד מקור | עריכה]