• Praktische Grundlagen der Informatik
• Algorithmen und Datenstrukturen
• Übersicht Data Science:
• Data Science / Machine Learning
• Projekt: Deep Teaching
• Alte Veranstaltungen:
• Grundlagen der Informatik (NF)
• Octave/Matlab Tutorial
• Game Physik

• Home
• Lehre
• Publikationen
• Kontakt/Impressum

Suchbäume

Sortierte Arrays (sorted arrays)

Suchbäume kann man sich als eine dynamische Version eines sortierten Arrays vorstellen. Aber sortierte Arrays unterstützen keine schnelle Implementierung von Insert und Delete.

Unterstütze Operationen des sortierten Arrays

Search: Für einen Schlüssel $k$, gib einen Zeiger zu einem Objekt in der Datenstruktur zurück, das den Schlüssel $k$ hat (oder melde, dass kein solches Objekt existiert). Implementiert wird dies auf einem sortierten Array mittels BinarySearch.

Min(Max): Gib einen Zeiger zu einem Objekt in der Datenstruktur zurück, das den kleinesten (größten) Schlüssel hat. Implementiert wird dies auf einem sortierten Array mittels "gib erstes (letztes) Element zurück".

Predecessor(Successor) d.h. Vorgänger(Nachfolger): Für einen Zeiger zu einem Objekt in der Datenstruktur gib einen Zeiger zu einem Objekt zurück, das den nächst-kleineren (nächst-größeren) Schlüssel besitzt. Wenn das gegebene Objekt den kleinsten (größten) Schlüssen hat, gib "none" ( bzw. Nullzeiger etc.) zurück. Implementiert wird dies auf einem sortierten Array mittels Search und anschließend das vorherige (nächste) Element des Arrays zurückgeben.

OutputSorted: Gib die Objekte in der Datenstruktur nacheinander aus in der Ordnung Ihrer Schlüssel. Implementiert wird dies auf einem sortierten Array indem einfach die Elemente in ihrer Reihenfolge zurückgegeben werden.

Select: Für eine Zahl $i$ zwischen $1$ und der Anzahl der Objekte in der Datenstruktur, gib das Objekt zurück, das den $i$-kleinsten Schlüssel besitzt. Implementiert wird dies auf einem sortierten Array einfach mittels Rückgabe des Elements mit dem Index $i$.

Rank: Für einen Schlüssel(wert) $k$ gib den Index des Objekts in dem Array zurück, mit einem Schlüsselwert maximal $k$. Implementation mit der Annahme "keine Duplikate im Array": Suche das Objekt mit Schlüsselwert $k$ und gib dessen Index zurück falls gefunden. Wenn festgestellt wird, das $k$ zwischen dem $i$-ten und $i+1$-Element liegen würde, gib den Index $i$ zurück.

Laufzeit der Operationen für sortierte Arrays

Operation	Laufzeit
Seach	$O(\log n)$
Min(Max)	$O(1)$
Predecessor(Successor)	$O(\log n)$
OutputSorted	$O(n)$
Select	$O(1)$
Rank	$O(\log n)$

Schlecht/Nicht unterstütze Operationen des sortierten Arrays

Insert: Füge ein neues Objekt $x$ der Datenstruktur hinzu.

Delete: Für ein gegebenen Schlüssel, lösche das Objekt aus der Datenstruktur mit dem Schlüssel (falls es existiert).

Beachte: Von balacierten Suchbäumen werden diese Operationen dagegen gut unterstützt.

(balancierte) Suchbäume vs. sortierte Arrays

Operation	sortiertes Array	balancierte Suchbäume
Seach	$O(\log n)$	$O(\log n)$
Min(Max)	$O(1)$	$O(\log n)$
Predecessor(Successor)	$O(\log n)$	$O(\log n)$
OutputSorted	$O(n)$	$O(n)$
Select	$O(1)$	$O(\log n)$
Rank	$O(\log n)$	$O(\log n)$
Insert	$O(n)$	$O(\log n)$
Delete	$O(n)$	$O(\log n)$

Wann sollte man einen Suchbaum benutzen?

