רמה של עץ בינארי

הגדרה

• השורש נמצא ברמה 0.
• אם צומת נמצא ברמה k, אז הילדים שלו (שמאלי וימני) נמצאים ברמה k+1.

במילים אחרות: הרמה של צומת = מספר הקשתות במסלול היחיד מהשורש אליו.

דוגמה מצוירת

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

• מספר צמתים מקסימלי ברמה k: 2^k.
• מספר צמתים מקסימלי בעץ בגובה h (סכום הרמות 0..h): 2^h+1 − 1.
• בעץ בינארי מלא בגובה h: בכל רמה k יש בדיוק 2^k צמתים.
• בעץ בינארי שלם (Complete): כל הרמות מלאות חוץ אולי מהאחרונה, שבה הצמתים מיושרים שמאלה.

איך מחשבים את הרמה של צומת? (קוד)

// בהינתן השורש וצומת מטרה, מחזיר את הרמה של המטרה.
// אם לא נמצא, מחזיר -1.
public static int levelOf(BinNode<Integer> root, BinNode<Integer> target, int currentLevel) {
    if (root == null) return -1;
    if (root == target) return currentLevel;
    int left = levelOf(root.getLeft(),  target, currentLevel + 1);
    if (left != -1) return left;
    return levelOf(root.getRight(), target, currentLevel + 1);
}
// קריאה ראשונה: levelOf(root, target, 0);

איך סופרים צמתים ברמה k?

public static int countAtLevel(BinNode<Integer> t, int k) {
    if (t == null) return 0;
    if (k == 0) return 1;
    return countAtLevel(t.getLeft(),  k - 1)
         + countAtLevel(t.getRight(), k - 1);
}

זמן ריצה: O(n). שטח: O(h) – לפי גובה העץ.

שימוש: סריקת רוחב (BFS)

סריקת רוחב עוברת על הצמתים רמה אחרי רמה: קודם רמה 0 (השורש), אחר כך כל רמה 1, וכן הלאה. ממומשת באמצעות תור (Queue). שימושית לחיפוש הצומת הקרוב ביותר לשורש לפי תכונה כלשהי.