Höhe eines Binärbaums mindestens Wurzel n - 100?

Question

Am Bartresen einer Kneipe in der Pontstraße spricht Sie ein Unbekannter an. Er behauptet: Die Höhe jedes binären Suchbaums, der n Schlüssel enthält, ist mindestens √n - 100. Finden Sie einen Beweis oder ein Gegenbeispiel für diese Behauptung.

Die Antwort sollen wir sehr knapp halten, so dass sie "auf einen Bierdeckel passt."

Comments

In der Aufgabenstellung habe ich fälschlicherweise + geschrieben statt -.

---

Höhe jedes binären Suchbaums, der n Schlüssel enthält, ist mindestens √ ( n - 100 ) . ?

EDIT: Wie weit geht die Wurzel? 

Das gäbe ja Suchbäume mit imaginärer Höhe oder negativer Höhe (?) 

Was meinst du mit Schlüssel? 

Answer 1

Gegenbeispiel:

vollständiger Binärbaum mit 1023 Einträgen hat Höhe 10 .

wurzel ( 1023 - 100 ) ungefähr 30,4 .

Answer 2

Bei der Wurzel fehlt die Klammer! Ich unterstelle mal: hinter dem n geht sie zu:

laut https://de.wikipedia.org/wiki/Bin%C3%A4rer_Suchbaum

ist f_max(x)=ceil(log(x+1)/log(2))

Behauptung: sqrt(x)-100 < ceil(log(x+1)/log(2))

Test auf Gleichheit:

ceil(log(x+1)/log(2))=sqrt(x)-100

http://www.gerdlamprecht.de/Roemisch_JAVA.htm#ceil(log(x+1)/log(2))@Ni=0;@Na=i+12900;@Bi]=@Qa)-100;@Ci]=Fx(a);@Ni%3E100@N0@N0@N#

ergibt x=12996

also stimmt die Bahauptung für alle x> 12996 NICHT