Shalom

Binäre Suchbäume erreichen für insert, delete und locate meistens logarithmische Zeit. Im schlimmsten Fall können alle Operationen jedoch lineare Zeit brauchen, das passiert, wenn der Baum keine logarithmische, sondern lineare Tiefe hat. Da in jeder der drei Operationen ein Pfad durch den Baum traversiert wird, erhalten wir die lineare Laufzeit. Wir wollen allerdings immer logarithmischer Laufzeit. Das erreichen wir, durch Bäume die immer balanciert sind – ein Beispiel dafür sind (a, b)-Bäume....

Unsere Reise durch die Algorithmik beginnt in der Regel mit Listen, für dessen Operationen man eine \(\mathcal{O}(n)\) worst-case Laufzeit beweist. Mit dem Verlangen die Operationen zu beschleunigen, betrachtet man Prioritätswarteschlangen, in Form von (a, b)-Bäumen, wodurch wir die Laufzeit auf \(\mathcal{O}(\log n)\) reduzieren. Was aber, wenn wir in einer Echtzeit-A nwendung \(\mathcal{O} (1)\) Laufzeit benötigen? Können wir das geschickt umsetzen? Ja, mittels Hashing. Eine Märchenwelt Wo fangen wir an, wenn wir konstante Laufzeit erzielen wollen?...