ברוכים הבאים ליחידה "מבני נתונים מתקדמים" בקורס "מבני נתונים ומבוא לאלגוריתמים" (20407). יחידה זו צוללת למבני נתונים מורכבים יותר, המאפשרים פתרונות יעילים לבעיות מאתגרות במיוחד, תוך התמודדות עם מגבלות ביצועים או זיכרון. הבנה מעמיקה של מבנים אלו חיונית לא רק לפתרון בעיות תיאורטיות אלא גם ליישומים מעשיים במערכות קבצים, מסדי נתונים, ואלגוריתמים מורכבים. נתמקד במבני נתונים המאזנים ביעילות בין פעולות שונות, תוך שמירה על ביצועים אופטימליים.
עצי חיפוש מאוזנים: עצי אדום-שחור
עצי אדום-שחור (Red-Black Trees) הם סוג של עצי חיפוש בינאריים מאוזנים עצמית, המבטיחים שכל הפעולות הבסיסיות (הכנסה, מחיקה, חיפוש) יתבצעו בזמן O(log n). האיזון מושג באמצעות צביעת צמתים באדום או שחור ושמירה על קבוצה של חמישה כללים.
פעולות וניתוח סיבוכיות
- חיפוש: זהה לעץ חיפוש בינארי רגיל, O(log n).
- הכנסה ומחיקה: מבוצעות כמו בעץ חיפוש בינארי, אך לאחר מכן נדרשים תיקונים (סיבובים ושינויי צבע) כדי לשמור על כללי העץ האדום-שחור. תיקונים אלו מבטיחים שהסיבוכיות נשארת O(log n).
עצי B
עצי B (B-Trees) הם עצי חיפוש מאוזנים רב-כיווניים, שתוכננו במיוחד לשימוש במערכות אחסון חיצוניות (כמו דיסקים קשיחים), שם עלות גישה לבלוק מידע גבוהה משמעותית מעלות עיבוד בזיכרון פנימי. הם ממזערים את מספר פעולות הקריאה/כתיבה לדיסק על ידי שמירת מפתחות רבים בכל צומת.
מאפיינים וסיבוכיות
- דרגה מינימלית (t): לכל צומת פנימי (למעט השורש) יש לפחות t-1 מפתחות ולפחות t ילדים. לשורש יש לפחות ילד אחד (או 0 אם הוא גם עלה).
- איזון: כל העלים נמצאים באותו עומק.
- פעולות: חיפוש, הכנסה ומחיקה מבוצעות בסיבוכיות של O(log_t n), כאשר t הוא הדרגה המינימלית. מכיוון ש-t יכול להיות גדול (לרוב מאות או אלפים), מספר הגישות לדיסק נמוך מאוד.
העשרת מבני נתונים (Augmenting Data Structures)
לעתים קרובות, מבנה נתונים קיים מספק את הפעולות הבסיסיות, אך אנו זקוקים לפעולות נוספות שאינן נתמכות ביעילות. הרעיון של העשרת מבני נתונים הוא להוסיף מידע נוסף לצמתי המבנה הקיים ולעדכן אותו באופן עקבי במהלך פעולות השינוי, ובכך לאפשר פעולות חדשות ביעילות.
דוגמה: מציאת האיבר ה-k הקטן ביותר
כדי למצוא את האיבר ה-k הקטן ביותר בעץ חיפוש בינארי מאוזן (כמו עץ אדום-שחור) בזמן O(log n), ניתן להעשיר כל צומת בשדה נוסף המכיל את גודל תת-העץ ששורשו בצומת זה (כולל הצומת עצמו). בעת הכנסה או מחיקה, יש לעדכן את שדות הגודל במסלול מהצומת שהשתנה ועד לשורש.
עצי אדום-שחור
עצי חיפוש בינאריים מאוזנים עצמית. יעילים לזיכרון פנימי, מבטיחים O(log n) לכל פעולה. מורכבים יותר ליישום.
עצי B
עצי חיפוש רב-כיווניים מאוזנים. אופטימליים לגישה לדיסק (מערכות קבצים, מסדי נתונים). מספר נמוך של גישות לדיסק, אך מורכבים יותר לניהול זיכרון פנימי.
העשרת מבנים
טכניקה להרחבת פונקציונליות של מבני נתונים קיימים. מאפשרת פעולות חדשות ביעילות על ידי הוספת מידע ועדכונו.
שאלות לדיון
- הסבירו מדוע עצי B עדיפים על עצי אדום-שחור במערכות קבצים, למרות ששניהם מציעים סיבוכיות לוגריתמית.
- כיצד הייתם מעשירים עץ אדום-שחור כדי לתמוך בפעולה המונה את מספר האיברים בתחום נתון [a, b] בזמן O(log n)?
- תארו מצב שבו מבנה נתונים פשוט יחסית (כמו רשימה מקושרת) עשוי להיות עדיף על עץ אדום-שחור, ומדוע.
נקודות לתשובת מודל
- עצי B מול עצי אדום-שחור: הדגשת ההבדל בעלות גישה לדיסק מול גישה לזיכרון. עצי B ממזערים גישות לדיסק על ידי שמירת מפתחות רבים בבלוק אחד, דבר שאינו רלוונטי לעצי אדום-שחור המיועדים לזיכרון RAM.
- העשרת עץ לספירת תחום: ניתן להוסיף לכל צומת שדה המכיל את מספר האיברים בתת-העץ שלו. כדי לספור בתחום [a, b], נבצע חיפוש ל-a ול-b, ולאחר מכן נשתמש במידע על גודל תת-העצים ובמסלולים כדי לחשב את הסכום. זה דורש אלגוריתם מורכב יותר אך עדיין ב-O(log n).
- עדיפות רשימה מקושרת: רשימה מקושרת עשויה להיות עדיפה כאשר מספר האיברים קטן מאוד, או כאשר הפעולות העיקריות הן הכנסה/מחיקה בקצוות בלבד, ואין צורך בחיפוש מהיר או גישה אקראית. עלות התקורה של עץ אדום-שחור (זיכרון וזמן לניהול האיזון) הופכת אותו לפחות יעיל במקרים אלו.