4.3 עצים

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

 

 

 

4.3.1 עצים בינאריים

הצורה הפשוטה ביותר של עץ היא עץ בינארי. עץ בינארי מכיל שני מרכיבים יסודיים:

·        צומת (הנקרא צומת השורש).

·        שני תתי-עצים - ימני ושמאלי, אשר כל אחד מהם מהווה בעצמו עץ בינארי.

 

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

 

עץ בינארי

 

 

הצמתים ברמה התחתונה ביותר של העץ (אלה שללא תתי-עצים) נקראים עלים.

 

בעץ בינארי מסודר מתקיים:

·        המפתחות של כל הצמתים בתת-העץ השמאלי נמוכים מאלה של השורש.

·        המפתחות של כל הצמתים בתת-העץ הימני גדולים מאלה של השורש.

·        תתי-העץ הימני והשמאלי הם בעצמם עצים בינאריים מסודרים.

 

מבנה נתונים

מבנה הנתונים עבור יישום של עץ פשוט מכיל מצביעים ימני ושמאלי במקום המצביע לחוליה הבאה הקיים ביישום של רשימה מקושרת. טען את מבנה עץ

 

מתודת AddToCollection היא רקורסיבית. טען את מתודת AddToCollection.

באופן דומה גם מתודת FindInCollection הינה רקורסיבית. טען את מתודת FindInCollection

 

ניתוח

עץ מלא

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

 

עץ מלא

 

 

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

 

תחילה נחשב כמה צמתים  (n)קיימים בעץ מלא בגובה h.

 

 

n = 1 + 2¹ + 2² + .... + 2^h

 

ומכאן מתקבל:

n = 2^h+1 - 1

וכן:

 

h = floor(log₂n)

 

בחינת המתודה Find מראה כי במקרה הגרוע ביותר יש צורך ב- h+1 או ceiling(log₂n) השוואות כדי למצוא פריט, בדומה לעץ בינארי.

 

אולם, המתודה Add דורשת גם ceiling(log₂n) השוואות על מנת לקבוע היכן להוסיף פריט. למעשה הוספת פריט דורשת מספר קבוע של פעולות, כך שניתן לומר כי עץ בינארי דורש O(logn) פעולות הן להוספה והן למציאה של פריט - שיפור ניכר מחיפוש בינארי, עבור מבנה דינאמי הדורש לעיתים הוספה של פריטים חדשים.

 

הסרת פריט גם היא פעולה בסדר גודל של O(logn).

 

עץ בינארי כללי

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

 

מה קורה במקרה שכזה? חשוב לפני שתקליק כאן!

 

בעיה זו ניתנת לפתרון! לצורך כך נשתמש במבנה הידוע בשם ערמה. בכל אופן, לפני שנסתכל

על ערמות, יש צורך לנסח היטב את הרעיונות שלנו לגבי סיבוכיות של אלגוריתם תוך הגדרה זהירה של מהו בדיוק O(f(n)).

 

 

מושגים

 

שורש

צומת הנמצא "בראש" העץ. זוהי הצומת אשר ממנה מתחילות כל הפעולות על העץ. השורש יכול גם שלא להתקיים ( במקרה של עץ NULL ללא צמתים) או להיות בעל 0 ,1 או 2 בנים בעץ בינארי.

עלה

            צומת הנמצא "בתחתית" העץ - הכי רחוק מהשורש, אשר אין לו אין בנים.

עץ מלא

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

גובה

            מספר הצמתים אשר צריך לעבור מהשורש על מנת להגיע לעלה.

 

 

המשך ל: סיבוכיות                      חזור ל: תוכן עניינים