יש לתכנן מבנה נתונים המבוסס על עץ חיפוש בינארי מאוזן, התומך בפעולות הבאות:

• INSERT(key): הכנסת מפתח חדש.
• DELETE(key): מחיקת מפתח קיים.
• SEARCH(key): חיפוש מפתח.
• MEAN(a, b): החזרת ממוצע ערכי המפתחות בקטע הסגור \([a, b]\).

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

א. תארו את מבנה הנתונים. אילו שדות נוספים יש להוסיף לכל צומת בעץ? כיצד יש לעדכן שדות אלו בפעולות INSERT ו-DELETE?
ב. תארו את המימוש של פעולת MEAN(a, b) באמצעות מבנה הנתונים שהצעתם, ונתחו את סיבוכיותה.