עץ בינומי

מתוך ויקיפדיה, האנציקלופדיה החופשית

בתורת הגרפים ובתאוריה של מבני נתונים, עץ בינומי (binomial tree) הוא עץ בעל שורש, המארגן צמתים לתת-עצים שכולם בינומיים בעצמם.

באופן רקורסיבי, העץ הבינומי מסדר 0, המסומן B0, מורכב מצומת אחד בלבד; העץ הבינומי Bn, מסדר n, מתקבל מהוספת השורש של עץ בינומי Bn-1 כצאצא נוסף של השורש של עץ בינומי Bn-1 אחר. בפרט, B1 מורכב משורש עם עלה יחיד; B2 - מורכב משורש שיש לו שני צאצאים: עותק של B1 משמאל, ועלה בודד מימין; וכן הלאה. לפיכך, עץ בינומי Bn מורכב משורש עם בנים Bn-1, ... ,B2, B1, B0.

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

מבניה זו נובע (באינדוקציה) שלעץ הבינומי Bn יש 2n צמתים; גובהו n; יש בו בדיוק צמתים בעומק i עבור i=0,...,n; ודרגת השורש היא n, והיא גדולה מדרגתו של כל צומת אחר.

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

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

ראו גם[עריכת קוד מקור | עריכה]


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