עץ בינומי

עץ בינומי הוא עץ מכוּנן עם שורש, שמבנהו בנוי בצורה רקורסיבית. עץ הבסיס B0 הוא צומת יחיד. עץ מסדר n, Bn, מתקבל על־ידי לקיחת שני עצים מהסדר n−1 וחיבור השורש של אחד מהם כבן לשורש של השני. כך B1 הוא שורש עם עלה אחד; B2 הוא שורש שמאלי עם עותק של B1 ועלה בודד מימין; וכן הלאה.

למבנה יש תכונות קבועות: הגובה של Bn הוא n, ומספר הצמתים גדל כפול כל פעם, יש ב‑Bn בדיוק 2 בחזקת n צמתים. במספר הצמתים בכל עומק i משתקפת תבנית של מקדמי הבינום (המספרים שמשתקפים גם במשולש פאסקל). דרגת (degree) השורש היא n, והיא גדולה יותר מדרגת כל צומת אחר.

את העץ הבינומי אפשר לבנות בזמן שכיח של O(n), ובנייתו דומה לבניית ערימה ממערך. מבנה נתונים שנקרא ערימה בינומית מורכב מקבוצת עצים בינומיים בגדלים שונים. ביצירה של ערימה כזו מוסיפים כל קודקוד כעץ מסדר 0 ואז מאחדים תמיד שני עצים מאותו סדר כדי לקבל סדר גבוה יותר, עד שאין עצים זהים.

קיימת גם גרסה לא סדורה של העץ, שבה הצומת שנוסף יכול להיות בן כלשהו של השורש ולא רק השמאלי. בבנייה כזו יש הרבה גרסאות שונות של עצים בינומיים באותו גובה, למשל 2^{n-1} עצים בגובה n.

עץ בינומי הוא סוג מיוחד של עץ עם שורש. שורש הוא הצומת בראש העץ. עלה הוא צומת בלי ילדים.

העץ הקטן ביותר נקרא B0. הוא צומת אחד. ל־B1 יש שורש ועליו עלה אחד. ל־B2 יש שורש, ובצד שמאל עותק של B1 ובצד ימין עלה.

כל פעם שעולים בסדר ה‑n, העץ גדל בצורת חיבור של שני עצים קטנים יותר. הגובה של Bn הוא n. מספר הצמתים ב‑Bn גדל בשיעור של כפול 2 בכל עלייה ב‑n. גם יש דפוס של מספרים בשכבות, כמו במשולש פאסקל (טבלה של מספרים).

ערימה בינומית היא אוסף של עצים כאלו בגדלים שונים. כשבונים ערימה מוסיפים צמתים כעצים קטנים ואז מאחדים עצים שווי סדר.

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