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

הגדרה: נאמר שעץ הוא דחוס אם כל צומת בגובה $h$ הוא ראשו של תת-עץ בעל $\mathrm{\Theta }(2^h)$ איברים.

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