א. יהי \(T\) עץ בינארי המכיל "שרשרת" בת שלושה צמתים (כלומר, קיים ב-\(T\) צומת שיש לו רק בן אחד, ולצומת זה יש רק בן אחד). הוכיחו או הפריכו: ניתן לצבוע את צומתי \(T\) כך שיתקבל עץ אדום-שחור חוקי.
הערה: צמתי ה-NIL של העץ האדום-שחור אינם חלק מהצמתים המקוריים של \(T\).

ב. נתון עץ בינארי \(B\) בעל \(n\) צמתים. מצד אחד, העץ מקיים את תכונת ערמת המקסימום: מפתחות הבנים קטנים ממפתח האב או שווים לו. מצד שני, העץ מקיים את תכונת עץ החיפוש הבינרי: לכל צומת \(x\) בעץ, המפתחות בתת-עץ השמאלי קטנים מהמפתח של \(x\) או שווים לו, והמפתחות בתת-עץ הימני גדולים מהמפתח של \(x\) או שווים לו. תארו את מבנה (צורת) העץ, בהנחה שכל המפתחות שונים זה מזה.

ג. נתון עץ בינארי \(B\) בעל \(n\) צמתים. בכל צומת יש זוג שדות (key, priority). מצד אחד, העץ מקיים את תכונת ערמת המקסימום ביחס לשדה ה-priority: ערך ה-priority אצל הבנים קטן מערך זה אצל האב או שווה לו. מצד שני, העץ מקיים את תכונת עץ החיפוש הבינרי ביחס לשדה ה-key: לכל צומת \(x\) בעץ, המפתחות (שדות ה-key) בתת-עץ השמאלי קטנים מהמפתח של \(x\) או שווים לו, והמפתחות בתת-עץ הימני גדולים מהמפתח של \(x\) או שווים לו. באילו תנאים יהיה מבנה העץ זהה לזה שבסעיף הקודם? (ניתן להניח שכל המפתחות וכל ערכי ה-priority שונים זה מזה).