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

(Balanced) Search-Trees

(Balancierte) Suchbäume

anchored to [[111.00_anchor]]

Overview | Grundidee

Betrachte, dass wir eine dynamische Menge verwalten möchten. Also in dieser Informationen sammeln, aber anschließend auch Operationen wie, [ Einfügen, Löschen, Aufspalten, Vereinigen, Suchen ] umsetzen möchten. Wie können uns jetzt Suchbäume/Search-Trees dabei helfen, dieses dynamischen Mengen sinnvoll zu speichern und die Operationen einfach abarbeiten zu lassen? #card Wir setzen hier eine bestimmte Voraussetzung ein: -> Elemente rechts von einem Knoten ( also dessen Children) sollen immer größer sein, als die Value des Knotens. -> Elemente links von einem Knoten ( also deren Children) sollen immer kleiner sein, als die Value des Knotens ^1706628844817

Beispiel Betracht folgende Menge von Inhalten $\{1,4,6,7,9,12,14\}$, wie sieht sie eventuell in solch einem Baum aus? #card ![[Pasted image 20240118144426.png]] ^1706628844822

Definition | Properties

[!Definition] Eigenschaften von Suchbäumen welche können wir über Knoten treffen? #card Suchbäume sind grundsätzlich Binäre Bäume, haben also zwei Kinder maximal!

Für jeden Knoten $v$ in unserem Tree haben wir bestimmte Eigenschaften

• Sie haben einen Schlüssel $key(v)$
• können immer auf ihre Kinder (links/rechts) verweisen. etwa mit $lchild(v),rchild(v)$
• Haben auch einen Eintrag für deren parent, etwa mit $parent(v)$ ^1706628844828

Wir können jetzt noch zwei verschiedene Arten der Speicherung der Inhalte unseres Baumes betrachten:

| Blattorientierte Speicherung |

[!Important] Blattorientierte Speicherung wie werden hier die Elemente gespeichert, was befindet sich in den Knoten selbst? #card Bei der blattorientierten Speicherung: -> Befinden sich die Elemente der Menge nur in den Blättern in einem jeden Knoten befinden sich keine tatsächlichen Werte, es sind nur Dummy-Values –> die nicht in der Menge enthalten sein müssen! Weiterhin folgen wir aber der Grundstruktur, dass alles im linken Teilbaum von Knoten $v$ kleiner sein muss, während alles rechts davon größer ist. Wir können folgende Menge somit entsprechend in einem blattorientierten Baum schreiben: $\{1,6,4,7,9,12,14\}$ ![[Pasted image 20240118150209.png]] ^1706628844833

Auf diese Form werden nicht so stark eingehen und uns eher auf die Knotenorientierte Speicherung fokussieren.

| Knotenorientierte Speicherung |

[!Important] Knotenorientierte Speicherung wie und wo werden die Daten gespeichert, was ist relevant? #card Bei dieser Struktur wird in jedem Knoten ein Element der Menge gespeichert. Es entspricht dann also etwa der obig gezeigten Struktur: ![[Pasted image 20240118144426.png]]

Für einen Knoten $v$ gilt dann jetzt: Alle Schlüssel im linken Teil-Baum von $v$ sind kleiner als $key(v)$, während die rechten dann größer sind –> ^1706628844839

Suchen |

Wir möchten unsere Menge jetzt entsprechend durchsuchen können, damit es auch einen Sinn ergibt, warum wir überhaupt diese Struktur gebaut haben. Wie könnte der Pseudocode dafür aussehen? #card

\begin{algorithm} 
\begin{algorithmic} 
\Procedure{search}{x} 
\State u = Wurzel 
\State found = false 
\While{$u \exists \land !found$ }
	\If{key(u) == x }
		\State found = true 
		\Comment{found the key searched for }
	\Elif{ key(u)>x}
	\State u = lchild(u) 
	\Comment{We know that everything to left is smaller, thus searching there}
	\Elif{key(u) < x}
	\State u = rchild(u)
	\EndIf
\EndWhile 

\EndProcedure 
\end{algorithmic}
\end{algorithm} 

