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

בכיתה למדנו כבר על עצי חיפוש בינריים. שאלה זו עוסקת בווריאציה. עץ Foo-Bar מוגדר כך:

1. כל צומת הוא אחד משני סוגים: צומת Foo או צומת Bar.
   1. צומת Bar מחזיק מפתח אחד ו(עד ל)2 ילדים (כמו הצמתים הרגילים שראינו).
   2. צומת Foo מחזיק 2 מפתחות ו(עד ל3 ילדים.
2. העץ מקיים את את תכונת הFoo-Bar - לכל צומת x:
   1. כל מפתח בתת-עץ שמאלי של מפתח כלשהו, קטן או שווה לו.
   2. כל מפתח בתת-עץ ימני של מפתח כלשהו, גדול או שווה לו.
3. כל המסלולים משורש העץ לעלה ריק (Nil) בעל אותו אורך בדיוק.

דוגמה: צומת Bar צומת Bar.

דוגמה: צומת Foo צומת Foo.

דוגמה: עץ Foo-Bar להלן דוגמה לעץ Foo-Bar תקין. בעץ זה 3 צמתים (2 מסוג Bar, ו1 מסוג Foo). יש לו 4 מפתחות, וגבהו 2. עץ Foo-Bar.

אנא הוכח שעץ Foo-Bar הוא לוגריתמי: אם יש בו $\displaystyle n$ מפתחות וגבהו הוא $\displaystyle h$, אז $\displaystyle h=O(\log(n))$.

שימו לב: אל תתייחס לשאלה כיצד ליצור עץ כזה, או כיצד להכניס ולהוציא מפתחות ממנו - זה לא רלוונטי.