Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Informatik in der Schule » Maximale Suchlaufzeit im Binärbaum? » Antwort erstellen » Hallo Gast [Anmelden|Registrieren]

Antwort erstellen
Benutzername: (du bist nicht eingeloggt!)
Thema:
Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33
smileWinkDaumen hoch
verwirrtAugenzwinkerngeschockt
Mit ZungeGottunglücklich
Forum Kloppebösegroßes Grinsen
TanzentraurigProst
TeufelSpamWillkommen
LehrerLOL HammerZunge raus
Hilfe 
aktuellen Tag schließen
alle Tags schließen
fettgedruckter Textkursiver Textunterstrichener Text zentrierter Text Hyperlink einfügenE-Mail-Adresse einfügenBild einfügen Zitat einfügenListe erstellen CODE einfügenPHP CODE farbig hervorheben
Spamschutz:
Text aus Bild eingeben
Spamschutz

Die letzten 2 Beiträge
as_string

Du hast pro Ebene nur eine Vergleichs-Operation. Wieso solltest Du beide Kinder überprüfen müssen?
Andererseits: das mit log(n) funktioniert ja nur, wenn der Baum balanciert ist. Ich weiß nicht, ob man davon ausgehen darf, weil da was von "maximal" steht...

Gruß
Marco
königsbergerklopse Maximale Suchlaufzeit im Binärbaum?

Meine Frage:
Hallo, ich habe eine Frage zur Laufzeit bei Binärbäumen.

Gesetzt, man hat 20 000 DVDs in einem solchen Baume gespeichert und pro untersuchtem Baumelement ist eine ns nötig.

Wie lange dauert dann die Suche maximal?

Vielen Dank
(Aufgabe: Informatik Abitur Bayern 2013 Teil 1 Aufgabe 3c) )

Meine Ideen:
Mein Ansatz:

2^n -1 = 20 000

==> n = log2(20 001)=14,29 ==> 15 Ebenen nötig

Beträgt die maximale Suchlaufzeit damit dann 15ns? Oder länger, weil ja jeweils beide Nachfolger "untersucht" werden müssen?