עץ בינארי bt שכל צומת בו מטיפוס תו, ייקרא "כחול-לבן" אם הוא עץ ריק, או מקיים: (1) כל צומת 'b' או 'w' בלבד; (2) כל עלה הוא 'b'; (3) אם צומת שאינו עלה הוא 'b', יש לו שני בנים 'w'.
עץ בינארי bt שכל צומת בו מטיפוס תו, ייקרא "כחול-לבן" אם הוא עץ ריק, או מקיים: (1) כל צומת 'b' או 'w' בלבד; (2) כל עלה הוא 'b'; (3) אם צומת שאינו עלה הוא 'b', יש לו שני בנים 'w'.
ארבעה עצים בינאריים לבדיקה — פוענחו מתמונת עמוד 13 (java) / עמוד 25 (csharp).
(1): w (צומת יחיד)
(2): b(w(b,·), w(·,b))
(3): w(b [עלה], b(b,·))
(4): w( w(b,b), w(b,w) )
סעיף א
להלן ארבעה עצים בינאריים. לגבי כל אחד מהעצים, קבעו אם הוא עץ כחול-לבן או לא. אם העץ אינו עץ כחול-לבן, העתיקו אותו למחברת, סמנו X בצמתים שאינם מקיימים את התנאים ונמקו מדוע אינם מקיימים.
סעיף ב
כתבו פעולה שתקבל עץ בינארי bt ותחזיר true אם הוא עץ כחול-לבן, ולא — הפעולה תחזיר false.
public static bool IsBlueWhite(BinNode<char> bt)
סעיף ג
מהי סיבוכיות זמן הריצה של הפעולה שכתבתם בסעיף ב'? נמקו את תשובתכם.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.