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