עץ AVL
מתוך ויקיפדיה, האנציקלופדיה החופשית
במדעי המחשב, עץ AVL הוא עץ חיפוש מאוזן, שבו הפרש גובהם של תת העצים הבנים של כל צומת הוא לכל היותר 1. תכונה זו מבטיחה שניתן יהיה לחפש בעץ ולהכניס או להוציא ממנו נתונים בסיבוכיות של 
במקרה הגרוע ביותר, כאשר 
הוא מספר האיברים בעץ.
עץ AVL נקרא כך על שם ממציאיו, Adelson-Velskii ו- Landis, שפיתחו אותו בשנת 1962.
[עריכה] דרך פעולת העץ
כל צומת בעץ שומר, פרט למידע הסטנדרטי של עץ חיפוש, גם מאפיין נוסף הנקרא "גורם האיזון" (Balance factor) . מאפיין זה הוא ההפרש בין גובהו של תת העץ השמאלי של הצומת ותת העץ הימני של הצומת.
בעת הכנסת איברים לעץ או הוצאת איברים ממנו, יכול להשתנות רק גורם האיזון של צמתים במסלול הכניסה או ההוצאה של האיבר שאותו משנים. לכן, בודקים מלמטה למעלה את גורמי האיזון של הצמתים לאחר שבוצעו השינויים בעץ, ואם מגלים חוסר איזון בצומת כלשהו, מבצעים "גלגול" - החלפת הצומת באחד מבניו, תוך העברת אחד מתת העצים אל הבן. בחלק מהמקרים נדרש גלגול אחד, ובחלק שניים, ודי בהם כדי להבטיח שמירה על איזון העץ. במקרה של הוספת איבר לעץ, לאחר שהתבצע גלגול מוצלח מובטח שהעץ יהיה מאוזן, אך במקרה של הוצאה יש לעבור לכל אורך מסלול החיפוש ולבצע גלגולים במידת הצורך.
כל גלגול משנה רק מספר קבוע של צמתים, ולכן מתבצע בזמן קבוע. לכן פעולות ההוצאה וההכנסה מבוצעות בזמן .
