---

Geschrieben von königsbergerklopse am 30.04.2021 um 11:47:

  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?

---

Geschrieben von as_string am 06.05.2021 um 10:18:

 

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

---

Geschrieben von Tomass am 27.12.2022 um 11:35:

 

Danke für die Erklärung