Logo des Repositoriums
 

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

Kurzanzeige
dc.contributor.authorPanny, Wolfgang
dc.contributor.editorGeyer-Schulz, Andreas
dc.contributor.editorTaudes, Alfred
dc.date.accessioned2019-11-14T11:01:27Z
dc.date.available2019-11-14T11:01:27Z
dc.date.issued2003
dc.description.abstractDie ü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.de
dc.identifier.isbn3-88579-362-8
dc.identifier.pissn1617-5468
dc.identifier.urihttps://dl.gi.de/handle/20.500.12116/29828
dc.language.isode
dc.publisherGesellschaft für Informatik e.V.
dc.relation.ispartofInformationswirtschaft: Ein Sektor mit Zukunft
dc.relation.ispartofseriesLecture Notes in Informatics (LNI) - Proceedings, Volume P-33
dc.titleLöschungen in zufälligen binären Suchbäumen – Eine Geschichte der Irrungende
dc.typeText/Conference Paper
gi.citation.endPage88
gi.citation.publisherPlaceBonn
gi.citation.startPage75
gi.conference.date4.-5. September 2003
gi.conference.locationWien, Österreich
gi.conference.sessiontitleRegular Research Papers

Dateien

Originalbündel
1 - 1 von 1
Vorschaubild
Name:
GI-Proceedings.33-5.pdf
Größe:
124.5 KB
Format:
Adobe Portable Document Format
Herunterladen

Sammlungen

P033 - Informationswirtschaft: Ein Sektor mit Zukunft