0 Daumen
483 Aufrufe
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."
Avatar von

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? 

2 Antworten

0 Daumen

Gegenbeispiel:

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

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

Avatar von 287 k 🚀
0 Daumen

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 fmax(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#

Bild Mathematik

ergibt x=12996

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

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community