8.2 עצי AVL

מבנה נתונים ואלגוריתמים

 

 

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

 

הגדרה של עצי AVL

עץ AVL הוא עץ בינארי בעל התכונות הבאות:

1.      תתי-העצים של כל צומת נבדלים בגובהם ב- 1, לכל היותר.

2.      כל תת-עץ הוא בעצמו עץ AVL.

 

      דרישת האיזון עבור עץ AVL:

     הבדל הגובה בין שני תתי-העצים

     יהיה לכל היותר 1.

 

 

צריכים להיות זהירים לגבי הגדרות אלו: הן מתירות עצים הנראים לא מאוזנים!

הנה מספר עצים כאלה לדוגמא:

 

 

 

הכנסה

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

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

 

 

 

 

 

פריט חדש שהוכנס לתת-העץ השמאלי

של צומת 1 גרם להבדל של 2 בין שני

תתי-העצים. סיבוב לימין מבוצע

כדי לתקן את חוסר האיזון.

 

 

 

 

 

מושגים

 

עצי AVL

עצים הנשארים מאוזנים ובכך מבטיחים זמני חיפוש של O(logn) בסביבה דינאמית. חשוב מכך, הם ניתנים לאיזון מחדש במחיר זול של O(logn).

 

 

המשך ל: עצים n-אריים כלליים                         חזור ל: תוכן עניינים