<!doctype html public '-//w3c//dtd html 4.0 transitional//en'>
Definition: Menge von sequentiell organisierten Elementen
VT: variable Größe
hohe Flexibilität
Einfügen u. Löschen sehr
einfach
NT: nur sequentielle Zugriffe möglich
Verschiedene Arten von Listen
einfach verkettet
Die einzelnen Elemente nur in eine Richtung verkettet - jedes Element kennt seinen Nachfolger, aber nicht seinen Vorgänger.
doppelt verkettet
Die einzelnen Elemente sind in beide Richtungen verkettet - jedes Element kennt seinen Nachfolger und seinen Vorgänger.
zyklisch verkettet
Wie
doppelt verkettete Liste, nur kennt das erste Element das letzte als seinen
Vorgänger und das letzte Element das erste als seinen Nachfolger.
Ein Baum besteht aus Knoten und Kanten
Jeder Knoten stellt einen Datensatz dar
Von jedem Knoten gehen eine oder mehrere Kanten aus, die entweder auf andere Knoten, oder auf NULL zeigen
Es gibt genau einen Knoten ohne Vorgänger, dieser heißt Wurzel
Die Anzahl der Knoten zwischen einem Knoten und der Wurzel nennt man Niveau des Knotens
Das größte vorkommende Niveau in einem Baum nennt man die Tiefe des Baumes
Verschiedene Arten von Bäumen
Binärbaum
Jeder Knoten hat maximal 2 Nachfolger
2 Arten:
geordnete (sortierte) Binärbaume: Die Daten sind nach einem Schlüsselbegriff sortiert. Für jeden Knoten gilt, daß jeder Schlüssel in seinem linken Teilbaum kleiner ist als sein eigener und alle Schlüssel im rechten Teilbaum größer sind als sein eigener Schlüssel.
voller Binärbaum: Jede ebene ist völlig mit inneren Knoten ausgefüllt.
VT:
schnelles Suchen
für rekursive
Verarbeitung geeignet
Einfügen und
löschen relativ einfach
NT: Wenn oft eingefügt und gelöscht wird besteht Gefahr des degenerierens zu einer Liste
Adelson-Velski-Landis - Baum
Für jeden Knoten gilt: Die Tiefe des linken Teilbaumes unterscheidet sich von der Tiefe des rechten Teilbaumes maximal um 1.
Balance = Tiefe des rechten Teilbaumes - Tiefe des linken Teilbaumes (zuläßige Werte: -1,0,1)
VT:
geringerer Suchaufwand, da dieser Baum nicht degenerieren kann
NT: für jeden Knoten Balance mitspeichern
Nach jeder Einfüge- u.
Löschoperation muß Balance wieder stimmen, dies geschieht mit Hilfe von
Rechts-, Links- od.
Rechts-Links-Rotation.
Bayer-Baum
Ein spezieller M-Wege-Suchbaum
Jeder Knoten hat maximal m Nachfolger und maximal m-1 Datenelemente
Die Daten im Knoten sind aufsteigend sortiert
Jedes Element kann einen linken und einen rechten Nachfolger haben, der rechte Nachfolger eines Elements entspricht dem linken Nachfolger des nächsten Datenelements.
Es handelt sich um einen Verallgemeinerung des Binärbaumes, der ein M-Wege-Suchbaum mit m=2 ist
mit zusätzlichen Einschränkungen:
Jeder Knoten enthält maximal 2*k Info - Komponenten und 2*k+1 Nachfolger
Jeder Knoten (außer der Wurzel) hat mindestens k-Info-Komponenten
Jeder Knoten (außer Wurzel und Blätter) hat mindestens n+1 Nachfolger, wobei n die Anzahl der Info-Komponenten ist
Alle Blätter haben das selbe Niveau
VT:
geringe Tiefe
Häufigkeit der
Navigation verringert sich durch große Seiten
Beispiel: k = 2
Definition: Objekt, das andere Objekte 'enthält'
Container - Arten werden durch mehrere 'Koordinaten' festgelegt:
1. durch die Zugriffsart aus 'logischer Sicht':
STACK
LIFO - Prinzip
QUEUE
FIFA - Prinzip
BAG
Irgendwie gespeichert
2. durch ihre 'physikalische' Realisierung:
A) Array, Liste, Baum
B) Element selber gespeichert
Zeiger auf Kopie der Elemente:
mittels Templates universell verwendbare Klasse
Zeiger auf ursprüngliches Element:
wird
häufig in C verwendet (mit void-Zeigern)
VT:
auch unterschiedliche Objekte pro Container
NT:
sehr fehleranfällig
Haupt | Fügen Sie Referat | Kontakt | Impressum | Nutzungsbedingungen
