הציעו מבנה נתונים S אשר מתחזק \(n\) מספרים שונים זה מזה ותומך בשגרות הבאות בזמני הריצה המצוינים ליד כל שגרה:

• Build(S,A): בניית המבנה S מתוך מערך ממוין A של \(n\) מספרים ייחודיים, בזמן ריצה של \(O(n)\).
• Insert(S,k): הכנסת המספר השלם \(k\) למבנה S, בזמן ריצה של \(O(\log n)\).
• Delete(S,x): מחיקת האיבר שאליו מצביע \(x\) מהמבנה S, בזמן ריצה של \(O(\log n)\).
• Search(S,k): חיפוש המפתח \(k\) במבנה S, בזמן ריצה של \(O(\log n)\).
• Median(S): החזרת חציון המפתחות במבנה S, בזמן ריצה של \(O(1)\).
• Between(S,k1,k2): החזרת כמות המפתחות \(k\) במבנה S המקיימים \(k_1 \le k \le k_2\), בזמן ריצה של \(O(\log n)\). (הערה: המפתחות \(k_1, k_2\) אינם בהכרח חלק מהמבנה S).

תארו את האלגוריתמים באופן מילולי ובקצרה, ונתחו את נכונותם וסיבוכיותם.