1) הראה כיצד ניתן לממש בעזרת עצים אדומים שחורים
מבנה נתונים שיכיל שמות סטודנטים ומספרי סטודנט, ויאפשר לחפש סטודנט
לפי שם או מספר. פעולות הוספה, מחיקה וחיפוש צריכות לקחת זמן (O(logn
במקרה הגרוע ביותר.
תשובה
תשובה: מבנה הנתונים יכיל שני עצים אדומים-שחורים:
באחד המפתח יהיה מספרי סטודנט, ובשני שמות.
הוספה: תתבצע הוספה לשני העצים.
מחיקה: יתבצע חיפוש ומחיקה בשני העצים.
חיפוש: נבצע חיפוש בעץ המתאים לנתון אותו מחפשים.
הסתר תשובה
2) אחרי הוספה בעץ
אדום-שחור, מה מספר הסיבובים המקסימלי
שיש לבצע על העץ?
תשובה
תשובה: ראה דרך הוספת איבר:
סיבוב מתבצע רק בסעיפים 4ג ו-4ד. לכן מספר הסיבובים המקסימלי הוא
שניים: כאשר מגיעים לסעיף 4ג אפשר לבצע סיבוב, ואז עוברים לסעיף
4ד שבו ניתן לבצע סיבוב נוסף. לאחר סעיף 4ד העץ חוקי.
הסתר תשובה
3) אחרי מחיקת איבר
בעץ אדום-שחור, מה מספר הסיבובים המקסימלי
שיש לבצע על העץ?
תשובה
תשובה: ראה דרך מחיקת איבר:
סיבוב העץ מתבצע רק במקרים א' ו-ד'. במקרה ד' מתבצעים לכל היותר
2 סיבובים ואחריהם העץ חוקי. במקרה א' מתבצע סיבוב אחד שאחריו עוברים
למקרים ב' או ד' (שאחריהם העץ נשאר חוקי). לכן מספר הסיבובים המקסימלי
הוא 3 (מקרה א' ואחריו מקרה ד').
הסתר תשובה
