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

הפתרון דומה מאד להוכחת הטענה שעצים אדומים-שחורים הם לוגריתמיים. נניח שגובה העץ הוא $\displaystyle h$. מה מספר המפתחות הקטן ביותר היכול להיות בעץ? קל לראות שזה המספר המתקבל כאשר כל אחד מהצמתים הוא מסוג Bar. במצב זה, היות שעל פי הנתונים כל המסלולים משורש לעלה הם בעלי אותו אורך, נקבל שמספר המפתחות הוא לכל הפחות $\displaystyle \sum _{i=1}^{h}\left[2^{i-1}\right]=2^{h}-1$. הפתרון, לכן, מתקבל על ידי פתירת אי-השוויון $\displaystyle n\geq 2^{h}-1$:

$\displaystyle n\geq 2^{h}-1\Rightarrow$
$\displaystyle n\geq 2^{h}/2\Rightarrow$
$\displaystyle \log(n)\geq h-1\Rightarrow$
$\displaystyle h=O\left(\log(n)\right)$