Löschungen in zufälligen binären Suchbäumen – Eine Geschichte der Irrungen

Abstract

Die üblichen Annahmen für die average-case Analyse von binären Such- bäumen (BSB) sind zufällige Einfügungen (random insertions) und zufällige Löschungen (random deletions). In einem durch zufällige Einfügungen aufgebauten BSB haben die Zugriffsoperationen eine erwartete Zeitkomplexität von O(log n) und schon die ersten Publikationen über BSB enthalten wesentliche analytische Ergebnisse für solche 'random' BSB. Wenn es allerdings um zufällige Löschungen und um ihre Interaktion mit zufälligen Einfügungen geht, scheint die Analyse um einiges komplizierter zu werden. Das kann man jedenfalls den einschlägigen Publikationen seit 1962 entnehmen, die es berechtigt erscheinen lassen, in diesem Zusammenhang von einer 'Geschichte der Irrungen' zu sprechen. Dieser Beitrag geht etwas näher auf diese Geschichte ein.