Wenn die Anwendung eine geordnete Repräsentation einer sich dynamisch ändernden Menge benötigt, ist ein balancierter Suchbaum die geeignete Datenstruktur.

Implementation von (binären) Suchbäumen

Implementation als binärer Suchbaum.

Ziel: Schnelle Suche nach dem Objekt-Schlüssel

Eingenschaft eines binären Suchbaums

1. Für jedes Objekt $x$ haben alle linken Nachfahren, d.h. die Objekte im linken Unterbaum, Schlüsselwerte kleiner als $x$.

2. Für jedes Objekt $x$ haben alle rechten Nachfahren, d.h. die Objekte im rechten Unterbaum, Schlüsselwerte größer als $x$.

# Hier Schlüsselwerte
tree = BinaryTree(nodes=[3, 1, 5, None, 2, 4, None])
tree.plot()

Image(filename='./tree.png') 

Da binäre Bäume beliebige Struktur haben können, werden sie (typischerweise) mit Zeigern zwischen den Knoten implementiert.

Für jeden Knoten wird ein Zeiger zum Parent (Eltern) und zum linken und rechten Child (Kind) gespeichert.

Knoten	Parent	Left	Right
1	3	null	2
2	1	null	null
3	null	1	5
4	5	null	null
5	3	4	null

Höhe(Tiefe) eines (Such-)Baumes

Die Höhe (Tiefe) eines Baums ist die Länge des maximalen Wegs von der Wurzel zu einem Blatt des Baums.

Quiz

Wir groß ist die minimale/maximale Höhe (height) eines Baumes mit $n$-Knoten?

• minimal $\approx \log_2 n$ (bei balancierten Bäumen)
• maximal $n-1$ (Kette)

Implementation der Operationen

Annahme: Alle Schlüssel sind eindeutig. Falls nicht müssen die Operationen/Bäume ggf. leicht modifiziert werden.

Search in $O(\text{height})$

Operation

Search: für einen Schlüssel $k$, gib einen Zeiger zu einem Objekt in der Datenstruktur zurück, das den Schlüssel $k$ hat (oder melde, dass kein solches Objekt existiert).

Implementation

1. Starte beim Wurzel-Knoten
2. Gehe im Baum passend zum Suchschlüssel $k$ nach unten, d.h.
   • nach links, wenn $k$ kleiner als der (laufende) Knotenschlüssel ist.
   • nach rechts, wenn $k$ größer als der (laufende) Knotenschlüssel ist.
3. Gib einen Zeiger zum gefundenen Objekt zurück, das den Schlüssel $k$ hat. Falls kein solches Objekt gefunden wurde, gib einen Null-Zeiger zurück.

Min (Max) in $O(\text{height})$

Semantik der Operation

Min(Max): gib einen Zeiger zu einem Objekt in der Datenstruktur zurück, das den kleinesten (größten) Schlüssel hat.

Implementation

1. Starte beim Wurzel-Knoten
2. Traversiere entlang des linken (rechten) Kind-Zeigers so weit wie möglich (bis ein Null-Zeiger erreicht wird).
3. Gib einen Zeiger zum letzten besuchten Objekt zurück.

Predecessor in $O(\text{height})$

Semantik der Operation

Predecessor(Successor) d.h. Vorgänger(Nachfolger): Für einen Zeiger zu einem Objekt in der Datenstruktur gib einen Zeiger zu einem Objekt zurück, das den nächst-kleineren (nächst-größeren) Schlüssel besitzt. Wenn das gegebene Objekt den kleinsten (größten) Schlüssen hat, gib "none" (z.B. den Nullzeiger) zurück.

Implementation

1. Wenn der linke Unterbaum nicht leer ist: Gib das Ergebnis von Max auf dem linken Unterbaum zurück.
2. Sonst: Traversiere die Parent-Zeiger nach oben maximal bis zum Wurzelknoten. Falls bei der Traversion zwei aufeinanderfolgende Knoten $y$ und $z$ gefunden werden, mit $y$ ist ein rechtes Kind von $z$, gib einen Zeiger zu $z$ zurück.
3. Sonst: Gib einen Nullzeiger zurück, da kein Vorgänger (Predecessor) vorhanden ist.

