Dynamische Datenstrukturen

1.) Listen

Allgemeines
   Eine verkettete Liste ist eine Menge von Elementen, die wie in einem Feld sequentiell organisiert sind. Bei Verwendung
   von Listen ist genau zu überlegen, welche Art man verwendet. Wenn nicht unbedingt notwendig, dann sollte man auf die
   doppelt bzw. zyklisch verketteten Listen verzichten, da diese mit mehr Aufwand verbunden sind.

   + es muß keine maximale Größe angegeben werden (anders als beim Array)
   + hohe Flexibilität, da Elemente recht leicht umgeordnet werden können
   + relativ einfache Operationen (Einfügen, Löschen). Bei Arrays müßte das ganze Feld verschoben werden.

Verschiedene Arten von Listen

* einfach verkettete Listen

Jedes Element der einfach verketteten Liste besteht aus einem Datenteil und
aus einem Zeiger auf das nächste Element. Deshalb kennt jedes Element nur seinen
Nachfolger. Es wird ein Zeiger (panker) auf das erste Element der Liste gespeichert, um
die einfach verkettete Liste durchlaufen zu können. Jenes Element das (noch) keinen
Nachfolger hat, hat als Wert im next-Zeiger NULL.

|-----|--| |-----|--| |-----|--|
panker +--> | 1 | +----->| 2 | +----->| 3 | +-----> NULL
|-----|--| |-----|--| |-----|--|

Anwendung der einfach verketteten Listen z. B. Stack (LIFO)
Ein Beispiel in C++:

class STACK *anf,*hilf;
public:
STACK ()
~STACK ()

void push(int i)


int pop ()



void main()

* doppelt verkettete Listen Jedes Element der doppelt verketteten Liste besteht aus einem Datenteil, aus einem
Zeiger auf das nächste Element und einem Zeiger auf das davorliegende Element.
Es wird ein Zeiger (panker) auf das erste Element der Liste gespeichert.
Damit kann man durch die Liste prev- und rückwärtsnavigieren.
Das erste Element der Liste hat als prev-Zeiger NULL.
Das letzte Element der Liste hat als next-Zeiger NULL.
Anwendung: Schlange oder auch Queue genannt

|--|-----|--| |--|-----|--| |--|-----|--|
panker +--->| | | +----->| | | +----->| | | +-----> NULL
| | 1 | | | | 2 | | | | 3 | |
NULL <-----+ | | |<-----+ | | |<-----+ | | |
|--|-----|--| |--|-----|--| |--|-----|--|

Bei der Schlange wird neben dem Zeiger auf das erste Element (panker oder head)
auch ein Zeiger auf das letzte Element (tail) gespeichert.

|--|-----|--| |--|-----|--| |--|-----|--|
head +--->| | | +----->| | | +----->| | | +-----> NULL
| | 1 | | | | 2 | | | | 3 | |
NULL <-----+ | | |<-----+ | | |<-----+ | | |<---+ tail
|--|-----|--| |--|-----|--| |--|-----|--|

- Schlange wächst:
Bei neuer Eintragung wandert der Tail-Zeiger
vom Head-Zeiger weg.

- Head- und Tail-Zeiger sind gleich,
wenn nur ein Element vorhanden ist

- die Schlange ist LEER,
wenn beide Zeiger auf NULL zeigen

* zyklisch verkettete Listen Bei einfach verketteten Listen:    Im letzten Element der Liste wird statt einem next-Zeiger auf NULL ein Zeiger auf
   das erste Element gespeichert.

/-------- ----- ------ ----- ----- -----
| |
--->|-----|--| |-----|--| |-----|--| |
| 1 | +----->| 2 | +----->| 3 | +-----/
panker +--->|-----|--| |-----|--| |-----|--|

Bei doppelt verketteten Listen:    Im letzten Element der Liste wird statt einem next-Zeiger auf NULL ein Zeiger auf das erste Element gespeichert.
   Im ersten Element der Liste wird statt einem prev-Zeiger auf NULL ein Zeiger auf das letzte Element gespeichert.

/-------- ----- ------ ----- ----- --------------
| |
| |--|-----|--| |--|-----|--| |--|-----|--| |
--->| | | +----->| | | +----->| | | +-----/
| | | | | | | | | | | |
panker +--->| | 1 | | | | 2 | | | | 3 | |
| | | | | | | | | | | |
/-----+ | | |<-----+ | | |<-----+ | | |<---
| |--|-----|--| |--|-----|--| |--|-----|--| |
| |
-------- ----- ------ ----- ----- --------------/

