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

(a,b)- Bäume | bei uns meist $(2,4)$-Bäume

anchored to [[111.00_anchor]] proceed from [[111.37_b_trees]]

Wir möchten uns eine weitere Form von Bäumen anschauen und diese definieren.

[!Definition] $(a,b)$-Bäume. Was macht sie aus, welche 4 Eigenschaften müssen gelten? #card

Seien folgend $a,b\in \mathbb{N},a\ge 2,b\ge 2a-1$>Dann nennen wir jetzt einen Baum $T$ $(a,b)$-Baum, falls die folgenden vier Eigenschaften gelten:

1. alle Blätter haben die gleiche Tiefe ( also wenn wir ihn visuell betrachten, sind alle Blätter auf der “gleichen Ebene”)
2. alle inneren Knoten haben $\le b$ Kinder –> innere Knoten sind die, die auf ihrer Höhe noch nachbarn haben!
3. alle Knoten (außer der Wurzel) haben $\ge a$ Kinder
4. Die Wurzel selbst hat $\ge 2$ Kinder

(2,4)-Bäume

Als spezielle bzw wichtige Grundstruktur möchten wir uns jetzt $(2,4)-$Bäume anschauen. Betrachten wir dabei eine Menge $S=\{x_1<x_2<\cdots <x_n\}$, welche wir jetzt in einem solchen Baum speichern möchten. ^1706629932940

[!Important] Wie gehen wir vor, um diese sortierte Menge entsprechend in den Baum einzufügen Wir speichern $S$ in den Blättern des Baumes und dabei immer von links nach rechts sortiert. Also im linkesten Blatt werden wir das kleinste Element $x_1$ haben und vice versa Ein innerer Knoten $v$ hat hierbei $d$ Kinder und weiterhin auch $s_1,\dots s_{d-1}$ Schlüssel! Weiterhin nennen wir dann ein Element $s_i$ den Inhalt des rechtestens Blattes im $i$-ten Unterbaum, den wir betrachten können. Wir müssen hier weiterhin das maximal Element von der Menge, also $x_n$, in der Wurzel speichern

Wir können durch diese Konstruktion eines Baumes jetzt folgende Aussage über die Höhe treffen:

[!Important] Höhe eines $(2,4)$-Baumes wie können wir sie einschränken / beschreiben? #card Es gilt jetzt für die Höhe eines $2,4$-Baumes mit $n$ Blättern folgend: $$\frac{1}{2}\cdot \log n\le h\le \log n$$ ^1706629932948

Suchen / Einfügen

Auch hier sind die Operationen Suchen/Einfügen gleich, wie bei einem B-Baum!

[!Important] Sonderfall beim Einfügen eines Wertes in Knoten $w$ was müssen wir beachten bezüglich der Menge von Schlüsseln? Wie ist die Laufzeit davon? #card Wenn wir einen Knoten haben und nach dem Einfügen jetzt $5$ Kinder haben ( also $\ne \le b=4$), dann müssen wir den Knoten $w$ wieder aufspalten und somit auf dessen Parent zugreifen, das Mittelelement $x_j$ nehmen und dann als Schlüssel deklarieren. Die beiden neuen Knoten $w^{\prime }$ und $w^{\prime \prime }$ werden dann links und rechts vo n $x_j$ platziert! ![[Pasted image 20240125222132.png]] Die Laufzeit dieser Operation beträgt dabei $$\mathcal{O}(1+\mid Spaltung\mid )$$ ^1706629932956

Entfernen

Wenn wir jetzt ein Element aus dem (2,4)-Baum entfernen möchten, müssen wir wieder bestimmte Dinge beachten, wie es auch bei B-Bäumen notwendig war.

[!Definition] Ablauf des Entfernens eines Inhaltes $a$ wie müssen wir vorgehen? welche 3 Fälle müssen wir unterscheiden? #card

Auch hier starten wir, indem wir das gesuchte Element mit Suche(a) suchen.

Haben wir dieses Element erhalten möchten wir drei Fälle unterscheiden:

1. $a$ steht auch im parent****, also $parent(v)=w$ -> dann löschen**** wir $v$ und streichen es aus $w$

