Direkt zum Inhalt | Direkt zur Navigation
Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-411
URL: http://www.freidok.uni-freiburg.de/volltexte/41/
|
Relaxed-Balancing ist in den letzten Jahren zu einem häufig
verwendeten Konzept beim Entwurf von Suchbaum-Algorithmen für
Mehrbenutzerumgebungen geworden. Viele verschiedene
Relaxed-Balancing-Algorithmen sind vorgeschlagen worden, insbesondere
für Rot-Schwarz-Bäume und AVL-Bäume. Über die tatsächliche
Effizienz dieser Algorithmen auf einer Mehrprozessor-Maschine
lassen sich bislang jedoch noch keine Aussagen machen.
Mit Hilfe der Simulation einer Mehrprozessormaschine wird in dieser
Arbeit die Leistung von drei Relaxed-Balancing-Algorithmen für
Rot-Schwarz-Bäume experimentell untersucht und mit der des Standard
Rot-Schwarz-Baumes verglichen. Ferner wird ein effizienter Algorithmus
für Gruppen-Wörterbuchoperation in Rot-Schwarz-Bäumen vorgestellt und
analysiert.
| SWD-Schlagwörter: | Suchbaum , Paralleler Algorithmus , Simulation | |
| Freie Schlagwörter (englisch): | concurrent red-black tree , relaxed balancing , group updates | |
| CCS Klassifikation | E.1 | |
| Institut: | Institut für Informatik | |
| Fakultät: | Fakultät für Angewandte Wissenschaften (bis Sept. 2002) | |
| DDC-Sachgruppe: | Informatik | |
| Dokumentart: | Dissertation | |
| Erstgutachter: | Prof. Dr. Thomas Ottmann | |
| Sprache: | Deutsch | |
| Tag der mündlichen Prüfung: | 29.03.2000 | |
| Erstellungsjahr: | 2000 | |
| Publikationsdatum: | 14.04.2000 |