עץ AVL

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
דוגמה לעץ 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).

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

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

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