עץ בינארי מאוזן ידוע גם כעץ מאוזן בגובה. הוא מוגדר כעץ בינארי כאשר ההפרש בין גובה תת-העץ השמאלי ותת-העץ הימני אינו גדול מ-m, כאשר m בדרך כלל שווה ל-1. גובה העץ הוא מספר הקצוות בנתיב הארוך ביותר בין העץ. צומת שורש וצומת העלה.
העץ הנ'ל הוא א עץ חיפוש בינארי . עץ חיפוש בינארי הוא עץ שבו לכל צומת בצד שמאל יש ערך נמוך יותר מהצומת האב שלו, ולצומת בצד ימין יש ערך גבוה יותר מהצומת האב שלו. בעץ הנ'ל, n1 הוא צומת שורש, ו-n4, n6, n7 הם צומת העלים. הצומת n7 הוא הצומת הרחוק ביותר מצומת השורש. ה-n4 ו-n6 מכילים 2 קצוות וקיימים שלושה קצוות בין צומת השורש לצומת n7. מכיוון ש-n7 הוא הרחוק ביותר מצומת השורש; לכן, גובה העץ הנ'ל הוא 3.
לטקס נגזר חלקי
כעת נראה אם העץ הנ'ל מאוזן או לא. תת העץ השמאלי מכיל את הצמתים n2, n4, n5 ו-n7, בעוד שתת העץ הימני מכיל את הצמתים n3 ו-n6. תת-העץ השמאלי כולל שני צמתים עלים, כלומר n4 ו-n7. יש רק קצה אחד בין הצומת n2 ל-n4 ושני קצוות בין הצמתים n7 ו-n2; לכן, צומת n7 הוא הרחוק ביותר מצומת השורש. גובה תת-העץ השמאלי הוא 2. תת-העץ הימני מכיל רק צומת עלה אחד, כלומר n6, ויש לו רק קצה אחד; לכן, הגובה של תת-העץ הימני הוא 1. ההבדל בין הגבהים של תת-העץ השמאלי ותת-העץ הימני הוא 1. מכיוון שקיבלנו את הערך 1, כך נוכל לומר שהעץ שלמעלה הוא עץ מאוזן בגובה. תהליך זה של חישוב ההפרש בין הגבהים צריך להתבצע עבור כל צומת כמו n2, n3, n4, n5, n6 ו-n7. כאשר אנו מעבדים כל צומת, נגלה שהערך של k אינו עולה על 1, כך שאנו יכולים לומר שהעץ שלמעלה הוא מאוזן עץ בינארי .
בעץ הנ'ל, n6, n4 ו-n3 הם צמתי העלים, כאשר n6 הוא הצומת הרחוק ביותר מצומת השורש. שלושה קצוות קיימים בין צומת השורש לצומת העלה; לכן, גובה העץ הנ'ל הוא 3. כאשר אנו מחשיבים את n1 כצומת השורש, אז תת העץ השמאלי מכיל את הצמתים n2, n4, n5 ו-n6, בעוד תת-עץ מכיל את הצומת n3. בתת העץ השמאלי, n2 הוא צומת שורש, ו-n4 ו-n6 הם צומת עלים. מבין הצמתים n4 ו-n6, n6 הוא הצומת הרחוק ביותר מצומת השורש שלו, ול-n6 יש שני קצוות; לכן, גובהו של תת-העץ השמאלי הוא 2. לתת-העץ הימני יש כל ילד משמאלו ומימין; לכן, גובה תת-העץ הימני הוא 0. מכיוון שגובה תת-העץ השמאלי הוא 2 ותת-העץ הימני הוא 0, כך שההבדל בין גובה תת-העץ השמאלי לתת-העץ הימני הוא 2. לפי ההגדרה, ההבדל בין גובה המשנה השמאלי לתת-העץ הימני אסור להיות גדול מ-1. במקרה זה, ההפרש מגיע להיות 2, שהוא גדול מ-1; לכן, העץ הבינארי לעיל הוא עץ חיפוש בינארי לא מאוזן.
למה אנחנו צריכים עץ בינארי מאוזן?
בואו נבין את הצורך בעץ בינארי מאוזן באמצעות דוגמה.
העץ שלמעלה הוא עץ חיפוש בינארי מכיוון שכל צמתי תת-העץ השמאלי קטנים מצומת האב שלו וכל צמתי תת-העץ הימניים גדולים יותר מצומת האב שלו. נניח שאנו רוצים למצוא את הערך 79 בעץ שלמעלה. ראשית, נשווה את הערך של צומת n1 עם 79; מכיוון שהערך של 79 אינו שווה ל-35 והוא גדול מ-35 אז נעבור לצומת n3, כלומר 48. מכיוון שהערך 79 אינו שווה ל-48 ו-79 גדול מ-48, אז נעבור ימינה ילד בן 48. הערך של הילד הימני של צומת 48 הוא 79 השווה לערך שיש לחפש. מספר הקפיצות הנדרשות לחיפוש אלמנט 79 הוא 2 ומספר הקפיצות המקסימלי הנדרש לחיפוש אלמנט כלשהו הוא 2. המקרה הממוצע לחיפוש אלמנט הוא O(logn).
העץ שלמעלה הוא גם עץ חיפוש בינארי מכיוון שכל צמתי תת-העץ השמאלי קטנים מצומת האב שלו וכל צמתי תת-העץ הימניים גדולים יותר מצומת האב שלו. נניח שאנו רוצים למצוא את הערך 79 בעץ שלמעלה. ראשית, נשווה את הערך 79 עם צומת n4, כלומר, 13. מכיוון שהערך 79 גדול מ-13 אז אנו עוברים לילד הימני של צומת 13, כלומר, n2 (21). הערך של הצומת n2 הוא 21 שהוא קטן מ-79, אז אנחנו שוב עוברים ימינה לצומת 21. הערך של הילד הימני של צומת 21 הוא 29. מכיוון שהערך 79 גדול מ-29 אז נעבור ימינה ילד של צומת 29. הערך של הילד הימני של צומת 29 הוא 35 שהוא קטן מ-79 אז אנחנו עוברים לילד הימני של צומת 35, כלומר, 48. הערך 79 גדול מ-48, אז אנחנו עוברים לילד הנכון של צומת 35. של צומת 48. הערך של צומת ילד ימני של 48 הוא 79 ששווה לערך שיש לחפש. במקרה זה, מספר הקפיצות הנדרשות לחיפוש אלמנט הוא 5. במקרה זה, המקרה הגרוע ביותר הוא O(n).
אם מספר הצמתים גדל, הנוסחה המשמשת בתרשים העץ1 יעילה יותר מהנוסחה המשמשת בתרשים העץ2. נניח שמספר הצמתים הזמינים בשני העצים לעיל הוא 100,000. כדי לחפש אלמנט כלשהו בתרשים עץ2, הזמן הנחוץ הוא 100,000 µs בעוד שהזמן שלוקח לחיפוש אלמנט בתרשים עץ הוא log(100,000) ששווה ל-16.6 µs. אנו יכולים לראות את ההבדל העצום בזמן בין שני עצים לעיל. לכן, אנו מסיקים שהעץ הבינארי של האיזון מספק חיפוש מהיר יותר ממבנה נתוני עץ ליניארי.