2.) Bäume

  * jeder Baum besteht aus Knoten und Kanten
  * jeder Knoten stellt einen Datensatz dar
  * von jedem Knoten gehen ein oder mehrere Kanten aus, die zu anderen Knoten oder NULL führen
  * jeder Knoten (außer die sogenannte Wurzel) hat genau einen Vorgänger.
  * alle Knoten ohne Nachfolger heißen Endknoten oder Blätter.
  * alle anderen Knoten (außer die Wurzel) heißen innere Knoten.
  * Die Anzahl der Kanten zwischen einem Knoten und der Wurzel nennt man 'Niveau des Knoten'
  * Das größte Niveaus des Baumes nennt man Tiefe oder Höhe des Baumes.

Der Binärbaum

Beim Binärbaum hat jeder Knoten maximal 2 Nachfolger.
Beim geordneten (sortierten) Binärbäum ist jeder Schlüssel des linken Teilbaums kleiner als der
eigene Schlüssel, jeder Schlüssel des rechten Teilbaumes ist größer

linker Knoten: L
rechter Knoten: R


/--- RR
/--- R -|
| --- RL
Wurzel -|
| /--- LR
--- L -| /--- LLR
--- LL -|
--- LLL

Der AVL-Baum

* Deim AVL-Baum unterscheidet sich die Tiefe des linken Teilbaumes von der der rechten um maximal 1
* Bei jedem Knoten wird die Balance mitgespeichert. (Tiefe des rechten minus Tiefe des linken)
  Blätter haben deshalb immer Varianz 0 * Der AVL-Baum kann nicht degenerieren

  + weniger Suchaufwand
  - für jeden Knoten muß die Balance mitgespeichert werden   - jede Einfüge- und Löschoperation muß Balance kontrollieren => Rechts-, Links-, od. Rechts-Links-Rotation.

Beispiel:(Zahlen in Klammer stellen Balance dar)

Alter Baum:

/--- 5 (0)
|

|
--- 3 (-1) -
|
---2 (0)

Einfügen von '1':

/--- 5 (0)
|

|
--- 3 (-2) -
|
---2 (-1) -
|
---1 (0)

Nach Einfügen ist Rotation notwendig.
Ergebnis nach Rechtsrotation.

/--- 5 (0)
|
/--- 2 (0)
| |
--- 3 (0) -|
|
--- 1 (0)

M-Wege-Suchbaum

Jeder Knoten hat
   - maximal m Nachfolger
   - und maximal m-1 Datenelemente
   - Die Knoten im Daten sind aufsteigend sortiert
   - Jedes Datenelement kann einen linken und einen rechten Nachfolger haben, der rechte
     Nachfolger eines Elements entspricht dem linken Nachfolger des nächsten Datenelements.
   - Ein Binärbaum ist ein M-Wege-Suchbaum mit m=2

B(ayer)-Baum

Der B-Baum ist ein spezieller M-Wege-Suchbaum mit zusätzlichen Einschränkungen.
Ein B-Baum der Ordnung k muß folgende Kriterien erfüllen:
   - jeder Knoten hat maximal (2*k)-1 Info-Komponenten und (2*k)+1 Nachfolger
   - jeder Knoten (außer Wurzel) hat mindestens k Infokomponenten    - jeder Knoten (außer Wurzel und Blätter) hat mindestens n+1 Nachfolger (Söhne),
     wobei n die Anzahl der Infokomponenten ist.
   - Alle Blätter haben das selbe Niveau (Anzahl Kanten bis zur Wurzel).

/----- /---|-----|---|-----|---|-----|---|-----|---
+--------->| | 2 | | 3 | | 5 | | 9 | |
|-----| ---|-----|---|-----|---|-----|---|-----|---/
| |
| 10 |
| |
/---|-----|---|-----|---|-----|---|-----|---
+--------->| | 12 | | 17 | | | | | |
|-----| ---|-----|---|-----|---|-----|---|-----|---/
| |
| 20 |
| |
|-----| /---|-----|---|-----|---|-----|---|-----|---
+--------->| | 25 | | 27 | | 28 | | | |
|-----| ---|-----|---|-----|---|-----|---|-----|---/
| |
| 30 |
| |
|-----| /---|-----|---|-----|---|-----|---|-----|---
+--------->| | 35 | | 37 | | 38 | | 40 | |
|-----| ---|-----|---|-----|---|-----|---|-----|---/
| |
| |
| |

| |


Da es sich um einen Suchbaum (sortierte Schlüsselbäume) handelt