Also wir vergleichen immer den ausgewählten Knoten und schauen, ob sich unser gesuchtes Item links / rechts davon befindet. Wir haben dann anschließend entweder einen Eintrag gefunden oder nicht. Dabei können wir relativ schnell durch die Menge traversieren –> mit jedem Schritt verrringern wir die Menge von Dingen zu betrachten, weil wir ja entweder links/rechts weiterschauen und somit diesen Teil ausschneiden / nicht mehr betrachten.

Einfügen |

Wir möchten neue Elemente in unsere Menge einfügen und müssen dabei darauf achten, dass wir nur Elemente einfügen dürfen, die noch nicht enthalten sind! Wie gehen wir dafür vor? Pseudocode? #card

\begin{algorithm} 
\begin{algorithmic} 
\Procedure{insert}{x} 
\State $isPartOf,lastVisitedNode = search(x) $
\If{$\text{not isPartOf}$}
	\State $\text{u = lastNisitedNode}$
	\State \Comment{we can use this as new entry point, because we know that it was percolated to this position}
	\State \Comment{percolated here because the new element was compared to each node before (and thus went there)}
\While{$u \exists \land !found$ }
	\If{$key(u) == x $}
		\State $found = true $
		\Comment{found the key searched for }
	\Elif{ $key(u)>x$}
	\State $u = lchild(u) $
	\Comment{We know that everything to left is smaller, thus searching there}
	\Elif{$key(u) < x$}
	\State $u = rchild(u)$
	\EndIf
\EndWhile 
\EndIf

\EndProcedure 
\end{algorithmic}
\end{algorithm} 

Löschen |

Löschen kann hier komplex werden, weil wir den Baum unter Umständen aufteilen und dann wieder zusammensetzen müssen. Wie gehen wir dafür vor, wenn wir Element $x$ entfernen möchten?welchen Ablauf hat der PseudoCode #card

