ברוכים הבאים ליחידת הלימוד על מבני נתונים מורכבים: עצים, במסגרת הקורס "יסודות מדעי המחשב" (371.1.1601) באוניברסיטת בן-גוריון. עצים הם אחד ממבני הנתונים החשובים והנפוצים ביותר במדעי המחשב, המאפשרים ייצוג יעיל של נתונים היררכיים. מיחידת לימוד זו תבינו את העקרונות הבסיסיים של עצים, סוגיהם השונים, פעולות נפוצות עליהם, וכיצד הם משמשים לפתרון בעיות מעשיות, כגון קידוד נתונים. הבנה מעמיקה של מבנים אלו חיונית הן לפתרון בעיות אלגוריתמיות והן ליישומים מעשיים.
מבוא לעצים ומבנים היררכיים
עץ הוא מבנה נתונים לא לינארי המדמה מבנה היררכי עם קשרים של אב-בן. בניגוד למערכים או רשימות מקושרות, שבהם הנתונים מאורגנים ברצף, עץ מאפשר גישה וארגון מורכבים יותר, המתאימים למגוון רחב של יישומים כגון מערכות קבצים, עצי ביטוי, עצי החלטה ואלגוריתמי דחיסה.
מושגי יסוד וסוגי עצים
הבנת המינוח הבסיסי חיונית לעבודה עם עצים ולניתוח אלגוריתמים המשתמשים בהם:
- צומת (Node): יחידת הנתונים הבסיסית בעץ. כל צומת מכיל ערך וקישורים לצמתים אחרים.
- שורש (Root): הצומת העליון בעץ, שאין לו אב. כל עץ לא ריק מכיל שורש אחד.
- בן/ילד (Child): צומת המחובר לצומת אחר (האב) מתחתיו.
- אב/הורה (Parent): צומת המחובר לצומת אחר (הבן) מעליו.
- עלים (Leaves): צמתים שאין להם בנים.
- עומק (Depth): המרחק של צומת מהשורש (מספר הקשתות מהשורש לצומת). עומק השורש הוא 0.
- גובה (Height): המרחק המקסימלי של צומת עלה מהשורש. לחלופין, גובה של צומת הוא אורך המסלול הארוך ביותר ממנו לעלה כלשהו.
סוגי עצים נפוצים:
- עץ בינארי (Binary Tree): עץ שבו לכל צומת יש לכל היותר שני בנים (שמאל וימין). זהו סוג העץ הנפוץ ביותר במדעי המחשב.
- עץ חיפוש בינארי (Binary Search Tree - BST): סוג מיוחד של עץ בינארי שבו לכל צומת, כל הערכים בתת-העץ השמאלי קטנים מערך הצומת, וכל הערכים בתת-העץ הימני גדולים מערך הצומת. תכונה זו מאפשרת חיפוש, הכנסה ומחיקה יעילים.
מעבר על עצים (Traversals) ופעולות בסיסיות
מעבר על עץ הוא תהליך ביקור בכל צומת בעץ בדיוק פעם אחת. ישנן שלוש שיטות רקורסיביות עיקריות למעבר על עצים בינאריים, הנבדלות בסדר הביקור בצומת הנוכחי ביחס לבניו:
מעבר קדם-סדר (Pre-order Traversal)
בקר בצומת הנוכחי, ואז עבור באופן רקורסיבי על תת-העץ השמאלי, ולבסוף על תת-העץ הימני. שימושי ליצירת עותק של עץ או לבניית עץ ביטוי (לדוגמה, בייצוג פרפיקס).
מעבר תוך-סדר (In-order Traversal)
עבור באופן רקורסיבי על תת-העץ השמאלי, בקר בצומת הנוכחי, ואז עבור על תת-העץ הימני. בעץ חיפוש בינארי, מעבר תוך-סדר מחזיר את הצמתים בסדר ממוין עולה.
מעבר בתר-סדר (Post-order Traversal)
עבור באופן רקורסיבי על תת-העץ השמאלי, ואז על תת-העץ הימני, ולבסוף בקר בצומת הנוכחי. שימושי למחיקת עץ (כדי למנוע מצביעים תלויים) או להערכת עץ ביטוי (פוסטפיקס).
פעולות בסיסיות בעץ חיפוש בינארי:
- חיפוש (Search): מתחילים מהשורש ומשווים את הערך המבוקש עם ערך הצומת הנוכחי. אם קטן, עוברים לבן השמאלי; אם גדול, עוברים לבן הימני. יעילות: O(log N) במקרה מאוזן, O(N) במקרה הגרוע.
- הכנסה (Insertion): מחפשים את המיקום המתאים להכנסת הערך החדש כעלים, תוך שמירה על כללי ה-BST. יעילות דומה לחיפוש.
- מחיקה (Deletion): המורכבת ביותר. ישנם שלושה מקרים: מחיקת עלה, מחיקת צומת עם בן אחד, ומחיקת צומת עם שני בנים (דורש מציאת היורש - הצומת הקטן ביותר בתת-העץ הימני או הגדול ביותר בתת-העץ השמאלי, והחלפתו עם הצומת הנמחק).
קידוד האפמן: יישום קריטי
עקרונות בניית עץ האפמן:
- מתחילים מכל תו כצומת עלה, עם שכיחותו כמשקל.
- יוצרים תור עדיפויות (priority queue) של כל העלים, ממוינים לפי משקל עולה.
- כל עוד יש יותר מצומת אחד בתור:
- מוציאים את שני הצמתים בעלי המשקל הנמוך ביותר.
- יוצרים צומת אב חדש ששני הצמתים שהוצאו הם בניו. משקל האב הוא סכום משקלי הבנים.
- מחזירים את צומת האב החדש לתור העדיפויות.
- הצומת האחרון שנותר בתור הוא שורש עץ האפמן.
לאחר בניית העץ, ניתן לקרוא את קוד האפמן לכל תו על ידי מעבר מהשורש לעלה המתאים. בדרך כלל, מעבר שמאלה מייצג '0' ומעבר ימינה מייצג '1', אך ניתן להחליף את ההקצאה באופן עקבי.
שאלות לדיון
- הסבירו מדוע עץ חיפוש בינארי מאוזן עדיף על עץ חיפוש בינארי לא מאוזן מבחינת יעילות פעולות החיפוש, ההכנסה והמחיקה. מהי מורכבות הזמן במקרה הגרוע ובמקרה הטוב?
- תארו מצב שבו מעבר Pre-order יהיה שימושי יותר ממעבר In-order או Post-order. תנו דוגמה קונקרטית מתוך יישום.
- בהינתן קבוצת תווים ושכיחויות (לדוגמה: A:5, B:9, C:12, D:13, E:16, F:45), בנו את עץ האפמן המתאים וחשבו את אורך הקוד הממוצע לתו.
- כיצד ניתן לייצג עץ בינארי בזיכרון באמצעות מערך במקום באמצעות מצביעים/קישורים? מהם היתרונות והחסרונות של גישה זו, ומתי היא עדיפה?
נקודות לתשובת מודל
- עץ מאוזן מול לא מאוזן: בעץ מאוזן (כמו עץ AVL או עץ אדום-שחור), גובה העץ הוא O(log N), ולכן כל הפעולות (חיפוש, הכנסה, מחיקה) הן ביעילות O(log N). בעץ לא מאוזן (שיכול להתדרדר לרשימה מקושרת), הגובה הוא O(N), והיעילות יורדת ל-O(N).
- שימוש ב-Pre-order: שימושי לבניית עותק של עץ (סריאליזציה) או לייצוג עץ ביטוי (לדוגמה, (A+B)*C) שבו הסדר חשוב לביצוע פעולות. לדוגמה, ייצוג ביטויים בפרפיקס נוטציה (prefix notation) כמו "+ A B".
- בניית עץ האפמן:
- שלב 1: צמתים בודדים: (A:5), (B:9), (C:12), (D:13), (E:16), (F:45).
- שלב 2: מיזוג (A:5, B:9) -> (AB:14). תור עדיפויות: (C:12), (D:13), (AB:14), (E:16), (F:45).
- שלב 3: מיזוג (C:12, D:13) -> (CD:25). תור עדיפויות: (AB:14), (E:16), (CD:25), (F:45).
- שלב 4: מיזוג (AB:14, E:16) -> (ABE:30). תור עדיפויות: (CD:25), (ABE:30), (F:45).
- שלב 5: מיזוג (CD:25, ABE:30) -> (CDABE:55). תור עדיפויות: (F:45), (CDABE:55).
- שלב 6: מיזוג (F:45, CDABE:55) -> (ROOT:100).
- דוגמת קודים (תלוי בבחירת ימין/שמאל): F:0, C:100, D:101, A:1100, B:1101, E:111.
- חישוב אורך קוד ממוצע: (5*4 + 9*4 + 12*3 + 13*3 + 16*3 + 45*1) / 100 = (20 + 36 + 36 + 39 + 48 + 45) / 100 = 224 / 100 = 2.24מצאתם טעות או שחסר משהו?