גובה עץ בינארי

הגדרה

גובה של עץ בינארי הוא אורך המסלול הארוך ביותר מהשורש לעלה, כשמודדים באורך במספר הקשתות. הגדרה רקורסיבית:

• עץ ריק (null) – גובה -1.
• עץ עם צומת בודד (עלה) – גובה 0.
• אחרת – 1 + max(גובה תת־עץ שמאלי, גובה תת־עץ ימני).

שימו לב: יש ספרים שמגדירים גובה של עלה כ־1 ושל עץ ריק כ־0 (מודדים בצמתים במקום בקשתות). חשוב לוודא איזו הגדרה הספר שלכם משתמש – בבגרות בישראל מקובל המוסכמה של 0 לעלה ו־-1 לעץ ריק.

דוגמה מצוירת

אלגוריתם רקורסיבי

// מחזיר את גובה העץ בקשתות. עץ ריק = -1.
public static int height(BinNode<Integer> t) {
    if (t == null)
        return -1;
    int leftH  = height(t.getLeft());
    int rightH = height(t.getRight());
    return 1 + Math.max(leftH, rightH);
}

זמן ריצה: O(n) – כל צומת נבדק פעם אחת. שטח (stack של רקורסיה): O(h) – פרופורציוני לגובה.

נוסחאות שימושיות

• גובה מינימלי בעץ בינארי עם n צמתים: ⌊log₂(n)⌋ (כשהעץ מאוזן).
• גובה מקסימלי: n − 1 (כשהעץ מנוון – כמו רשימה מקושרת).
• מספר צמתים מקסימלי בעץ בגובה h: 2^(h+1) − 1.
• מספר עלים מקסימלי בעץ בגובה h: 2^h.

הקשר ל"רמה" ו"עלה"

גובה הוא מושג גלובלי של העץ. רמה של צומת היא ההפך כיוונית – נמדדת מהשורש כלפי מטה. גובה השורש = הרמה הגבוהה ביותר בעץ. עלים תמיד בגובה 0.