עץ בינומי
מתוך ויקיפדיה, האנציקלופדיה החופשית
בתורת הגרפים ובתאוריה של מבני נתונים, עץ בינומי (binomial tree) הוא עץ המוגדר באופן רקורסיבי באופן הבא:
- B0 - עץ בינומי מגובה 0, הוא עץ המורכב מצומת בודד (שורש) בלבד.
- Bk - עץ בינומי מגובה k, מורכב מהוספת (חיבור) עץ בינומי Bk-1 לשורש של עץ בינומי Bk-1 אחר.
דוגמאות:
- B0 - צומת בודד
- B1 - שני צמתים בודדים שנחבר אחד מהם כבנו השמאלי ביותר של האחר (כלומר נקבל שורש בעל בן יחיד)
- B2 - שני עצי B1 שאחד מהם מחובר כבנו השמאלי ביותר של האחר (שורש שבנו השמאלי הוא עלה, ובנו הימני הוא אב לעלה נוסף)
וכן הלאה.
לפיכך, עץ בינומי Bk מורכב משורש עם בנים Bk-1, ... ,B2, B1, B0.
לעץ בינומי מגובה k יש 2k צמתים, ולכן גובה עץ בינומי בעל n צמתים הוא lg n.
מספר הצמתים ברמה d הוא המקדם הבינומי. ההוכחות באינדוקציה.
מבחינים בין שני סוגים של עץ בינומי
- עץ בינומי סדור – חיבור העצים נעשה כך שהמחובר החדש יהיה הבן השמאלי ביותר של השורש (באופן זה, לכל גובה קיים עץ בינומי יחיד)
- עץ בינומי לא סדור – המחובר החדש יהיה בן כלשהו של השורש (לאו דווקא השמאלי ביותר).

