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

• SEARCH(S, k): חיפוש אחר המפתח \(k\) במבנה \(S\).
• INSERT(S, k): הכנסת המפתח \(k\) למבנה \(S\).
• DELETE(S, x): מחיקת האיבר שאליו מצביע \(x\) מהמבנה \(S\).
• MEAN(S, a, b): החזרת ממוצע כל המפתחות \(k\) במבנה \(S\) המקיימים \(a \le k \le b\).

כל הפעולות צריכות להתבצע בסיבוכיות זמן של \(O(\log n)\).
תארו במפורט ובמדויק את מבנה הנתונים ואת מימוש כל אחת מהפעולות.