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