שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2018 - עצי חיפוש
קבעו אם הטענה הבאה נכונה או לא והסבירו בקצרה (2-3 שורות):
ביצוע רוטציה בעץ אדום שחור שומר על כל תכונות העץ.
ביצוע רוטציה בעץ אדום שחור שומר על כל תכונות העץ.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
שאלה חוזרתהאוניברסיטה הפתוחהמבחן סמסטר ב2018 סמסטר ב | 2018 סמסטר ב
★★★★★
עצי חיפושעץ אדום-שחור
חשבו אילו תכונות של עץ אדום-שחור עשויות להישמר ואילו עשויות להיפגע ברוטציה בלבד (ללא שינוי צבעים).
לא נכון.
רוטציה שומרת על תכונת עץ החיפוש הבינרי (הסדר בין האיברים נשמר), אך לא בהכרח שומרת על כל תכונות העץ האדום-שחור. רוטציה בלבד (ללא שינוי צבעים) עלולה להפר את התכונה שכל מסלול מהשורש לעלה מכיל אותו מספר צמתים שחורים (black-height), או את התכונה שלצומת אדום אין בן אדום. לכן, ברוטציות שמבוצעות כחלק מהכנסה/מחיקה, תמיד מלווה גם שינוי צבעים כדי לשמור על כל התכונות.
רוטציה שומרת על תכונת עץ החיפוש הבינרי (הסדר בין האיברים נשמר), אך לא בהכרח שומרת על כל תכונות העץ האדום-שחור. רוטציה בלבד (ללא שינוי צבעים) עלולה להפר את התכונה שכל מסלול מהשורש לעלה מכיל אותו מספר צמתים שחורים (black-height), או את התכונה שלצומת אדום אין בן אדום. לכן, ברוטציות שמבוצעות כחלק מהכנסה/מחיקה, תמיד מלווה גם שינוי צבעים כדי לשמור על כל התכונות.