Next:
Grundlegende Operationen
Up:
Inhalt
Previous:
Transformation des Definitions- bzw.
Höhere Datenstrukturen
Grundlegende Operationen
Suchbäume, balancierte Bäume
Höhenbalancierte Bäume
(a,b)-Bäume
Rot-Schwarz-Bäume
Binäre Suchbäume
Natürliche binäre Suchbäume
Höhenbalancierte binäre Suchbäume (AVL-Bäume)
Hashing
Grundlagen
Chainingverfahren
Hashing mit offener Adressierung
Universelles Hashing
Perfektes Hashing
Priority Queues
Binomial Queues (binomial heaps)
Fibonacci-Heaps
Die Datenstruktur
Amortisierte Kostenanalyse für Fibonacci-Heaps
Sich selbst organisierende Datenstrukturen
Motivation
Sich selbst organisierende lineare Listen
Sich selbst organisierende Binary Keys
Splay-Trees als Suchbäume
Einleitung
Die Splaying-Operation
Amortisierte Kostenanalyse der Splay-Operation
Wörterbuchoperationen in Splay-Trees
Weitere Arten von Datenstrukturen
Radix-basierte Priority-Queue
Buckets
1-Level-Backets
2-Level-Buckets
k
-Level-Buckets
Von-Ende-Boas-PQ
Radix-Heaps
Union-Find-Datenstrukturen
Motivation
Union-Find-Datenstruktur
Intrees
Gewichtete Union (erste Verbesserung)
Pfad-Kompression mit gewichteten Union (zweite Verbesserung)
Erweiterung
Abbas-Bardia Kabiri-Jarghouyeh
3/3/1999