(a,b)–Bäume
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....