cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

Data Structures | Basics:

anchored to [[111.00_anchor]]

Overview:

Wenn wir Algorithmen betrachten brauchen wir für diverse Operationen bestimmte Datenstrukturen. Folgend beschreiben diese eine Möglichkeit Daten zu speichern. Dabei haben sie ihre eigenen Vor/Nachteile, können unterschiedliche Daten oder Mengen von diesen Speichern und brauchen unterschiedlich viel Speicherplatz.

Wir werden hier erkennen, dass es diverse Datenstrukturen gibt, die sich in unterschiedlichen Szenarien gut anwenden lassen.

Wir beziehen uns hier nicht auf grundlegende Strukturen, wie Integer, Strings etc., sondern um solche, die mehrere Daten akkumulieren oder zusammenhalten können.

Arrays:

Arrays sind mit die einfachsten Datenstrukturen. Sie haben folgende Eigenschaften: #card

[!Example] Eigenschaften Array:

• sie können Objekte des selben Types $n$-mal speichern. Dabei ist $n$ die Längedes Arrays und die Objekte sind geordnet
• Array[0] ist das erste Element, Array[1] das zweite … ^1704708664188

Kosten von Operationen im Array? #card Operationen, wie lesen und schreiben kosten jeweils $\mathcal{O}(1)$ -> denn die Adresse ist im Speicher schon bekannt ^1704708664194

Nachteil eines Arrays: #card Ein Array ist in seiner Größe Fest und somit muss man einen neuen Erstellen, wenn man mehr Platz brauch. Hierbei kommt auch das zweite Problem zu tragen: Der Speicher muss komplett belegt werden für einen Array der Länge $n$. ^1704708664199

Listen:

Listen sind in ihrere Idee gleich einem Array, aber haben einige andere Umsetzungen: #card

• sie haben keine feste Länge, denn jedes Element zeigt immer auf das nächste, wodurch dynamisch erweitert werden kann.
• sie können auch nur einen Datentyp in sich Speichern.
• Ein Element der Liste besteht folgend aus:
  • Inhalt des Elements, Zeiger auf das nächste Element, Zeiger auf den Anfang der Liste.
  • doppelt verketteten Listen: gibt es immernoch einen Zeiger, der auf das vorherige Element verweist. ^1704708664205

[!Tip] Zeiger bei Listen und Arrays: Zeiger sind, wie in vielen Sprachen, Referenzen auf einen Inhalt. Dabei ist diese Referenz meist eine Speicheradresse, da diese eindeutig angibt, wo sich etwas befindet. Zeiger sind meisten so aufgebaut, dass sie auf die erste Adresse eines Elementes zeigen / verweisen. Also bei einem Array wird somit der Anfang desse referenziert.

Operationen in Listen, wenn sie doppelt verkettet sind:

• das Einfügen eines Element $x$ nach einem gegebenen Element $e$ kostet bei doppelt verketteten Listen :: $\mathcal{O}(1)$, ( dafür muss man aber schon bei $e$ sein, sonst erst bis zu diesem Punkt durchlaufen!) ^1704708664210

• das Löschen eines Elementes bei doppelt verketteten Listen ist mit :: $\mathcal{O}(1)$ definiert ^1704708664216

• Das Suchen eines Element $k$ in doppelt verketteten Listen brauch folgend :: $\mathcal{O}(n)$ weswegen? Weil wir nicht wissen, wo sich ein Element befindet und wir so im schlimmsten Fall die ganze Liste traversieren müssen. ^1704708664221

• Das Löschen einer Teilliste ( also einer Teilmenge dieser) brauch, wenn wir wissen, wo das erste und letzte Element ist :: $\mathcal{O}(1)$ ^1704708664226

• Das Einfügen einer zweiten Liste nach einem Element $e$ in der ersten benötigt :: $\mathcal{O}(1)$ -> wir können einfach den Zeiger neu setzen und fertig ^1704708664231

Mögliche Implementationen einer Liste: #card Wir können Listen verschieden konstruieren und ihnen so unterschiedliche Fähigkeiten geben:

• Head als Anfang markieren und Tail als Ende
• in sich geschlossene Liste, die am Ende wieder beim Anfang anfängt ^1704708664237

