מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים/תרגילים/מציאת איברי קצה בעץ דחוס/שאלה

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

נניח שמספר המפתחות בקבוצה הוא $\displaystyle n$. אנא שנה את מבנה עץ החיפוש הבינרי, ובפרט את פעולת Member, כך שMember(t, x) יעבוד בזמן $\displaystyle \log(k)$ אם $\displaystyle x$ אכן איבר בקבוצה, והוא האיבר ה$\displaystyle k$ הקטן ביותר.

שים לב שתשובתך אמורה להיות נכונה לכל $\displaystyle k=1,\ldots ,n$.