עץ בינארי מלא לעומת עץ בינארי מלא
עץ בינארי הוא עץ שבו לכל צומת יש ילד אחד או שניים. בעץ בינארי, לצומת לא יכולים להיות יותר משני ילדים. בעץ בינארי, ילדים נקראים בתור ילדים "שמאליים" ו"ימין". צמתי הצאצא מכילים הפניה להורה שלהם. עץ בינארי שלם הוא עץ בינארי שבו כל רמה של העץ הבינארי מלאה במלואה מלבד הרמה האחרונה. ברמה הלא מלאה, הצמתים מחוברים החל מהמיקום השמאלי ביותר. עץ בינארי מלא הוא עץ שבו לכל צומת בעץ יש שני ילדים מלבד עלי העץ.
מהו עץ בינארי מלא?
עץ בינארי מלא הוא עץ בינארי שבו לכל צומת בעץ יש בדיוק אפס או שניים ילדים. במילים אחרות, לכל צומת בעץ מלבד העלים יש בדיוק שני ילדים. איור 1 להלן מתאר עץ בינארי מלא. בעץ בינארי מלא, מספר הצמתים (n), מספר הלובים (l) ומספר הצמתים הפנימיים (i) קשורים באופן מיוחד כך שאם אתה מכיר אחד מהם תוכל לקבוע את שני האחרים ערכים כדלקמן:
1. אם לעץ בינארי מלא יש צמתים פנימיים:
– מספר העלים l=i+1
– המספר הכולל של צמתים n=2i+1
2. אם לעץ בינארי מלא יש n צמתים:
– מספר הצמתים הפנימיים i=(n-1)/2
– מספר העלים l=(n+1)/2
3. אם לעץ בינארי מלא יש לי עלים:
– מספר סך הצמתים n=2l-1
– מספר צמתים פנימיים i=l-1
מהו עץ בינארי מלא?
כפי שמוצג באיור 2, עץ בינארי שלם הוא עץ בינארי שבו כל רמה של העץ מלאה במלואה מלבד הרמה האחרונה. כמו כן, ברמה האחרונה, יש לחבר צמתים החל מהמיקום השמאלי ביותר. עץ בינארי שלם בגובה h עומד בתנאים הבאים:
– מצומת השורש, הרמה שמעל לרמה האחרונה מייצגת עץ בינארי מלא בגובה h-1
– לצמתים אחד או יותר ברמה האחרונה עשויים להיות 0 או 1 ילדים
– אם a, b הם שני צמתים ברמה שמעל לרמה האחרונה, אז ל-a יש יותר ילדים מ-b אם ורק אם a ממוקם משמאל ל-b
מה ההבדל בין עץ בינארי מלא לעץ בינארי מלא?
עצים בינאריים מלאים ועצים בינאריים מלאים יש הבדל ברור. בעוד שעץ בינארי מלא הוא עץ בינארי שבו לכל צומת יש אפס או שני ילדים, עץ בינארי שלם הוא עץ בינארי שבו כל רמה של העץ הבינארי מלאה במלואה מלבד הרמה האחרונה. כמה מבני נתונים מיוחדים כמו ערימות צריכים להיות עצים בינאריים שלמים בעוד שהם לא צריכים להיות עצים בינאריים מלאים. בעץ בינארי מלא, אם אתה יודע את מספר הצמתים הכוללים או את מספר הלובים או את מספר הצמתים הפנימיים, אתה יכול למצוא את שני האחרים בקלות רבה. אבל לעץ בינארי שלם אין תכונה מיוחדת המתייחסת לשלוש התכונות האלה.