[!Info] Nachteile von einfachen Listen ( einmal verkettet): #card Das Löschen von Elementen ist aufwendiger, da kein previous-Zeiger vorhanden ist. Dafür ist der Speicherplatz geringer ^1704708664243

Trees | Grundlegende Definition:

built from top to bottom, root is at uppermost layer

![[Pasted image 20221024152605.png]]

In einem Baum versuchen wir Knoten mit anderen Knoten zu verbinden, um so eine Struktur aufbauen zu können, die in ihrere Tiefe meist sehr breit wird. Es gibt in einem Baum Branches(Zweige) und Knots(Knoten).

Der Wichtigste Knoten ist hierbei root, welcher als Kern / höchster Ebene des Baumes gilt. Ein jeder Knoten, kann weitere Zweige bzw Blätter aufweisen, welche dann von dem oberen Knoten, wo sie entspringen, abhängig sind. Solche Blätter sind dann folgend als Nachkömmlinge(Descendants) benannt.

[!Definition] Tiefe eines Knotens $v$ #card Sei hierfür $v$ ein Knoten in einem Baum $T$: Wir definieren die Tiefe von $v$, also $Tiefe(v)$ damit, dass sie angibt, auf welcher Schicht sich $v$ befindet. Im obigen Beispiel ist die Tiefe von $a$ dann etwa $1$, da dieser sich dieser in der ersten Schicht befindet.

Allgemein gilt: $Tiefe(T)=\max \{Tiefe(v),v\in T\}$ ^1704708664248

[!Definition] Höhe eines Knoten $v$ #card Auch hier sei $v$ ein Knoten im Baum $T$: Wir definieren die Höhe eines Knotens, damit, dass $H\ddot{o}he(v)$ der maximalen Tiefe entspricht, die von diesem Knoten aus erzielt werden kann. Betrachten wir folgendes Beispiel: ![[Pasted image 20231029153504.png]] Dann ist $H\ddot{o}he(w)=2,H\ddot{o}he(u)=3,H\ddot{o}he(x)=0$

Allgemein gilt: $H\ddot{o}he(T)=\max \{H\ddot{o}he(v),v\in T\}$ (Das sollte eigentlich immer die Wurzel sein, weil man von auf alle Blätter zugreifen kann/muss) ^1704708664253

Binäre Bäume:

Sind eine Sonderform von Bäumen, denn sie haben folgende Definition: #card

[!Definition] Binärbaum: Jeder Knoten hat höchstens 2 Kinder. Dabei sind sie links und rechts Wir wollen immer zuerst die linke Hälfte füllen, bevor danach die rechte gefüllt wird. ^1704708664259

Vollständige Binärbäume:

[!Definition] Vollstander Binärbaum: Wir sprechen hier von einem complete / vollständigen Binärbaum, wenn folgend gilt #card alle Level außer des untersten sind gefüllt. Bei diesem stehen alle Knoten dann möglichst links. ![[Pasted image 20231029154150.png]]

^1704708664264

Es folgt hieraus ein Lemma:

[!Example] Lemma Vollständiger Binärbaum: Ein vollständiger Baum hat folgend die Höhe/Tiefe beschrieben mit:$$\lceil {\log }_2(n+1)-1\rceil \in \Theta (\log n)$$

Um zu zeigen, dass diese Aussage stimmt, kann man den Beweis für volle Bäume betrachten. Was hier dann noch gilt: Wir können nicht ganz sagen, wie viele Knoten in der untersten Stufe fehlen werden, weswegen wir folgend runden: $$h=\lceil {\log }_2(n+1)\rceil -1$$

Volle Binärbaume:

[!Definition] Volle / full Binärbäume Mit full / vollen Binärbäumen meinen wir jetzt einen Binärbaum, der folgende Eigenschaft erfüllt: #card Alle Level sind gefüllt, auch das unterste Level muss komplett gefüllt sein. Wir meinen damit also einen Baum, der Komplett belegt ist. ^1704708664270

Auch hier lässt sich ein Lemma erzeugen:

[!Example] Lemma Voller Binärbaum: die Tiefe / Höhe eines vollen Binärbaum wird beschrieben mit: #card $${\log }_2(n+1)-1\in \Theta (\log n)$$

