יום רביעי, 15 בינואר 2014











אלגוריתמים נבחרים בתורת הגרפים

עצים בינריים

עץ בינרי

הגדרה: עץ שבו לכל צומת שאינו עלה יש בן שמאלי ו/או בן ימני.

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



עץ בינרי שלם:
עץ בו לכל צומת פנימי שני בנים

עץ בינרי מלא:
עץ בינרי מלא בו כל
העלים באותו עומק

בעץ בינרי מלא בעל n צמתים, L עלים וגובה h:
.1מספר הצמתים בעומק i: ni=2i
.2מספר העלים: L=nh=2h
.3מספר הצמתים: n=2h+1-1
.4הגובה: h=log2(n+1)-1
.5מספר הצמתים הפנימיים:
n-L=2h-1=L-1

לפניכם דוגמא לעץ בינרי, האם הוא עץ חיפוש בינרי?

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

אין תגובות:

הוסף רשומת תגובה