ברוכים הבאים ליחידת הלימוד בנושא "עצים" במסגרת הקורס "מתמטיקה דיסקרטית ח'". עצים הם מבנה נתונים היררכי יסודי ורב עוצמה, בעל חשיבות עצומה במדעי המחשב ומתמטיקה. הם מאפשרים לנו לייצג קשרים היררכיים, לארגן מידע ביעילות ולפתור מגוון רחב של בעיות, החל ממערכות קבצים ועד לאלגוריתמים מורכבים. ביחידה זו נצלול לעומק ההגדרות, התכונות, סוגי העצים השונים, דרכי המעבר בהם, וכיצד אנו מוכיחים תכונות חשובות הקשורות אליהם, בדגש על הוכחות אינדוקטיביות – כלי חיוני לבחינה בטכניון.
מהו עץ? יסודות והגדרות
בבסיסו, עץ הוא גרף קשיר וחסר מעגלים. זוהי הגדרה רקורסיבית המאפשרת לנו לבנות עצים מורכבים מיחידות פשוטות. הבנת המינוח הבסיסי חיונית לכל דיון בעצים.
סוגי עצים נפוצים ותכונותיהם
קיימים סוגים רבים של עצים, כל אחד עם תכונות ייחודיות המתאימות ליישומים ספציפיים. עץ בינארי הוא הנפוץ ביותר.
סוגים ספציפיים של עצים בינאריים:
עץ בינארי מלא (Full Binary Tree):
עץ שבו לכל צומת פנימי (שאינו עלה) יש בדיוק שני ילדים. כלומר, כל צומת הוא או עלה או בעל שני ילדים.
עץ בינארי שלם (Complete Binary Tree):
עץ שבו כל הרמות מלאות, למעט אולי הרמה האחרונה, שבה הצמתים ממולאים משמאל לימין ככל האפשר. עץ בינארי שלם עם n צמתים ניתן לייצג ביעילות באמצעות מערך.
עץ בינארי מאוזן (Balanced Binary Tree):
עץ שבו גובה תת-העצים של כל צומת אינו שונה ביותר מקבוע מסוים (לרוב 1). עצים מאוזנים מבטיחים ביצועים יעילים לפעולות כמו חיפוש, הוספה ומחיקה (לדוגמה, עצי AVL, עצי Red-Black).
עצים בינאריים הם הבסיס למבני נתונים רבים, כגון עצי חיפוש בינאריים, ערימות (Heaps) ועוד.
מעברי עצים ויישומים מרכזיים
מעבר על עץ (Traversal) הוא תהליך של ביקור בכל צומת בעץ בדיוק פעם אחת. ישנן שלוש דרכים עיקריות למעבר על עצים בינאריים, שלכל אחת מהן יישומים שונים.
מעברי עצים בינאריים:
מעבר קדם-סדר (Pre-order Traversal):
בקר בצומת השורש, ואז עבור על תת-העץ השמאלי, ולבסוף על תת-העץ הימני. שימושי לבניית עותק של העץ או לבניית עץ ביטוי.
מעבר תוך-סדר (In-order Traversal):
עבור על תת-העץ השמאלי, בקר בצומת השורש, ולבסוף עבור על תת-העץ הימני. בעץ חיפוש בינארי, מעבר תוך-סדר יחזיר את האיברים בסדר ממוין.
מעבר בתר-סדר (Post-order Traversal):
עבור על תת-העץ השמאלי, ואז על תת-העץ הימני, ולבסוף בקר בצומת השורש. שימושי למחיקת עץ או להערכת עץ ביטוי.
יישומים מרכזיים:
עצי ביטוי (Expression Trees) הם דוגמה נוספת, בהם צמתים פנימיים מייצגים אופרטורים ועלים מייצגים אופרנדים. מעברי עצים שונים יכולים לייצר את הביטוי בפרפיקס, אינפיקס או פוסטפיקס.
הוכחות אינדוקטיביות על עצים
כיוון שעצים מוגדרים באופן רקורסיבי (עץ הוא שורש וקבוצת תת-עצים), אינדוקציה מבנית היא שיטת ההוכחה העיקרית. עלינו להוכיח את טענת הבסיס (עבור העץ הפשוט ביותר, לרוב עץ עם צומת אחד או עץ ריק) ואז את צעד האינדוקציה (בהנחה שהטענה נכונה עבור תת-עצים קטנים יותר, להראות שהיא נכונה עבור העץ כולו).
דוגמה לתכונה להוכחה:
טענה: בעץ בינארי מלא עם L עלים, ישנם 2L-1 צמתים בסך הכל.
רמז לפתרון: השתמשו באינדוקציה על גובה העץ או על מספר העלים. בצעד האינדוקציה, התייחסו לעץ שבו השורש מחובר לשני תת-עצים בינאריים מלאים.
שאלות לדיון
- הסבירו את ההבדל בין עץ בינארי מלא לעץ בינארי שלם. תנו דוגמה לכל אחד.
- בהינתן עץ חיפוש בינארי, תארו את הפלט של מעבר תוך-סדר. מדוע פלט זה שימושי?
- כיצד ניתן לייצג עץ בינארי במערך? מהם היתרונות והחסרונות של ייצוג זה לעומת ייצוג באמצעות מצביעים?
- הוכיחו באינדוקציה כי בעץ בינארי עם N צמתים, ישנם N-1 קשתות.
- הסבירו מדוע הוכחות אינדוקטיביות הן כלי כה חשוב בניתוח תכונות של עצים.
נקודות לתשובת מודל
- הבדל בין מלא לשלם: עץ מלא דורש שלכל צומת פנימי יהיו שני ילדים. עץ שלם דורש שכל הרמות תהיינה מלאות (למעט אולי האחרונה, שממולאת משמאל לימין). דוגמאות גרפיות או טקסטואליות ברורות.
- פלט תוך-סדר ב-BST: הפלט הוא רשימה ממוינת של האיברים בעץ. שימושי לשליפת נתונים בסדר עולה, או לבדיקה שה-BST תקין.
- ייצוג עץ בינארי במערך: צומת במיקום i במערך, ילדיו יהיו ב-2i+1 (שמאל) ו-2i+2 (ימין). יתרונות: חסכון בזיכרון למצביעים, גישה מהירה. חסרונות: בזבוז זיכרון עבור עצים דלילים, קושי בהוספה/מחיקה. ייצוג מצביעים: גמיש יותר, מתאים לעצים דלילים, אך דורש יותר זיכרון למצביעים.
- הוכחה באינדוקציה (N צמתים, N-1 קשתות):
- בסיס: עץ עם צומת אחד (N=1) יש לו 0 קשתות. 1-1=0. נכון.
- הנחת אינדוקציה: נניח שלכל עץ עם k צמתים יש k-1 קשתות.
- צעד אינדוקציה: נתבונן בעץ T עם N+1 צמתים. נסיר עלה v וקשת אחת המחברת אותו להורה שלו u. נקבל עץ T' עם N צמתים. לפי הנחת האינדוקציה, ל-T' יש N-1 קשתות. מכיוון שהסרנו קשת אחת בלבד, לעץ T המקורי היו (N-1)+1 = N קשתות. לכן, לעץ עם N+1 צמתים יש N קשתות.
- חשיבות הוכחות אינדוקטיביות: עצים מוגדרים באופן רקורסיבי, ולכן תכונותיהם ניתנות להוכחה טבעית באמצעות אינדוקציה מבנית. היא מאפשרת לנו להוכיח תכונות כלליות על כל העצים, ללא תלות במבנה הספציפי שלהם, על ידי התבססות על תכונות תת-העצים.