lineare / rekursive datenstrukturen?

2 Antworten

Diese Bezeichnungen sind für mich im Zusammenhang mit Datenstrukturen etwas befremdlich.

Ich kenne sie eher im Zusammenhang mit Algorithmen, könnte mir aber vorstellen, dass man unter einer "rekursiven Datenstruktur" einen Baum und unter einer "linearen Datenstruktur" eine (verkettete) Liste verstehen könnte.

Bei einer verketteten Liste hat der Zugriff auf ein beliebiges Objekt eine Laufzeitkomplexität von O(n), das Einfügen und Entfernen eines Elements eine Laufzeitkomplexität von O(1).

Bei einer Baumstruktur hat der Zugriff auf ein beliebiges Objekt eine Laufzeitkompexität von O(log n), weil die Höhe des Baumes logarithmisch mit der Anzahl der Knoten wächst. Wie "teuer" Einfügen und Entfernen sind, hängt davon ab, ob der Baum sortiert ist. Bei einem unsortierten Baum sind, wie bei der verketteten Liste, beides Operationen mit einer Laufzeit von O(1). Wenn man allerdings beim Einfügen und Entfernen von Elementen anfangen muss, so genannte Baumrotationen durchzuführen, können die Operationen teurer werden. Dadurch wird dann aber widerum die mittlere Zugriffszeit auf die Elemente beschleunigt, weil die Höhe des Baums reduziert wird.

Listen Arrays etc. sind linear. Du durchläufst die ein Element nach dem nächsten (im schlimmsten Fall. Bäume zum Beispiel sind rekursiv, weil jeder Teilbaum selbst alle eigenschaften eines Baumes aufweist.

Deswegen sind viele Algorithmen beim Baum (wie die Suche) rekursiv gelöst.

Die Komplexität spielt da eher keine Rolle, falsche Baustelle sozusagen.

Ein Baum ist einfach eine rekursive Struktur, ebenso wie z.B. auch Butterflynetze eine rekursive Struktur aufweisen.

1
@KarlRanseierIII

Ergänzend:

Verkettete listen werden auch als rekursiv gesehen, weil eine Referenz auf den Typ vorliegt. Im Endeffekt ist also die um das erste Element reduzierte Liste wieder eine verkette Liste.

Ein Stack wiederum sollte nicht zwingend rekursiv sein, es sei denn, man allokiert die Elemente dynamisch und baut Ihn auf einer verketteten Liste auf.

1
@NoHumanBeing

Noch ein Versuch.

Okay.

Das heißt, es kann durchaus sinnvoll sein, iterative Algorithmen auf rekursiven Datenstrukturen operieren zu lassen oder umgekehrt rekursive Algorithmen auf linearen Datenstrukturen operieren zu lassen.

Wenn ich beispielsweise eine lineare Suche in einer verketteten Liste durchführe, dann wende ich also einen iterativen Algorithmus auf eine rekursive Datenstruktur an.

Umgekehrt, wenn ich den Merge-Sort-Algorithmus verwende, um ein Array zu sortieren, dann wende ich einen rekursiven Algorithmus auf eine lineare Datenstruktur an.

Wenn ich allerdings den Merge-Sort-Algorithmus verwende, um eine verkettete Liste zu sortieren (was ja auch leicht möglich ist), dann wende ich einen rekursiven Algorithmus auf eine rekursive Datenstruktur an, ebenso wenn ich beispielsweise eine Tiefensuche in einem Suchbaum durchführe. Gleichsam, wenn ich eine lineare Suche in einem Array durchführe, dann wende ich einen iterativen Algorithmus auf eine lineare Datenstruktur an.

Die beiden Konzepte sind also im Prinzip orthogonal zueinander. Eine rekursive Datenstruktur erfordert nicht, dass rekursive Algorithmen auf ihr operieren oder umgekehrt.

0
@NoHumanBeing

Japp, soweit scheint mir das alles schlüssig. Du kannst ja sogar den Mergesort iterativ umsetzen. Das erfordert zwar einen Heap mit entsprechender Komplexität und die Formulierung wird komplizierter, aber machbar ist das.

Ich kann natürlich auch einen Baum durch ein Vaterarray implementieren. Dann wäre es wohl nach der üblichen Definition eine lineare Datenstruktur (Array) ohne Selbstbezüge.

Davon unabhängig hat ein Baum natürlich immer auch ganz allgemein eine rekursive Struktur als Eigenschaft.

Es scheint, so wie ich es verstehe, wirklich nur auf die Datenstruktur, also den Typ, bezogen zu werden.

Aber das ist so ein wenig wie die ganzen Software Designpatterns. Das gros ergibt sich eigentlich ganz natürlich aus der Notwendigkeit heraus, auch schon bevor man anfing ihnen Namen zu geben und darüber zu schwadronieren ;-).

1

Eine rekursive Datenstruktur ist eine Datenstruktur, deren Definition auf sich selbst basiert. Eine lineare Datenstruktur hat keinen Bezug auf sich selbst.

Beispiel in C# für eine lineare Datenstruktur:

public struct Adresse
{
  public string Name;
  public string Straße;
  public string Hausnummer;
  public string Postleitzahl;
  public string Ort;
}

Beispiel in C# für eine rekursive Datenstruktur:

public struct Baumknoten
{
  public string Wert;
  public Baumknoten LinkerNachfolger;
  public Baumknoten RechterNachfolger;
}

Mit letzterer Struktur kannst Du eine Baumstruktur darstellen und musst dafür nur den Wurzelknoten als "Einstiegspunkt" kennen.

Mit ersterer Struktur kannst Du nur eine Adresse darstellen, brauchst also eine Liste, um mehrere "Datensätze" speichern zu können.


Was möchtest Du wissen?