Analog für Successor.

OutputSorted in $O(n)$

Semantik der Operation

OutputSorted: Gib die Objekte in der Datenstruktur nacheinander aus in der Ordnung Ihrer Schlüssel.

Implementation

Prozedur OutputSorted:

1. Rufe rekursiv OutputSorted auf dem linken Unterbaum auf (beginnend mit dem Wurzelknoten).
2. Gib das Wurzelobjekt zurück.
3. Rufe rekursiv OutputSorted auf dem rechten Unterbaum auf.

Insert in $O(\text{height})$

Semantik der Operation

Insert: Füge ein neues Objekt $x$ der Datenstruktur hinzu.

Implementation

1. Starte beim Wurzel-Knoten

2. Gehe im Baum passend zum Schlüssel $k$ des einzufügenden Objektes $x$ nach unten (wie bei Search) bis ein Null-Zeiger erreicht ist, d.h.

   • nach links, wenn $k$ kleiner als der (laufende) Knotenschlüssel ist.
   • nach rechts, wenn $k$ größer als der (laufende) Knotenschlüssel ist.

3. Ersetze den Null-Zeiger mit einem Zeiger auf den neuen Knoten des einzufügenden Objektes $x$. Setze die Kind-Zeiger des neuen Knotens auf Null-Zeiger.

Delete in $O(\text{height})$

Semantik der Operation

Delete: Für ein gegebenen Schlüssel $k$, lösche das Objekt aus der Datenstruktur mit dem Schlüssel (falls es existiert).

Implementation

1. Nutze Search um einen Knoten (ein Objekt) $x$ mit Schlüssel $k$ zu finden. Falls kein Knoten gefunden wurde, beende die Prozedur.
2. Falls $x$ keine Kinder hat, lösche $x$dadurch indem der Elter-Zeiger zu $x$ durch einen Null-Pointer ersetzt wird. (falls $x$ die Wurzel des Baums war, ist der neue Bau leer.)
3. Falls $x$ ein Kind hat, entferne $x$ und verbinde das Kind von $x$ mit dem Parent von $x$, d.h.
   • setze den Parent-Pointer des Kindes auf den Parent-Pointer von $x$
   • setze den gesetzten Kind-Pointer des Parent von $x$ auf das Kind von $x$.
4. Sonst ($x$ hat zwei Kinder): Vertausche $x$ mit dem Knoten des linkten Unterbaums von $x$ mit dem größten Schlüssel (Predecessor von $x$). Lösche dann $x$ aus dem Baum (jetzt hat es maximal ein Kind).

Rank und Select mit Augmentierung des Baums

Für die Operationen Rank und Select kann man die Knoten des Suchbaums mit dem Metadaten "Anzahl der Knoten des Unterbaumes" (size) erweitern. So können diese auch in $O(height)$ durchgeführt werden. Hierfür müssen die Operationen, die den Baum ändern (wie Insert und Delect) entsprechend erweitert werden.

Aufgabe (in der Übung): Überlegen Sie wie diese Informationen genutzt werden können, um Rank und Select zu implementieren.

Wie kann Rank und Select durchgeführt werden, wenn die Information size ("Anzahl der Knoten des Unterbaumes") an jedem Knoten des Baums vorhanden ist?

Implementation von balanchierten Suchbäumen

Die Höhe eines Baums bestimmt die Laufzeit der Operationen. Im Idealfall ist die Höhe $\log (n)$. Durch Ausbalancieren kann dieser Ideallfall angenähert/erreicht werden.

Beispiele für solche ausbalancierten Bäume sind:

• B-Trees
• Red-Black Trees

Die gängigste Technik zum Ausbalancieren ist Rotation, siehe [Rough2] Für weitere Implementierungsdetails siehe z.B. [Corman]

Literatur

• [Corman] Introduction to Algorithms von T. Corman, C. Leiserson, R. Rivest und C. Stein, second edition, MIT Press.

• [Rough2] T. Roughgarden, Algorithms Illuminated, Part 1: The Basics

Kontakt/Impressum