ברוכים הבאים ליחידת הלימוד על עצים בינאריים, מבנה נתונים לא לינארי ורב עוצמה, המשמש בסיס לאלגוריתמים רבים במדעי המחשב. ביחידה זו נצלול לעומקם של עצים בינאריים, נבין את המבנה שלהם, את אופן פעולתם, ונתמקד במיוחד בעצי חיפוש בינאריים (BST) – וריאציה קריטית להבנת יעילות חיפוש, הכנסה ומחיקה של נתונים. נדון במושגי יסוד, פעולות נפוצות, ונבחן את יעילותן, תוך התייחסות למורכבות ורקורסיה, שהן לב ליבה של עבודה עם עצים.
מבוא לעצים בינאריים
עץ בינארי הוא מבנה נתונים היררכי המורכב מצמתים (Nodes), כאשר לכל צומת יש לכל היותר שני צמתים-בנים: בן שמאלי ובן ימני. מבנה זה מאפשר ארגון נתונים בצורה המקלה על פעולות רבות.
סוגי עצים בינאריים נפוצים
עץ בינארי מלא (Full Binary Tree)
כל צומת בעץ מכיל 0 או 2 בנים. כלומר, אין צמתים עם בן אחד בלבד.
עץ בינארי שלם (Complete Binary Tree)
כל הרמות מלאות, למעט אולי הרמה האחרונה, שבה הצמתים ממולאים משמאל לימין.
עץ בינארי מושלם (Perfect Binary Tree)
עץ שבו כל הצמתים הפנימיים הם בעלי שני בנים, וכל העלים נמצאים באותה רמה. עץ כזה הוא גם מלא וגם שלם.
עצי חיפוש בינאריים (Binary Search Trees - BST)
עץ חיפוש בינארי הוא סוג מיוחד של עץ בינארי, שבו יש סדר מסוים בין הצמתים, המאפשר חיפוש יעיל. תכונה זו היא קריטית להבנת היתרונות של BST.
X מתקיימים התנאים הבאים:
- כל הערכים בתת-העץ השמאלי של
Xקטנים או שווים לערך שלX. - כל הערכים בתת-העץ הימני של
Xגדולים או שווים לערך שלX.
תכונת הסדר הזו מאפשרת לבצע פעולות חיפוש, הכנסה ומחיקה ביעילות רבה, בדומה לחיפוש בינארי במערך ממויין, אך עם גמישות רבה יותר לשינויים.
פעולות מרכזיות בעצים
הבנת הפעולות הבסיסיות היא המפתח לשליטה בעצים. רובן ממומשות באופן רקורסיבי בשל האופי הרקורסיבי של מבנה העץ.
חיפוש (Search)
ב-BST, חיפוש אלמנט מתחיל מהשורש. אם הערך המבוקש קטן מערך הצומת הנוכחי, ממשיכים לתת-העץ השמאלי; אם גדול, ממשיכים לתת-העץ הימני. אם שווה, נמצא. אם מגיעים לעלה ולא נמצא, הערך אינו קיים.
הכנסה (Insertion)
הכנסת אלמנט חדש ל-BST מתבצעת באופן דומה לחיפוש. יורדים בעץ לפי כללי ה-BST עד שמגיעים למקום שבו האלמנט צריך להיות מוכנס כעלֶה חדש.
מחיקה (Deletion)
מחיקת צומת מ-BST היא הפעולה המורכבת ביותר, שכן יש להתייחס לשלושה מקרים:
- צומת עלה: פשוט מוחקים אותו.
- צומת עם בן אחד: מחליפים את הצומת בבנו היחיד.
- צומת עם שני בנים: זהו המקרה המאתגר ביותר. יש למצוא את "העוקב" (successor) של הצומת (הערך הקטן ביותר בתת-העץ הימני), להחליף את ערך הצומת הנמחק בערך העוקב, ולמחוק את העוקב ממקומו המקורי (שיהיה תמיד צומת עלה או צומת עם בן ימני אחד).
מעבר על העץ (Traversal)
ישנן שלוש דרכים עיקריות לעבור על כל צמתי העץ:
Inorder Traversal (סדר תוכי)
מבקרים בתת-העץ השמאלי, אחר כך בצומת הנוכחי, ולבסוף בתת-העץ הימני. ב-BST, מעבר Inorder יפיק את הערכים בסדר עולה.
Preorder Traversal (סדר קדמי)
מבקרים בצומת הנוכחי, אחר כך בתת-העץ השמאלי, ולבסוף בתת-העץ הימני. שימושי ליצירת עותק של העץ.
Postorder Traversal (סדר אחורי)
מבקרים בתת-העץ השמאלי, אחר כך בתת-העץ הימני, ולבסוף בצומת הנוכחי. שימושי למחיקת עץ שלם (מהעלים כלפי מעלה).
יעילות וסיבוכיות
יעילות הפעולות בעצי חיפוש בינאריים תלויה במידה רבה בגובה העץ. במקרה הטוב (עץ מאוזן), גובה העץ הוא O(log n), ולכן פעולות חיפוש, הכנסה ומחיקה הן בסיבוכיות זמן של O(log n). במקרה הגרוע (עץ מנוון, שנראה כמו רשימה מקושרת), גובה העץ הוא O(n), וסיבוכיות הזמן תהיה O(n). זו הסיבה לחשיבותם של עצים מאוזנים עצמית (כמו AVL או Red-Black Trees), אך אלו אינם חלק מיחידה זו.
שאלות לדיון
- הסבר מדוע עץ חיפוש בינארי מנוון (degenerate BST) מאבד את יתרונות היעילות שלו, וכיצד הוא מתנהג בהשוואה למבנה נתונים אחר שלמדתם?
- כיצד ניתן למצוא את הערך המינימלי והמקסימלי ב-BST ביעילות? כתוב פסאודו-קוד קצר לכל אחת מהפעולות.
- בהינתן סדרת ערכים, תאר כיצד ניתן לבנות מהם BST. האם סדר הכנסת הערכים משפיע על מבנה העץ הסופי? נמק.
- הסבר את ההבדל בין מעבר Preorder למעבר Postorder, ותן דוגמה לשימוש מעשי לכל אחד מהם.
נקודות לתשובת מודל
- BST מנוון: עץ שבו כל צומת מכיל רק בן אחד (שמאלי או ימני). הוא מתנהג כמו רשימה מקושרת, וסיבוכיות הפעולות הופכת ל-O(n) במקום O(log n).
- ערך מינימלי/מקסימלי: מינימלי - יורדים תמיד שמאלה עד שמגיעים לצומת ללא בן שמאלי. מקסימלי - יורדים תמיד ימינה עד שמגיעים לצומת ללא בן ימני.
- בניית BST: מתחילים עם השורש, וכל ערך נוסף מוכנס לפי כללי ה-BST. סדר ההכנסה בהחלט משפיע על מבנה העץ (לדוגמה, הכנסת ערכים ממויינים תייצר עץ מנוון).
- Preorder vs. Postorder: Preorder מבקר בשורש לפני הבנים (שימושי להעתקת עץ או יצירת ביטויים). Postorder מבקר בשורש אחרי הבנים (שימושי למחיקת עץ או חישוב ביטויים).