הסבר על הכנסת עץ AVL, סיבוב ואיזון

מהו עץ AVL?

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

BST הוא מבנה נתונים המורכב מצמתים. יש לה את הערבויות הבאות:

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

לעצי AVL יש אחריות נוספת:

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

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

סיבוב נכון

סיבוב שמאלי

תהליך הכנסת AVL

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

• אם יש חוסר איזון אצל הילד השמאלי של תת העץ הימני, אז אתה מבצע סיבוב שמאלה ימינה.
• אם קיים חוסר איזון בילד שמאלי בעץ השמאלי, אז אתה מבצע סיבוב ימינה.
• אם יש חוסר איזון בילד הימני של תת העץ הימני, אז אתה מבצע סיבוב שמאלי.
• אם יש חוסר איזון בילד הימני של תת העץ השמאלי, אז אתה מבצע סיבוב ימין-שמאל.

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

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

סיבובי עץ AVL

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

פעולות סיבוב משמשות לאיזון עץ. ישנם ארבעה סיבובים והם מסווגים לשני סוגים:

סיבוב שמאלי יחיד (סיבוב LL)

בסיבוב LL כל צומת מעביר מיקום אחד שמאלה מהמיקום הנוכחי.

סיבוב ימינה יחידה (סיבוב RR)

בסיבוב RR כל צומת מעביר מיקום אחד ימינה מהמיקום הנוכחי.

סיבוב ימינה שמאלה (סיבוב LR)

סיבוב LR הוא שילוב של סיבוב שמאלי יחיד ואחריו סיבוב ימינה יחיד. בסיבוב LR, ראשית כל צומת מעביר מיקום אחד שמאלה ואז מיקום אחד ימינה מהמיקום הנוכחי.

סיבוב ימינה שמאלה (סיבוב RL)

סיבוב ה- RL הוא שילוב של סיבוב ימינה בודד ואחריו סיבוב שמאלי יחיד. בסיבוב RL, ראשית כל צומת מעביר מיקום אחד ימינה ואז מיקום אחד שמאלה מהמיקום הנוכחי.

ניתוח זמן של עצי AVL

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

ממוצע אלגוריתם המקרה הגרוע ביותר: שטח:, O(n)זמן:O(n)

יישום עצי AVL

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