עץ AVL

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


במדעי המחשב, עץ 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 מאוזנים. מספר כחול ליד צומת מציין גורמי איזון אפשריים (אלה שבסוגריים מתקיימים רק במקרה של מחיקה).

כדי לבצע הכנסה ומחיקה מעץ 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. לכן פעולות ההוצאה מבוצעות בזמן \  O(\log n).

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

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

מציאת הצומת[עריכת קוד מקור | עריכה]

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

הוצאת הצומת[עריכת קוד מקור | עריכה]

בהינתן צומת {\textstyle v} שרוצים להוציא מתוך העץ אך להשאיר את העץ כעץ חיפוש. אז מבצעים את הפעולות הבאות:

  • אם אין בנים ל{\textstyle v} אז מוחקים אותו מהעץ.
  • אם ל{\textstyle v} יש בן אחד מוחקים את {\textstyle v} והבן שלו יהיה יחליף את מקומו בתור הבן של האבא של {\textstyle v}.
  • אם ל{\textstyle v} יש שני בנים אז צריך למצוא את הצומת העוקב ל{\textstyle v} ולהחליף בניהם כאשר העוקב של {\textstyle v} הוא הצומת השמאלית ביותר שאליה אפשר להגיע מהבן הימני של {\textstyle v} ({\textstyle v_{rlll..}}). לאחר ההחלפה מוחקים את {\textstyle v} לפי אחת מהפעולות הקודמות.

איזון העץ לאחר ההוצאה[עריכת קוד מקור | עריכה]

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

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

סריקת העץ[עריכת קוד מקור | עריכה]

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

  1. בצע את הסריקה עבור הבן השמאלי של הצומת.
  2. בצע את הפעולה הנדרשת.
  3. בצע את הסריקה עבור הבן הימני של הצומת.

סריקה של העץ בסדר הזה תעבור על כל הצמתים בעץ בזמן ריצה \Theta(n) כאשר הסריקה של העץ תהיה לפי סדר מהקטן לגדול.

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