הצגת המקור של הדף "עץ מאוזן"

{{מבנה נתונים
| תמונה = [[קובץ:AVLtreef.svg|250px]]
| כיתוב = דוגמה לעץ מאוזן (במקרה זה מסוג [[עץ AVL|AVL]] המקיים את תכונת האיזון)
| קישור זיכרון =
| זיכרון ממוצע = {{משמאל לימין|O(n)}}
| זיכרון במקרה הגרוע = {{משמאל לימין|O(n)}}
| קישור חיפוש = #פעולת חיפוש
| חיפוש ממוצע = {{משמאל לימין|O(log n)}}
| חיפוש במקרה הגרוע = {{משמאל לימין|O(log n)}}
|קישור הכנסה=#פעולת הכנסה
|הכנסה ממוצע= תלוי במימוש
|הכנסה במקרה הגרוע= תלוי במימוש
|קישור הוצאה=#פעולת מחיקה
|הוצאה ממוצע= תלוי במימוש
|הוצאה במקרה הגרוע= תלוי במימוש
}}

'''עץ מאוזן''' הוא רעיון של [[מבנה נתונים]] מסוג [[עץ חיפוש בינארי]], עץ חיפוש יקרא עץ מאוזן אם הגובה של העץ יהיה שווה ל- <math>\log_2(n)</math> של (כאשר <math>\ n</math>הוא מספר הצמתים בעץ). כלומר עבור עץ <math>\ T</math> וגובה <math>\ h</math> אז העץ יהיה מאוזן אם: <math>\ h(T) </math> = <math>\ O(\log n)</math><ref>{{קישור כללי|כתובת=http://www.math-wiki.com/images/c/cf/Trees-AVL1.pdf|הכותב=math-wiki|כותרת=Trees}}</ref>

תכונה זו מבטיחה שניתן יהיה לחפש בעץ ב[[סיבוכיות זמן|סיבוכיות]] של <math>\ O(\log n)</math> במקרה הגרוע ביותר.

=== מהלך פעולה ===
עץ מאוזן כשלעצמו איננו מבטא מבנה נתונים בעל דרך להגיע למצב זה, אלא רעיון כללי לעץ שעבורו מתקיימים הדרישות ומכך גם מתקיימת תכונת החיפוש ב - <math>\ O(\log n)</math>. והוא בדומה ל[[עץ בינארי]] מייצג קבוצה מסוימת המקיימת תכונה מסוימת (בהתאם) עבור מבנה נתונים.

== תתי עצים ==
פותחו כמה [[מערכת מודל|מודלים]] מסוג [[עץ חיפוש בינארי|עצי חיפוש בינארים]] המקיימים את התכונה הזו, ובניהם:
* [[עץ AVL]]
* [[עץ אדום שחור]]
* [[ערימת פיבונאצ'י]]

כל עץ מבצע פעולה הנקראת "איזון" על מנת להמשיך לקיים את דרישות העץ המאוזן. לדוגמה: עבור עץ AVL פעולת האיזון נקראת "גלגול".

== משפטים ==
רשימת משפטים הנכונים עבור כל עץ המקיים את תכונת עץ מאוזן:
* [[עץ מנוון]] לעולם איננו יהיה עץ מאוזן אלא אם בעץ צומת אחת בלבד והיא השורש.
* ההפרש בין הגובה של שני תתי-עצים של אותו הצומת לעולם אינו גדול מאחד.
* אם <math>n=2^h</math> אז העץ הוא [[עץ שלם]].

== ראו גם ==
* [[עץ חיפוש]]
* [[עץ אדום שחור]]
* [[עץ AVL]]

== קישורים חיצוניים ==
{{ויקישיתוף בשורה}}

== הערות שוליים ==
{{הערות שוליים}}


[[קטגוריה:עצים (גרפים)|בינארי]]