עץ בינומי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Gnome-colors-edit-find-replace.svg יש לשכתב ערך זה. הסיבה לכך היא: לא נהיר.
אתם מוזמנים לסייע ולתקן את הבעיות, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף. אם אתם סבורים כי אין בדף בעיה, ניתן לציין זאת בדף השיחה.

בתורת הגרפים ובתאוריה של מבני נתונים, עץ בינומי (binomial tree) הוא עץ המוגדר באופן רקורסיבי באופן הבא:

  • B0 - עץ בינומי מגובה 0, הוא עץ המורכב מצומת בודד (שורש) בלבד.
  • Bk - עץ בינומי מגובה k, מורכב מהוספת (חיבור) עץ בינומי Bk-1 לשורש של עץ בינומי Bk-1 אחר.

דוגמאות:

  • B0 - צומת בודד
  • B1 - שני צמתים בודדים שנחבר אחד מהם כבנו השמאלי ביותר של האחר (כלומר נקבל שורש בעל בן יחיד)
  • B2 - שני עצי B1 שאחד מהם מחובר כבנו השמאלי ביותר של האחר (שורש שבנו השמאלי הוא עלה, ובנו הימני הוא אב לעלה נוסף)

וכן הלאה.

לפיכך, עץ בינומי Bk מורכב משורש עם בנים Bk-1, ... ,B2, B1, B0.

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

העץ הבינומי Bk מקיים:

  1. מכיל 2k צמתים.
  2. גובהו k.
  3. ישנם בדיוק \binom{k}{i} צמתים בעומק i עבור i=0,..k
  4. דרגת השורש היא k והיא גדולה מדרגתו של כל צומת אחר.

ההוכחות באינדוקציה.

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

מבחינים בין שני סוגים של עץ בינומי

  • עץ בינומי סדור – חיבור העצים נעשה כך שהמחובר החדש יהיה הבן השמאלי ביותר של השורש (באופן זה, לכל גובה קיים עץ בינומי יחיד)
  • עץ בינומי לא סדור – המחובר החדש יהיה בן כלשהו של השורש (לאו דווקא השמאלי ביותר).
P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.