Ermittle, wie viele Ebenen ein balancierter binärer Suchbaum mit

• a) 12
• b) 1500
• c) 10 000 000 000

Elementen besitzt.

Zu a)
$$2^n - 1 \ge 12$$ $$\Leftrightarrow n \ge log_2 (12 + 1)$$ $$\Rightarrow \ge \approx 3,70$$ Der Baum hat vier Ebenen.

Zu b)
$$2^n - 1 \ge 1500$$ $$\Leftrightarrow n \ge log_2 (1500 + 1)$$ $$\Rightarrow n \ge 10,55$$ Der Baum hat 11 Ebenen.

Zu c)
$$2^n - 1 \ge 10 000 000 000$$ $$\Leftrightarrow n \ge log_2 (10 000 000 000 + 1)$$ $$\Rightarrow n \ge 33,22$$ Der Baum hat 34 Ebenen.