\begin{algorithm}
	\begin{algorithmic}
	\Procedure{delete}{x}
		\State $search(x)$ 
		\Comment{it will result with node $u$ which denotes the key for $x$!}
		\If{$u$ child}
		\State $rChild(parent()) = null$
		\Comment{We know that its the last in a tree, so we take its parent and delete this entry, easy!}
		\EndIf 
		\If{$u \text{only one child}$}
		\State $w = OnlyChild(u)$
		\Comment{saving child that is attached to node we want to remove}
		\State $Child(parent(u)) = w$
		\Comment{setting old child to be new child of parent ( we've overwritten u with w!)}
		\EndIf 
		\If{$u \text{has two childs w,v}$}
			\State`$v' = maxKey(Child())$
			\Comment{find the largest key in childs of this Tree ( nodes!) }
			\State $u = v'$
			\Comment{replace u - what we want to delete - with v - what we found to be second largest}
			\State $delete(v)$
			\Comment{delete the entry in its original position --> we placed it in position of $u$ now}
		\EndIf 
	\EndProcedure

	\end{algorithmic}
\end{algorithm}

Um also ein Elemente aus dem Baum zu löschen müssen wir drei Fälle betrachten, wobei zwei davon relativ einfach sind:

1. gesuchtes Element hat keine Kinder –> einfach löschen, problem solved
2. gesuchtes Element hat ein Kind –> das element an Stelle des zulöschenden Element –> easy!
3. gesuchtes Element hat zwei Kinder ( und so noch mehr darunter eventuell) –> wir suchen in der Menge darunter das größte Element ( Eigenschaft des Baumes!) und fügen es an Stelle des zu löschenden ein.
   1. Jetzt löschen wir den original-Eintrag des neuen Elements und sind fertig!

| Komplexität der Methoden

[!Definition] Laufzeit wovon ist die Laufzeit hier abhängig? Was für eine spezielle Betrachtung haben wir in Abhängigkeit von $n$ ? #card Die Laufzeit hängt immer sehr stark von der Höhe ab, weil wir ja bei allen Operationen Search/Delete/Add erstmal Suchen müsssen –> also in die Tiefe gehen und schauen, ob unser Element da gefunden werden kann. Daher folgt jetzt als Laufzeit $$\mathcal{O}(heighth+1)$$ Es ist dabei wichtig, dass $h$ minimal $\log n$ ist, und sosnt $h$ auch $=n$ sein kann! ^1706628844858

Wir möchten diesen Fall, dass der Baum auch $height=n$ haben kann vermeiden, müssen also einen Weg schaffen, wie wir dazu kommen, dass nicht aus Versehen der ganze Baum eine lange Kette ist und kein Baum mehr.

| Balancierte Bäume

| Höhenbalance

Um auf balancierte Bäume eingehen zu können, müssen wir uns zuerst die Höhenbalance anschauen:

[!Definition] Höhenbalance eines Baumes was meinen wir damit, wovon ist sie abhängig? Höhe eines leeren Teilbaumes #card Mit der Höhenbalance meinen wir folgende Definition: $$Balance(u)=Height(T_{righy}-Height(T_{left}))$$ Also wenn wir einen bestimmten Knoten $u$ anschauen, dann wird bei der Balance jetzt also die Höhe des rechten Teilbaum - Höhe des linken Teilbaum gerechnet.

Wir definieren noch, dass die Höhe eines leeren Teilbaum $=11$ ist! –> sonst ist es dumm, wenn man es, wie in der Vorlesung mit -1 setzt!

Es folgt für die Beispiele jetzt: ![[Pasted image 20240120215942.png]]

Das Bestimmen der Tiefe geht hier immer von der gesamten Höhe des Teilbaumes aus. Also heißt, wenn wir etwa den zweiten Knoten aus dem linken Baum betrachten: der linke Teilbaum ist in seiner Tiefe $=1$ während der rechte Teilbaum eine Tiefe von $2=1+1$ hat! damit folgt dann $Height(x_1)=2-1=1$ !

Für den obersten Knoten, also die Wurzel gilt jetzt: $1+1+1-1=2$! der rechte Teilbaum hat 3 Stufen, während der linke nur eine hat! ^1706628844863

AVL-Baum |

[!Definition] AVL-BAUM wann sprechen wir bei einem Suchbaum von einem AVL-Baum? #card Wir nennen irgendeinen Baum jetzt AVL-Baum, wenn für Alle Knoten $\mid Balance(u)\mid \le 1$ gilt. Das heißt also, dass wir für jeden Knoten folgend berechnen: $Balance(X)=Height(Tre{e}_{right}(X))-Height(Tre{e}_{left}(X))\le 1$ Die Balance kann folgende Fälle haben: $Balance=-1$ –> dann haben wir nur einen linken Knoten $Balance=0$ –> dann haben wir einen linken und rechten Knoten ( und somit balancieren sie sich aus!) $Balance=1$ –> dann haben wir nur einen rechten Knoten-Punkt drunter. ^1706628844868

[!Example] Betrachte folgenden Baum, wie können wir hier jetzt die Balance beschreiben? ![[Pasted image 20240120221953.png]] #card Wir gehen beim bestimmen der Balance immer nach der Gesamten Maximalen Höhe des Teilbaumes aus! Es folgt dadurch so eine Bestimmung. Und weil hier die Eigenschaft gehalten wurde, haben wir einen AVL-Baum! ![[Pasted image 20240120223155.png]]

^1706628844873

[!Example] weiteres Beispiel für AVL-BAUM: #card ![[Pasted image 20240120223438.png]] ^1706628844880

AVL Tress $⟹$ Fibonacci-Sequence

Wir können die Fibonacci-Sequenzen auf AVL-Bäume anwenden und sprechen dabei dann immer über den minimalen Baum, um ein AVL bilden zu können. Sie werden folgend definiert: #card Wie bei Fibonacci können wir diesen Baum jetzt rekursiv beschreiben: Dafür brauchen wir die zwei Grundzustände $T_0,T_1$ mit:

• $T_0=$ ein einzelner Knoten $Balance=0$
• $T_1=$ ein links-Starker Baum, also ein solcher Baum mit zwei Knoten, wobei der Knoten einen linken Knoten hat und damit gilt $Balance=-1!$ Wir beschreiben alle nachfolgenden Zustande jetzt mit:$T_n=$ Ein Knoten mit linken und rechtem Teilgraphen: Dabei ist $T_{left}=T_{n-1}$ und $T_{right}=T_{n-2}$ ![[Pasted image 20240120223948.png]]

AVL-Bäume mit Höhe $h$ haben mind $F_h$ Blätter

[!Definition] Es folgt für einen Teilbaum $T_h$ = $F_h$ warum? #card Da die Definition der Fibonacci-Bäume gleich den Fibonacci-Zahlen ist, können wir jetzt für einen beliebigen Punkt sagen, wie die Struktur des Knoten aufgebaut ist. Also wenn wir Knoten $F_h$ anschauen, dann ist $h=n-x$ und dann können wir das wieder aufteilen und dann bestimmen, wie der Teilbaum für die sukzessiv tieferen Teilbäume sein muss / wird. (Wir wissen ja, dass diese Bäume hier auf sich aufbauen!) ^1706628844885

Beweis von [[#AVL-Bäume mit Höhe $h$ haben mind $F_h$ Blätter]]

^1706628844890 Wir können das jetzt mit einer Induktion betrachten / beweisen wie, was beachten wir bei der Konstruktion für $h\ge 2$ #card Für die Werte $h=0$ gilt das mit einem einzigen Knoten und $F_0=0$ ! mit $h=1$ gibt es für die AVL Bäume drei Möglichkeiten:

• ein balancierter mit Balance $=0$ –> also ein Knoten mit Child links und rechts
• ein links-starker Knoten mit Balance $=-1$ -> nur linkes Kind von Knoten
• ein rechts-starker Knoten mit $Balance=1$ -> nur rechtes Kind von Knoten Ist jetzt $h\ge 2$, dann folgt: Der Baum der Höhe $h$ mit baut sich aus zwei Bäumen (links/rechts) mit Höhe $T_{h-1}$ (links) und $T_{h-2}$ (rechts) zusammen. Nach der Annahme hat dann $T_h$ nach Induktionsannahme $\ge F_{h-1}+F_{h-2}$ Blätter und damit wird das erfüllt! Visuell folgend: ![[Pasted image 20240120224907.png]] ^1706628844895

Höhe von AVL-Bäumen

[!Definition] Höhe von AVL-Bäumen bei $n$ Knoten Wir können aussagen, dass die Höhe des AVL-Baum bei $n$ Knoten $$\mathcal{O}(\log n)$$ ist. Beweisen können wir das mit: Betrachte die Definition der Fibonacci-Zahlen: $F_h=\frac{{\alpha }^h-{\beta }^h}{\sqrt{5}},\alpha =\frac{1+\sqrt{5}}{2},\beta =\frac{1-\sqrt{5}}{2}$ Wir wissen, dass ein AVL-Baum $T$ $\le n$ Blätter hat. Dadurch dann: $F_h=\frac{{\alpha }^h-{\beta }^h}{\sqrt{5}}\le n$ Jetzt wissen wir, dass $\mid \beta \mid <1$ und dadurch $\frac{a^h-{\beta }^h}{\sqrt{5}}\ge \frac{a^h}{2\sqrt{5}}$ $⟹a^h\le 2\sqrt{5}\cdot n$ $⟹h\log a\le \log (2\sqrt{5})+\log n$ $⟹\le \frac{\log (2\sqrt{5})+\log n}{\log \alpha }=\mathcal{O}(\log n)$

Einfügen in AVL-Bäume

Der AVL-Baum soll ja in seiner Struktur $Balance(u)\le 1,\forall u$ nicht verletzt werden, das heißt, wenn wir ein neues Element einfügen möchten, dann ist es relevant, dass wir unter Umständen den Baum neu balancieren müssen. Betrachte das Szenario, dass wir nach dem Einfügen eines neuen Elementes in einem Baum, dabei werden wir etwas rechts eingefügt haben!, die Balance jetzt plötzlich $Balance(u)=2$ ist. Was heißt das, und wie können wir das lösen? #card Wie wir sehen können haben wir jetzt auf der rechten Seite des betrachteten Teilbaumes von $u$ ( also dessen rechtes Kind!) entweder $Height=2,3,\dots$ während konträr dazu beim linken Teilbaum (linkes Kind ) $Height=0,1,height(T_{right})-1,\dots$ ist, also wir haben einen Zustand erhalten, wo rechts die Tiefe höher ist und dadurch eine Disbalance ensteht!. Wir müssen jetzt schauen, dass wir die Balance wieder herstellen, indem wir Teile des Baumes verschieben. ^1706628844899

Rebalancieren, wenn Disbalance $\wedge$ Wert Rechts eingefügt

Betrachten wir folgenden Fall: Wir haben jetzt $Balance(v)=2$, betrachten das rechte Kind $u=T_{right}$ und sehen $Balance(u)=1$ Das heißt, wir haben den neuen Knoten rechts eingefügt und damit die vorherrschende Balance darüber gestört: ![[Pasted image 20240120230607.png]] Anhand des Bildes, wie können wir das jetzt wiederherstellen /lösen? #card Wir können mit einer Rotation der Knoten darüber nach links die Ordnung wiederherstellen! Der Knoten, wo eine Disbalance aufgetreten ist, wird genommen und eins nach oben verschoben ( also $v$ ist jetzt an Stelle $u$) Der Wert, der verschoben wurde, wird jetzt auch nach links verschoben und dabei dann der Teilbaum vom ehemaligen $v$ diesem Knoten $u$ rechts angehangen. Wir hängen ihn rechts an, weil er ursprünglich auch schon größer war und das eingehalten werden muss! Es entsteht folgende Struktur: ![[Pasted image 20240120231027.png]]

[!Important] Auswirkung der Rotation was ändert / bleibt danach? #card unter Anwendung der Rotation bleibt die links-rechts Ordnung erhalten, also dass die Werte links kleiner, als die Werte rechts sind! Ferner $T_{left}<u<T_A<v<T_B$ gemäß des obigen Beispiels: ![[Pasted image 20240120231225.png]]

Es werden die Balancen von $v,u$ auf $=0$ verändert! In den Teilbäumen ist die Balance gleichgeblieben! Es folgt weiter bezüglich der Rotation: $height(v)=height(u_{\text{ before rotation}})$ -> Da wir $v$ nach links verschieben und es den Platz von $u$ einnimmt, ist die Höhe dann auch anders ^1706628844904

Rebalancieren, wenn Disbalance $\wedge$ Links eingefügt:

Wenn wir jetzt links einen neuen Wert in unseren Baum einfügen und dadurch eine Disbalance erzeugen, dann wird daraus folgen, dass $Balance(v)=-1$, denn wir haben jetzt hier mehr, als in den anderen. Als Beispiel dafür: ![[Pasted image 20240120231942.png]] Wie können wir das Problem jetzt lösen ? #card Wir wenden eine Doppelrotation an, sodass hier entsprechend das linke Kind, was die Disbalance in $v$ auslöst zwei Stufen nach oben verschoben wird. Auch hier ist die Rotation wieder vom Prinzip links drehend. Visuell ist es wahrscheinlich einfacher zu erklären: ![[Pasted image 20240120232124.png]] Wir erhalten wieder bestimmte Eigenschaften:

• $z$ im Beispiel wird hier also 2 nach oben geschoben
• die Balance ist danach $Balance(z)=0$
• Man könnte $A,B$ vertauschen. ^1706628844909

| Einfügen in AVL-Baum

Aus der vorherigen Betrachten kann es kompliziert sein, etwas in den AVL-Baum einzutragen. Wir brauchen daher einen Ablauf. Was müssen wir beim einfügen beachten? Bei Fehlern, wie oft würden wir rotieren müßsen? #card Wir möchten einen folgenden Algorithmus zum Einfügen betrachten:

[!Definition] Einfügen in AVL-Baum

1. Füge $x$ als neues Element in das entsprechend Blatt $w$ als Kind ein ( links oder rechts davon, größer/kleiner!) -> Folge dem Pfad und berechne alle Balancen neu ( die darüber liegen und davon betroffen sein könnten)
2. Sofern eine Disbalance auftritt, also $Balance(x)=-2\vee 2$ –> rebalanciere entweder mit Rotation $balance()=2$ oder Doppelrotation $balance()=-2$

Wie oft werden wir diese Rotation beim Einfügen eines Elementes maximal machen? –> 1x, weil wir nur in einem Teilbaum die Balance groß zerstören können und diese dann durch die Operation wiederherstellen! ^1706628844913

| Löschen aus AVL-Baum

Das Löschen eines Elementes kann zu ähnlichen Fehlern / Problemen, wie beim einfügen führen. Wir könnten die Balance zerstören! Wie verfahren wir demnach beim löschen eines Elementes? Welche 3 Fälle müssen wir betrachten? #card

[!Definition] Löschen aus einem AVL-Baum Um das zu bewältigen:

1. Suchen wir das Element $w$
2. Löschen jetzt den Knoten $w$.
3. mögliche Disbalance muss gelöst werden Wir können tendenziell 3 Fälle betrachten, die diese Disbalance auslösen könnte: Sei dabei jetzt der tiefste Knoten mit einer Disbalance $u,Balance(u)=2$ Sei weiterhin $v$ das rechte Kind von $u$

^1706628844918

Wir können jetzt folgende Fälle betrachten:

[!Definition] 1. Disbalance im linken Kind Also $Balance(v)=1$ was bedeutet das für den Baum, wie können wir das lösen? #card ,während $Balance(u)=2$ und wir somit zu wenig im linken Teil haben! Das lösen wir, durch eine Rotation nach links! –> also $v$ der rechte Knoten mit $balance(v)=1$ wird an die Stelle des Knotens $u,Balance(u)=2$ gesetzt und u rutscht nach links. Dabei wird auch $A$ dann ein rechtes Kind von $u$! ![[Pasted image 20240120234222.png]]

^1706628844923

[!Definition] 2 Disbalance im rechten Kind entsteht Also $Balance(v)=-1$ wie können wir das lösen, was muss gemacht werden, warum? #card , während $Balance(u)=2$ –> Das heißt der linke Baum wird plötzlich zu flach und der rechte Baum ist viel tiefer ( daher -1!) Wir lösen das durch eine Doppelrotation nach links, folgen also auch da dem gleichen Ansatz, wie beim Einfügen! Im Beispiel wird jetzt $z$ an die Stelle von $u$ rücken, $v$ an der Stelle bleiben und als linken Teilbaum dann nur noch $B$ oder $A$ beibehalten ( ist egal). Das nun obenliegende $z$ wird rechts von sich v und den Rest haben und links wird es $u$ als erstes Kind haben und $A$ ist dann das rechte Kind von $A$ und $L$ das linke von $u$! Visuell: ![[Pasted image 20240120234658.png]] ^1706628844927

[!Definition] 3 Disbalance im rechten Kind entsteht, ist aber ausgeglichen. Also jetzt ist $Balance(v)=0$ ( innerhalb dieser passt es also!) aber warum müssen wir das trotzdem anpassen? Wie können wir das machen? #card , aaber der Parent-Knoten $u$ hat $balance(u)=2$ –> Also der linke Teilbaum ist wieder viel kleiner, als der rechte Teilbaum. Wir lösen das durch eine Rotation nach links! Das heißt im Beispiel werden wir den Knoten mit $Balance(v)=0$ nehmen und eins nach links verschieben. Dadurch wird dann $v$ an der Stelle von $u$ sein und $u$ nach links runterrutschen. Weiterhin ist dann das rechte Kind von $v$ der Teilbaum $B$ welcher zuvor der rechte Teilbaum von $v$ war ( bleibt also erhalten). der gleichgroße Teilbaum $A$ ( linkes Kind von $v$ und Grund für $Balance(v)=0$) wird jetzt das rechte Kind von $u$, wobei $u$ das linke Kind von $v$ ist! Der Teilbaum, wo das Element entnommen wurde, also $L$ wird weiterhin der linke Teilbaum von $u$ bleiben. Visuell: ![[Pasted image 20240120235343.png]] Dabei ändert sich die Gesamthöhe nicht! ^1706628844932

Satz für balanced trees

[!Definition] Laufzeitverhalten von balanced trees wie ist es definiert, warum? #card Mit balancierten Bäumen kann man die Operationen Suchen / Einfügen / Streichen unter Abhängigkeit von $n$ Elementen in diesem Tree in folgender Zeit durchlaufen: $$\mathcal{O}(\log n)$$ ^1706628844937

Anwendung | Plane-Sweep Algorithmen

Betrachten wir jetzt folgendes Problem: Wir möchten in einem $m$ dimensionalen Raum, hier jetzt $2$-dimensional, die Schnitte von $n$ achsenparallelen Liniensegmenten berechnen.

Dafür haben einen greedy Ansatz gegeben:

1. berechne die Schnitte von allen Paaren, die auftreten können
   1. Wir müssen also jede Kombination von Linien durchgehen und prüfen, ob ein Schnitt auftritt
   2. das Ganze brauch jetzt $\mathcal{O}(n^2)$

Alternativ dazu bietet sich noch ein zweiter Ansatz, welcher deutlich schneller sein wird ( mit $\mathcal{O}(\log n)$)

[!Definition] Plane-Sweep was ist der Ansatz für diesen Algorithmus, wozu brauchen wir hier dann AVL-Bäume? #card Als Ansatz für “Sweep-Line” werden wir den ganzen Bereich quasi mit einer Linie entlang $y$ oder $x$ konstruieren und sie anschließend des ganzen Bereiches ( jenachdem entlang x oder y) abfahren. An bestimmten Punkten “halten wir an” und berechnen dann etwas ( etwa Distanz zwischen Punkten, die wir soeben gefunden haben)

Wir bauen jetzt zwei eigene Strukturen auf, die wir während des Verlaufs des Algorithmus anwenden werden / möchten: x-Struktur Diese Struktur ist aufgebaut, wie eine (Event-)Queue und enthält eine geordnete Liste der Endpunkt, Diese Events werden anschließend nacheinander abgearbeitet, man wird also für jede $x$-Koordinate im Bereich ( wir machen ja eine vertikale Linie) unserer Punkte, dann immer die Menge der getroffenen Linien speichern. ( Stelle man sich vor, dass wir gerade bei $x=4$) sind und auf verschiedenen $y$ Höhen jetzt drei Linien haben, die sich überschneiden köönten. Diese drei Linien “Segmente” werden anschließend in dieser x-Struktur gesammelt für bestimmtes $x$

eine zweite Datenstruktur ist die $y$-Struktur Sie gibt den Zustand der Sweep-Line an Position $x$ an. Das heißt, es speichert die horizontalen Segmente, die soeben von $L$ gekreuzt werden Diese Struktur wird als AVL-Baum organisiert. Dabei werden die Segmente, die ausgewählt werden, dann immer nach y sortiert ^1706628844942

Bei diesem Ablauf werden die Events bei einem Schnitt mehrer Segmente jetzt entscheiden sein. Betrachten wir hierbei folgenden Zustand bei einem Schnitt in vertikalem Segment $s(x,y_u,)y_0$ und folgendem Suchbaum ( nach y-Koordinate sortiert!) ![[Pasted image 20240122151031.png]] was müssen wir jetzt berechnen was muss anschließend gelten? #card Wir müssen für beide Segmente, die aufgetreten sind, jetzt entsprechend die Ränge im Baum berechnen. Dabei berechnen wir den Rang eines Segments $y$ mit: $rang(y)=|segmente<y\mid$ Wir suchen damit jetzt die Menge der Schnittpunkte des gewählten Segments. Es folgt also: $s=Rang(y_0)-Rang(y_u)$ -> Wir bestimmen jetzt $Rang(y)$ indem:

1. wir uns von der Wurzel aus, an jeden Knoten $v$ die Zahl der Elemente im linken Teilbaum merken. Also $coun{t}_{left}(v)$
2. wir laufen den Suchpfad bis nach $y$ herab ( entlang des AVL-Baumes!)
3. sofern wir an einem Knoten $v$ rechts abbiegen ( also größer sind), machen wir $coun{t}_{left}(v)+1$
4. wenn wir nach links abbiegen -> nichts machen
5. anschließend haben wir dann den Rang von $y$ gefunden in $\mathcal{O}(\log n)$ ^1706628844946

[!Important] Laufzeit von plane-Sweep bezüglich Schnittpunkt0Berechnung In Zeit $\mathcal{O}(n\cdot \log n)$ kann man mit Plane-Sweep die Anzahl der Schnittpunkte von $n$ achsenparallelen Liniensegmentn in einer Ebene finden!

( Bemerkung ):

• die Segmente müssen nicht zwingend achsenparallel sein!
• Plane-Sweep funktioniert auch im 3D Raum ( Space-Sweep!)