עץ בינומי

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

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

באופן רקורסיבי, העץ הבינומי מגובה 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; יש בו בדיוק \binom{n}{i} צמתים בעומק i עבור i=0,...,n; ודרגת השורש היא n, והיא גדולה מדרגתו של כל צומת אחר.

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

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

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

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