יחידה 5: עצים

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

עצי חיפוש בינאריים (Binary Search Trees - BST)

עץ חיפוש בינארי הוא מבנה נתונים היררכי שבו כל צומת מכיל ערך, ומתקיימים שני תנאים מרכזיים:

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

פעולות בסיסיות וסיבוכיות

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

מעבר על עצים (Traversal)

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

עצי AVL

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

בעיית חוסר האיזון וגורם האיזון

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

סיבובים (Rotations)

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

סיבוכיות זמן

בזכות מנגנון האיזון העצמי, כל הפעולות בעץ AVL (חיפוש, הכנסה, מחיקה) מובטחות בסיבוכיות זמן של O(log n), גם במקרה הגרוע.

עצי B (B-Trees)

עצי B הם עצי חיפוש רב-כיווניים (Multi-way search trees) שתוכננו במיוחד לשימוש במערכות אחסון חיצוניות כמו דיסקים קשיחים. הם ממזערים את מספר פעולות הקלט/פלט (I/O) הנדרשות לגישה לנתונים.

הצורך בעצי B: אחסון על דיסק

בניגוד לעצי BST ו-AVL שמתאימים לאחסון בזיכרון הראשי, עצי B מתוכננים כך שכל צומת יתאים לגודל של בלוק דיסק. זה מאפשר לקרוא או לכתוב צומת שלם בפעולת I/O אחת, ובכך להפחית משמעותית את זמן הגישה לנתונים.

מאפיינים מרכזיים

• סדר (Order) m: כל צומת פנימי (למעט השורש) מכיל בין m/2 ל-m-1 מפתחות, ובין m/2+1 ל-m ילדים. השורש יכול להכיל פחות מפתחות.
• איזון מושלם: כל העלים נמצאים באותה רמה, מה שמבטיח שכל חיפוש יארך זמן דומה.
• מפתחות מסודרים: המפתחות בתוך כל צומת מסודרים בסדר עולה.

פעולות בסיסיות (הכנסה, מחיקה, חיפוש)

פעולות אלו דומות במהותן לאלו של BST, אך מורכבות יותר עקב הצורך לשמור על תכונות עץ B. הכנסה או מחיקה עשויות לדרוש פיצול צמתים (Split) או איחוד צמתים (Merge) כדי לשמור על הסדר והאיזון. סיבוכיות הזמן של פעולות אלו היא O(logm n), כאשר m הוא סדר העץ ו-n הוא מספר המפתחות הכולל. בפועל, מספר פעולות ה-I/O הוא קטן מאוד.

השוואת סוגי העצים

שאלות לדיון

• הסבר מדוע עץ חיפוש בינארי "רגיל" אינו מתאים בהכרח למערכות קריטיות הדורשות ביצועים עקביים, וכיצד עצי AVL פותרים בעיה זו.
• מהם ההבדלים המהותיים בין עץ AVL לעץ B מבחינת המטרה שלשמה הם תוכננו, וכיצד הבדלים אלו משפיעים על מבנה הנתונים שלהם?
• תאר מצב שבו מעבר Pre-order על עץ BST יהיה שימושי יותר ממעבר In-order.
• כיצד סדר העץ (Order) משפיע על ביצועי עץ B, ומדוע בחירת סדר מתאים היא קריטית?

נקודות לתשובת מודל

לשאלה: "מהם ההבדלים המהותיים בין עץ AVL לעץ B מבחינת המטרה שלשמה הם תוכננו, וכיצד הבדלים אלו משפיעים על מבנה הנתונים שלהם?"

• מטרה עיקרית: עץ AVL נועד לאופטימיזציה של זמן ריצה בזיכרון הראשי (RAM), על ידי הבטחת גובה לוגריתמי. עץ B נועד לאופטימיזציה של מספר פעולות קלט/פלט (I/O) באחסון משני (דיסק).
• מבנה הצומת: בעץ AVL, כל צומת הוא בינארי (עד 2 ילדים) ומכיל מפתח אחד. בעץ B, כל צומת הוא רב-כיווני (Multi-way) ויכול להכיל מספר רב של מפתחות וילדים, בגודל של בלוק דיסק.
• מנגנון איזון: עץ AVL שומר על איזון באמצעות גורם איזון וסיבובים. עץ B שומר על איזון מושלם (כל העלים באותה רמה) באמצעות פיצול ואיחוד צמתים.
• גובה העץ: עץ AVL יהיה גבוה יחסית (log₂ n), בעוד שעץ B יהיה נמוך ורחב מאוד (log_m n, כאשר m גדול). גובה נמוך בעץ B ממזער את מספר פעולות ה-I/O.
• סיבוכיות: שניהם מציעים סיבוכיות לוגריתמית, אך בסיסים שונים. AVL: O(log n). B-Tree: O(logm n), כאשר m גדול משמעותית מ-2.