ברוכים הבאים לשיעור בנושא עצי חיפוש בינאריים מאוזנים, יחידה קריטית בקורס "מבני נתונים ומבוא לאלגוריתמים" (20407) באוניברסיטה הפתוחה. יחידה זו מתמודדת עם אחת המגבלות המרכזיות של עצי חיפוש בינאריים רגילים: היכולת שלהם להתדרדר במקרה הגרוע למבנה דמוי רשימה מקושרת, מה שמוביל לזמני ריצה של O(n) עבור פעולות כמו חיפוש, הכנסה ומחיקה. עצים מאוזנים פותרים בעיה זו על ידי הבטחת גובה לוגריתמי, ובכך שומרים על יעילות O(log n) באופן עקבי. הבנה מעמיקה של עקרונות האיזון, סוגי העצים השונים והאלגוריתמים הנלווים היא חיונית להצלחה במבחן.
הצורך בעצים מאוזנים
עץ חיפוש בינארי (BST) הוא מבנה נתונים המאפשר חיפוש, הכנסה ומחיקה של איברים בזמן ממוצע של O(log n). אולם, במקרה הגרוע, כאשר האיברים מוכנסים בסדר עולה או יורד, העץ יכול להפוך לרשימה מקושרת, וזמן הריצה של כל הפעולות הללו יתדרדר ל-O(n). מצב זה פוגע קשות ביעילות המבנה.
עצים מאוזנים נועדו למנוע את התדרדרות הביצועים הזו. הם עושים זאת על ידי שמירה על "מאפיין איזון" קפדני, המבטיח שגובה העץ יישאר לוגריתמי ביחס למספר האיברים (n). כאשר פעולות הכנסה או מחיקה מפרות את מאפיין האיזון, העץ מבצע סדרת פעולות "איזון מחדש" כדי לשחזר אותו.
עקרונות האיזון: סיבובים וגובה
הכלי המרכזי לשמירה על איזון בעצים בינאריים הוא ה"סיבוב" (Rotation). סיבובים הם פעולות מקומיות המשנות את מבנה העץ מבלי לפגוע בתכונת עץ החיפוש הבינארי. הם מאפשרים להזיז צמתים למעלה או למטה בעץ כדי להקטין את גובהו או לתקן הפרות איזון.
סוגי סיבובים:
- סיבוב יחיד (Single Rotation): מתבצע כאשר הפרת האיזון היא "קו ישר" (לדוגמה, הכנסה לתת-עץ ימני של בן ימני). ישנם סיבוב שמאלה (Left Rotation) וסיבוב ימינה (Right Rotation).
- סיבוב כפול (Double Rotation): מתבצע כאשר הפרת האיזון היא "זיג-זג" (לדוגמה, הכנסה לתת-עץ שמאלי של בן ימני). זהו למעשה רצף של שני סיבובים יחידים (לדוגמה, Left-Right Rotation או Right-Left Rotation).
סוגי עצים מאוזנים נפוצים
קיימים מספר סוגים של עצי חיפוש בינאריים מאוזנים, כאשר הבולטים והנלמדים ביותר הם עצי AVL ועצי Red-Black.
עצי AVL
עצי AVL הם עצי חיפוש בינאריים שבהם לכל צומת, הפרש הגבהים בין תת-העץ השמאלי לתת-העץ הימני שלו הוא לכל היותר 1. זהו מאפיין איזון קפדני מאוד, המבטיח שגובה העץ יהיה O(log n). פעולות הכנסה ומחיקה בעץ AVL עשויות לדרוש עד שני סיבובים (יחידים או כפולים) כדי לשחזר את האיזון.
- מאפיין איזון: גורם איזון (-1, 0, 1).
- מורכבות: O(log n) לכל הפעולות.
- יתרונות: חיפוש מהיר מאוד בזכות האיזון הקפדני.
- חסרונות: פעולות הכנסה/מחיקה עשויות להיות מורכבות יותר למימוש בשל הצורך לעדכן גבהים ולבצע סיבובים רבים.
עצי Red-Black
עצי Red-Black הם עצי חיפוש בינאריים המקיימים חמישה מאפיינים: 1. כל צומת הוא אדום או שחור. 2. השורש שחור. 3. כל העלים (צמתי NIL) שחורים. 4. אם צומת אדום, אז שני בניו שחורים. 5. לכל מסלול פשוט מצומת לעלה כלשהו בתת-העץ שלו יש אותו מספר צמתים שחורים. מאפיינים אלו מבטיחים שגובה העץ יהיה לכל היותר 2 log(n+1), כלומר O(log n).
- מאפיין איזון: חמישה כללים על צבעי הצמתים.
- מורכבות: O(log n) לכל הפעולות.
- יתרונות: מימוש הכנסה ומחיקה פשוט יותר במעט מ-AVL, נפוץ בשימוש במערכות הפעלה ובספריות סטנדרטיות.
- חסרונות: חיפוש עשוי להיות מעט איטי יותר מ-AVL במקרה הגרוע (אך עדיין O(log n)), בשל איזון פחות קפדני.
השוואה ושיקולי בחירה
הבחירה בין עץ AVL לעץ Red-Black תלויה בדרישות הספציפיות של היישום.
- עצי AVL מתאימים יותר למצבים שבהם פעולות חיפוש תכופות יותר מפעולות הכנסה/מחיקה, שכן הם מציעים את האיזון הקפדני ביותר ובכך את זמני החיפוש המהירים ביותר.
- עצי Red-Black מועדפים כאשר יש איזון בין פעולות חיפוש, הכנסה ומחיקה, או כאשר פעולות הכנסה/מחיקה תכופות יותר, שכן הם דורשים פחות סיבובים בממוצע (אך יותר שינויי צבע). המימוש שלהם נחשב לפעמים לפשוט יותר מבחינת קוד.
שני סוגי העצים מבטיחים ביצועים לוגריתמיים, אך הדרך שבה הם משיגים זאת והעלויות הנלוות שונות. הבנת הניואנסים הללו תעזור לכם לא רק במבחן אלא גם בתכנון מערכות בעולם האמיתי.
שאלות לדיון
- הסבירו מדוע עץ חיפוש בינארי רגיל אינו מספק פתרון יעיל במקרה הגרוע, וכיצד עצים מאוזנים מתמודדים עם בעיה זו.
- תארו את ההבדלים העיקריים בין עץ AVL לעץ Red-Black מבחינת מאפייני האיזון, מורכבות המימוש של פעולות הכנסה/מחיקה, והשימושים האופייניים.
- בהינתן עץ AVL, ציירו את מצבו לאחר הכנסת סדרת איברים המצריכה סיבוב יחיד ולאחר מכן סיבוב כפול. הסבירו את סוגי הסיבובים שביצעתם.
- מהו "גורם איזון" בעץ AVL, ומדוע הוא מוגבל לערכים -1, 0, 1? מה קורה כאשר הוא חורג מגבולות אלו?
נקודות לתשובת מודל
- הצורך באיזון: התייחסות למקרה הגרוע של BST רגיל (O(n)) והצורך להבטיח O(log n).
- עקרונות האיזון: הגדרה של גובה, גורם איזון, והסבר על סיבובים (יחידים וכפולים) כתהליך תיקון.
- עצי AVL: הגדרת מאפיין האיזון הקפדני (גורם איזון (-1, 0, 1)), מורכבות O(log n), ודוגמאות לסיבובים.
- עצי Red-Black: הגדרת חמשת כללי הצבע, מורכבות O(log n), והשוואה ל-AVL מבחינת קפדנות האיזון וקלות המימוש.
- השוואה ובחירה: דיון בטרייד-אופים בין AVL ל-Red-Black (חיפוש מול עדכון, מורכבות מימוש) והתאמה לתרחישי שימוש שונים.
- ניתוח אלגוריתמים: היכולת לנתח את זמן הריצה של פעולות שונות על עצים אלו.
- יישום: הבנה כיצד לבצע פעולות הכנסה ומחיקה, כולל זיהוי וביצוע הסיבובים הנדרשים.