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

Informatiker Board » Themengebiete » Informatik in der Schule » Maximale Suchlaufzeit im Binärbaum? » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Maximale Suchlaufzeit im Binärbaum?
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
königsbergerklopse
unregistriert
Maximale Suchlaufzeit im Binärbaum? Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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?
30.04.2021 11:47
as_string as_string ist männlich
Haudegen


Dabei seit: 06.11.2013
Beiträge: 611
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
06.05.2021 10:18 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Informatik in der Schule » Maximale Suchlaufzeit im Binärbaum?