Gleichgewichtsverteilungen

Inhaltlich unvernderte Neuauflage. Binre Suchbume stellen eine der meistverwendeten nicht-linearen Datenstrukturen in der Informatik dar. Ihre Vorteile liegen vor allem in ihrer einfachen und intuitiven Darstellung und in den effizienten Algorithmen zum Suchen, Einfgen und Lschen von Elementen. Zur Analyse der Effizienz unterschiedlicher Algorithmen zur Manipulation von dynamischen Datenstrukturen wird blicherweise auf die Verwendung von zuflligen Einfgungen und zuflligen Lschungen zurckgegriffen. Bei der Anwendung dieser "Randomness" auf binre Suchbume ist den Autoren seit Anfang der sechziger Jahre jedoch eine Reihe von Irrungen unterlaufen. Die gegenstndliche Arbeit leistet daher einen Beitrag zur Frage, ob in den betrachteten Werken weiterhin fehlerhafte Annahmen getroffen wurden oder ob mittlerweile von einem Ende dieser "Geschichte der Irrungen" ausgegangen werden kann.