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

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

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