Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Greedy Aufwärts: Hauptseite Algorithmen Vorherige Seite: Kruskal zur Erstellung des   Inhalt

Unterabschnitte

Speichermöglichkeiten von Datenmengen mit dynamischer Größe

Hashing

Beim Hashing wird mit Hilfe einer surjektiven Funktion das Universum auf einen kleineren Speicher abgebildet.

Verschiedene Hashfunktionen

  • Modulofunktion: $x\,\,mod\,\,y$ wobei $y$ die Größe des Hashspeichers ist
  • Mittelquadrat: Die Speicheradresse wird quadriert. Danach werden aus der quadrierten Zahl in der Mitte Ziffern herausgenommen: Beispiel: $128^{2}=16\underline{38}4\Rightarrow 38$
  • Multiplikationsmethode: Die Zahl wird mit einer irrationalen Zahl zwischen $]0,1[$ multipliziert. Danach erhalten wir eine Orignial+d-bittige Zahl. Die letzten d Bits werden als Speicheradresse für den Hash verwendet.

Offenes Hashing mit Kollisionslisten

Wenn es Kollisionen gibt, dann werden an den Hashspeicher Listen angehängt, in denen Elemente gespeichert werden, die nicht mehr in den normalen Speicher passten, weil diese schon besetzt war.

Geschlossenes Hashing mit offener Adressierung

Beim geschlossenen Hashing mit offener Adressierung wird bei belegten Hashspeicherplätzen mittels anderer Hashfunktionen auf andere Speicherplätze ausgewichen.

Dynamisches Hashing

Schon einmal berechnete Ergebnisse von Teilproblemen eines großen Problems werden gespeichert. Diese können aber problemlos gelöscht werden, wenn ein neuer Wert die Hashspeicherzelle überschreibt, da sie neu berechnet werden können.

Balancierte Bäume

Bei den Bäumen ist jeweils das Verhalten beim Einfügen und Entfernen wichtig.

Höhe von Bäumen

leerer Teilbaum: -1
ein Knoten: 0
  usw.

Suchbäume

Bei einem INORDER-Durchlauf eines Suchbaumes sind alle Elemente sortiert.

AVL

  • Wenn $bal(v)=-2$ und $bal(right(v))\in\{-1,0\}$ einfache Rotation nach links
  • Wenn $bal(v)=-2$ und $bal(right(v))=1$ Doppelrotation rechts-links
  • Wenn $bal(v)=2$ und $bal(left(v))\in\{1,0\}$ einfache Rotation nach rechts
  • Wenn $bal(v)=2$ und $bal(left(v))=-1$ Doppelrotation links-recht
Die Höhe eines AVL-Baumes ist $O(\log n)$. Schlechteste AVL-Bäume sind Fibonaccibäume. Bei diesen steht die Fibonaccizahl $F_{n+1}$ in der Wurzel.

Blatt

In den inneren Knoten werden nur die Schlüssel, die zur Suche benötigt werden, gespeichert. Die eigentlichen Informationen stehen in den Blättern. Dabei sind die Blätter zum besseren sequentiellen Auslesen untereinander doppelt verknüpft.

B-Bäume

B-Bäume sind Speicherstrukturen für den externen Speicher.
Wenn ein B-Baum die Ordnung $m$ hat, dann bedeutet das, daß jeder Knoten mindestens $m$ aber höchstens $m\cdot 2$ Schlüsselwerte mit den dazugehörigen Daten beinhaltet. (Davon ist die Wurzel ausgenommen)
B-Bäume haben folgende Eigenschaften:
  • Jeder Knoten, außer die Wurzel hat mindestens $m$ und höchstens $2m$ Schlüsselwerte, wobei $m$ die Ordnung ist.
  • Die Wurzel hat höchstens $2m$ Schlüsselwerte. Nach unten gibt es jedoch keine Grenze.
  • Jeder Knoten mit $k$ Schlüsselwerten hat $k+1$ Söhne, wenn dieser Knoten nicht ein Blatt ist.
  • Alle Blätter haben dieselbe Tiefe bezüglich des Wurzelknotens.
Wir fügen Schlüssel zu dem Baum hinzu, indem wir sie in dem geeigneten Blattknoten einfügen. Wird dieser zu groß (OVERFLOW), müssen wir ihn splitten. Hierbei wandert der mittlere Wert dieses Knoten in den darüber liegenden Vater und aus dem einen Knoten werden zwei gemacht.
Beim Löschen kann es passieren, daß ein Knoten zu klein wird (UNDERFLOW). Wenn es möglich ist, borgen wir uns Schlüsselwerte von einem benachbarten Bruderknoten. Hierbei geht ein Wert aus dem Bruder in den gemeinsamen Vaterknoten, während ein Schlüsselwert aus dem Vaterknoten in den Knoten mit dem UNDERFLOW kommt. Geht dies nicht, so wenden wir Konkatenation an und zwei Bruderknoten werden zu einem Knoten zusammengefügt. Dieser Knoten nimmt des weiteren noch den Wert aus dem Vaterknoten auf, der nun auf keinen Sohn mehr zeigt.
Die Laufzeit von Suchen, Einfügen und Löschen auf B-Bäumen ist

\begin{displaymath}O(H\uml {o}he(T))=O(\log_{(m+1)}(N))\end{displaymath}

wobei $m$ die Ordnung und $N$ die Schlüsselanzahl.
next up previous contents
Nächste Seite: Greedy Aufwärts: Hauptseite Algorithmen Vorherige Seite: Kruskal zur Erstellung des   Inhalt