עץ בינומי

בתורת הגרפים ובתאוריה של מבני נתונים, עץ בינומי (binomial tree) הוא עץ בעל שורש, המארגן $\ 2^{n}$ צמתים לתת-עצים שכולם בינומיים בעצמם.

באופן רקורסיבי, העץ הבינומי מסדר 0, המסומן B₀, מורכב מצומת אחד בלבד; העץ הבינומי B_n, מסדר n, מתקבל מהוספת השורש של עץ בינומי B_n-1 כצאצא נוסף של השורש של עץ בינומי B_n-1 אחר. בפרט, B₁ מורכב משורש עם עלה יחיד; B₂ - מורכב משורש שיש לו שני צאצאים: עותק של B₁ משמאל, ועלה בודד מימין; וכן הלאה. לפיכך, עץ בינומי B_n מורכב משורש עם בנים B_n-1, ... ,B₂, B₁, B₀.

משמאל לימין: עצים בינומיים מגובה 0 עד 3. לכל עץ יש שורש עם תת-עצים מכל הגבהים הנמוכים ממנו. בעץ הבינומי מסדר 3, למשל, השורש מחובר לעצים מגובה 2, 1, 0 המוקפים במסגרת כחולה, ירוקה ואדומה, בהתאמה

מבניה זו נובע (באינדוקציה) שלעץ הבינומי B_n יש 2ⁿ צמתים; גובהו n; יש בו בדיוק ${\binom {n}{i}}$ צמתים בעומק i עבור i=0,...,n; ודרגת השורש היא n, והיא גדולה מדרגתו של כל צומת אחר.

זמן בניית העץ הבינומי היא (O(n, את העץ הבינומי ניתן לבנות ממערך בדומה לבניה של ערמה.

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

ראו גם

• ערימה בינומית

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

25508541עץ בינומי