2. $a$ steht nicht im parent****, also $parent(v)=w$ und ist somit das**** rechteste Kind ( weil ja Schlüssel offenbar kleiner sind ( sonst wäre es nicht da drin zu finden) . Sei dann weiter $v^{\prime }$ das linkere Kind von $v$ mit dem Schlüssel $s$. Wir entfernen dann den Eintrag $a$

![[Pasted image 20240125223642.png]]

3. Es kann sein, dass w nur noch ein Kind hat. Dann können wir zwei vorgehen betrachten: vereinigen / balancieren mit Nachbarn

　 1. verschmelzen****: Dabei muss ein Geschwister von $w$, also $v$ genau 2 Kinder haben********. Anschließend kann das einzige Element $w$ dann in den knoten übernommen werden****. Visuell folgend:

![[Pasted image 20240125223912.png]]

　 2. Ein Geschwister $v$ von $w$ hat $\ge 3$ Kinder –> also wir können versuchen aufzuspalten und zu balancieren!. Dann möchten wir jetzt folgendes machen: Wir nehmen das linkeste Element von $v$ und fügen es bei $w$ ein ( also den Schlüssel und dessen Teilbaum). Visuell folgend:

![[Pasted image 20240125224047.png]]

Die Laufzeit fürs Entfernen lässt sich dann auf $\mathcal{O}(1+\mid \text{Vereinigung}\mid )$ zusammenführen. –> Teils müssen wir viel vereinigen / mal weniger!

Amortisierte Laufzeit vom (2,4)-Baum

Wir können aus der obigen Betrachtung heraus erkennen, dass hier die Laufzeit von diversen Operationen immer zwischen $\mathcal{O}(1),\mathcal{O}(\log n)$ schwankt, weil diese vom Zustand des Baumes abhängig sind. Wir möchten daher jetzt eine amortisierte Analyse durchführen, um die Laufzeit entsprechend evaluieren zu können..

mögliches Vorgehen könne hierbei das Betrachten eines Bankkontos sein, in welchem wir bei: • schnellen Operationen einen Euro einzahlen –> somit Zeit gutschreiben! • teure Operationen ziehen wieder Geld ab –> etwa $\log n€$ –> also sie machen den Gesamtwert wieder schlechter

Aus dieser Betrachtung heraus können wir dann evaluieren, wie schnell / gut unser System in Abhängigkeit von normalen Operationen sein wird / kann Dabei achten wir darauf, dass $T_{actual}+\Delta B\le T_{amortisiert}$, dass heist wir möchten upper boundaries finden. Dabei erhoffen wir uns natürlich $T_{actual}=\mathcal{O}(1)$ Aus der obigen Konstruktion können wir jetzt folgende Zeit evaluieren / erzeugen:

[!Definition] amortisierte Kosten für Operationen: einfügen/löschen wie kommen wir auf die amortisierte Laufzeit, welche ist es? #card

Wir können folgern, dass in einem (2,4)-Baum die amortisierten Kosten zum einfügen / löschen in der Zeit von $\mathcal{O}(1)$ verlaufen!

Beweisen können wir es folgend:

Wir wählen ein Potential ( in obigen Beispiel also einen Bankkonto-Betrag) und definieren es wie folgt:

$$pot(T)=2\cdot \mid Grad-nod{e}_1\mid +1\cdot \mid Grad-noe{d}_2\mid +0\cdot \mid Grad-nod{e}_3\mid +2\cdot \mid Grad-nod{e}_4\mid +4\cdot \mid Grad-nod{e}_5\mid$$

und bei dieser Konstruktion sehen wir, dass folgende Invarianten eintreten werden!

• $pot(T)\ge 0,\forall T$

• Immer wenn wir die Operation zum spalten/vereinigen/reduzieren auf einen Knoten $v$ anwenden, werden dann die anderen Knoten eine Ordnung von 2,3,4 Kindern haben! -> sonst wäre die Operation nicht notwendig gewesen!

• Vor dem Einfügen/Löschen sind immer alle Knoten in Ordnung ( also die Struktur ist valide!)

Es gilt hierbei jetzt also folgendes:

Die Unter-Operationen Spalten/Vereinigen/verringern werden mit Kosten von $\mathcal{O}(1)$ beschrieben und es handelt sich dabei um deren tatsächlichen Kosten!

[!Info] betrachten wir die amortisierte Analyse vom Einfügen genauer: wie konstruieren wir die amortisierte Laufzeit, womit schließen wir ab? #card

Beim einfügen brauchen wir unter die Unter-Operationen: Spalten, wofür wir betrachten können, wie es das Potential ( also den Betrag des Bankkontos ) verringern kann.

Beim Spalten betrachten wir folgende Veränderung des Potentials: $w=4\to 0$ und weiter beim parent $parent(w)$ steigt es um $\le 2$ –> also ist es doch am sinken, weil die Nachteile die Vorteile überwiegen!

Es folgt weiterhin: amortisierte Laufzeit = tatsächliche Kosten + Potentialerhöhung

Also beim Einfügen:

1. tatsächliche Kosten 1 + Potentialerhöhung $\le 2$

2. und für die Spalte-Operation: tatsächliche Kosten $f$ + Potentialerhöhung $\le f$

wodurch wir jetzt folgend: $\le 3$ resultieren werden

Für die Entfernen-Operationen verfahren wir hier analog!

Anwendung der Bäume | Sortieren von fast sortierten Listen

Angenommen wir haben jetzt eine fast sortierte Liste, die wir anschließend vollends sortieren möchten. Wie können wir das unter Anwendung von (2,4)-Bäumen sinnvoll machen? #card Prinzipiell möchten wir einen leeren Baum einfach fortlaufend mit den Elementen füllen, und lassen ihn sich selbst balancieren, wodurch wir keinerlei Aufwand haben. Wir werden hierbei logischerweise $$\begin{gathered} m \\ cdot\mathcal{O}(n\log n)(Search) \end{gathered}$$ und weiterhin auch $n\cdot \mathcal{O}(n)(insert)$ durchfüren. Die Operation der Suche ist relativ langsam, aber wir können sie in ihrer Geschwindigkeit verbessern –> das passiert automatisch, wenn wir eine etwas vorsortierte Menge haben( weil man dann einfacher durch den Baum traversieren bzw cachen kann). Betrachte dafür die Eingaben-Menge $X=\{x_1,\dots ,x_n\}$ welche wir chronologisch einfügen möchten Weiterhin beschreibt $F=|\{(i,j)\mid i<j\wedge x_i>x_j\}|$ die Menge von Inversionen, die innerhalb dieser Folge auftreten kann –> also die Paare innerhalb der Menge, die in ihrer Sortierung verdreht sind Für diese Inversion gilt dann: $0\le F\le \frac{n^2}{2}$

[!Definition] Laufzeit vom Sortieren mit einem $(2,4)$ Baum mit welcher Geschwindigkeit können wir das durchführen? Was sind wichtige Betrachtungen dafür? #card

Das Sortieren von einer fast sortierten Liste von Elementen ist mit (2,4)-Bäumen mit einer Laufzeit von $\mathcal{O}\left(n\log \left(\frac{F}{n}+1\right)\right)$ möglich, wobei wir mit $F$ die Menge von Inversionen( also falsch herum geordneten Elementen in der Eingabe) meinen

Das bedeutet dann folgende Laufzeiten, je nach $F$!

$$\begin{array}{rl}& \\ >>F& \approx n^2⟹T=\mathcal{O}(n\log n)\\ >>F& \approx n⟹T=\mathcal{O}(n)\\ >>F& \approx n\log n⟹T=\mathcal{O}(n\log \log n)\\ >>F& \approx n^{\frac{3}{2}}⟹T=\mathcal{O}(n\log n)>>\end{array}$$

Beweisen kann man das folgend: Sei $f_i=|\{j\mid i<j\wedge x_i>x_j\}$ dann können wir daraus die gesamte Menge von $F$ konstruieren mit

　 $F=\sum _i{f}_i$

-> Wir fügen jetzt die Elemente in umgekehrter Reihenfolge in den Baum ein und fangen so etwa mit $x_n$ an.

Beim einfügen eines jeden Elements dieser Menge $x_i$ sind dann $x_{i+1},\dots x_n$ schon enthalten. Wir starten dann ganz links und laufen bis zur Wurzel, anschließend wieder nach unten -> entsprechen der Knoten und deren Schlüssel. Wenn jetzt $x_i$ relativ klein ist, läuft man sich weit bis zur Wurzel!

[!Important] PseudoCode zum sortieren eines (2,4) Baumes wie gehen wir vor? #card Das heißt als PseudoCode können wir das folgend beschreiben:

>traverse-Up(xi): >v = linkestes Blatt >while ( xi > Schlüssel(parent(v))) > v = parent(v) `>````

Wir traversieren also bis wir wissen, dass unser xi kleiner ist, als die betrachteten Schlüssel!

[!Tip] amortisierte Laufzeit zum Einfügen eines Elementes #card Die amortisierte Laufzeit zum Einfügen eines Elementes kostet uns $$\mathcal{O}(1+ \log f_{i})$$ Wir wissen bereits, dass das Einfügen sonst mit $\mathcal{O}(1)$ läuft. Wir müssen uns aber immer noch im Baum zurechtfinden ( also lokalisieren). Das machen wir ja jetzt durch das hochtraversieren, wobei wir dann zu einer Höhe $h$ kommen und anschließend unser neues Elemente nach den $f_{i}$-ten Elementen einfügen. Betrachten wir es visuell: Dafür beschreibt $v$ den Umkehrpunkt und $v’$ das linkeste Kind von $v$. Wir machen folgendes: ![[Pasted image 20240126123632.png]]

Es folgen jetzt Gesamtkosten von $$\sum\limits_{i=1}^{n} \mathcal{O}(1 + \log f_{i}) = \mathcal{O}\left( n + \sum\limits_{i=1}^{n} \log f_{i}\right) = \mathcal{O}\left( n + n \log \frac{F}{n} \right)$$ Was dann unserer Gesamtzeit zum sortieren entspricht! ^1706629932963