Das folgt daraus, dass die Menge der Knoten in einem vollen Binärbaum mit der Tiefe $h$ folgend aussehen: $$1+2+4+\dots +2^h=2\cdot 2^h-1=2^{h+1}-1$$ und daraus folgt dann: $$n=2^{h+1}-1⟺h={\log }_2(n+1)-1$$ ^1704708664275

Implementation von Bäumen:

Wir haben folgend die Struktur von Binärbäumen betrachtet und implementiert. Was wir hier sehen können, dass ein Knoten immer 2 Kinder haben muss / wird. Da es schwierig ist dieses Konzept Baum in eine Datenstruktur zu übersetzen bzw. man es einfacher lösen kann, nimmt man dafür Arrays. Wie kann man hier einen Baum darstellen? #card Da wir wissen, wie viele Elemente ein Baum der Tiefe $k$ haben wird, können wir den Array gemäß dieser erzeugen. Anschließend nummerieren wir einfach von links nach rechts pro Schicht die Elemente, wobei diese dann die Position im Array darstellen.

[!Tip] Position von Kindern: Betrachten wir den Knoten $i$. Wir können jetzt für die Kinder des Knotens die Position mit $2\cdot i$(links) und $2\cdot i+1$(rechts) festlegen. Über die Mutter ( darüber) ist dann die Position: $\lfloor \frac{i}{2}\rfloor$ ^1704708664280

Stacks | Keller:

Mit einem Stack beschreiben wir eine Datenstruktur, bei welcher $n$-viele Elemente eingetragen werden können, aber immer nur das oberste Element abrufbar ist. Ein Stack folgt dem Prinzip des :: LIFO ( Last in First Out). ^1704708664285

Aus dieser Prämisse haben wir für diese Struktur dann zwei grundlegende Operationen: welche? #card

• Push(Element) -> um es auf den Stack zu legen
• Pop(Element) -> um das oberste Element vom Stack zu nehmen ^1704708664291

Implementierung:

Wir können einen Stack verschieden implementieren. Wir wenden dabei die bekannten Datenstrukturen Array und Liste (einfach und doppelt) an. Wie können wir sie jetzt konstruieren? es gibt 3 #card

• Array: wir zeigen immer auf das Top-Element. Dabei ist dann eine Operation mit $\mathcal{O}(1)$ definiert
• doppelt verkettete Listen: Der Zeiger wird an das Ende der Liste gesetzt. An diesem wird sich dann immer das Top-Element befinden
• einfach verkettete Liste: wir fügen das neuste Element einfach immer am Anfang ein. Gleichzeitig verbieten wir, dass sich der Pointer auf etwas anderes, als das erste Element ändern darf. ^1704708664296

Queues | Warteschlangen:

Während ein Stack nach LIFO funktioniert, setzen wir bei Queues auf :: FIFO (First in, first out). ^1704708664301

Das heißt also, dass wir mit einer Queue ebendiese Struktur ( das Konzept) implementieren: #card Es wird immer das letzte Element zuerst bearbeitet. Also ein neues Element wird einer Warteschlange angehangen, die den Inhalt chronologisch abrufen kann. -> Fügen wir also ein Element $x$ hinzu, dann wird es an das Ende der Queue gesetzt. -> Das erste Element der Queue wird immer als nächstes bearbeitet. ^1704708664306

Implementierung:

Auch hier haben wir wieder einige Möglichkeiten eine Queue zu implementieren: auch hier werden wir zwischen Array, doppelt/einfach Liste unterscheiden. Welche Möglichkeiten haben wir? #card

• Array: Zeiger auf End(neustes Element) und Top-Element(nächstes zu verarbeiten) -> es folgt $\mathcal{O}(1)$
• doppelte/einfach verkettete Liste: Zeiger auf erstes Element der Liste ( also nächstes Element zu verarbeiten) und auf letztes Element ( als neustes Element in Queue) ^1704708664312

Weiterführende Betrachtungen:

Wir bilden hiermit die grundlegenden Datenstrukturen, welche ferner für andere System notwendig werden und diese Konzepte erweitern oder spezielle Fähigkeiten erzeugen:

• [[111.09_heaps]]
• [[111.10_hash_functions]]
• [[111.11_bloom_filters]]