Algorithmen und Datenstrukturen
Im folgenden Themenbereich geht es um Algorithmen und Datenstrukturen und um die Landau Symbole oder O - Notation und wie diese im Kontext von Algorithmen und Datenstrukturen verwendet werden.
Bei den Alghorithmen werden wir uns auf Sortieralgorithmen beschränken und uns mit deren Laufzeitanalyse (und der daraus resultierenden O - Notation) befassen.
Bei den Datenstrukturen beschränken wir uns auf Arrays, Listen und Bäume und ebenfalls um deren Laufzeitanalyse für verschiedene Operationen.
Landau Symbole oder O - Notation
Landau-Symbole (auch O-Notation) werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an [1].
Unter asymptotischem Verhalten verstehen wir hier das Grenzverhalten eines Algorithmus, vereinfacht gesagt, wie kann sich die Laufzeit im schlechtesten Fall entwickeln. Um das Grenzverhalten eines Algorithmus zu betrachten, analysieren wir wieviele Operationen im schlechtesten Fall in Bezug auf die größe des Problems (z.B.: Anzahl der Elemente) benötigt wird. Konstante Werte können dabei vernachlässigt werden (z.B.: eine Schleife muss 2 mal durchlaufen werden. Dieser Wert ist eine Konstante da sie unabhängig von der Anzahl der Elemente ist, es wird also immer 2 mal durchlaufen).
Beispiel
Suchen des kleinsten und größten Elements in einem Array.
| 1 | 2 | 3 | 4 | 5 | 6 |
Um das größte Element zu finden, werden 5 Schritte benötigt, dies entspricht der Länge des Arrays - 1. Für die Suche des größten Elements benötigen wir ebenfalls 5 Schritte. Somit ist die Laufzeit des Algorithmus 2 * (n - 1). Die Konstanten werden entfernt, somit bleibt: O(n)
public void findMinAndMax(int[] arr) {
int min = arr[0];
int max = arr[0];
for(int i=1; i<arr.length; i++) {
min = Math.min(min, arr[i]);
}
for(int i=1; i<arr.length; i++) {
max = Math.max(max, arr[i]);
}
System.out.println("Min: "+min);
System.out.println("Max: "+max);
}
In der O - Notation werden einige gebräuchliche Schranken verwendet, wenn wir einen Algorithmus oder eine Datenstruktur analysieren, verwenden wir diese Schranken und nicht die exakte Mathematische repräsentation des Problems, auch wenn dies möglich wäre (siehe Bubblesort)
| O - Notation | Bedeutung | Beispiel |
|---|---|---|
| O(1) | Das Laufzeitverhalten hängt nicht von der Anzahl der Elemente ab und ist konstant | Element an der Stelle N aus einem Array oder einer ArrayListe holen |
| O(n) | Das Laufzeitverhalten verlängert sich linear mit der Anzahl der Element | Suchen eines bestimmten Elements in einem unsortierten Array |
| O(n log n) | Super lineares Wachstum :-DDD | Mergesort, Heapsort, Durchschnittsfall Quicksort |
| O(n2) | Quadratisches Wachstum, die Laufzeit wächst quadratisch zur Anzahl der Elemente | Bubblesort |
| O(log2n) | 2er Logarithmisches Wachstum | Suche im balancierten Binärbaum |
Datenstrukturen
In der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt, welches zur Speicherung und Organisation von Daten dient. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung effizient zu ermöglichen [2]. Im folgenden sollen einige Datenstrukturen erläutert werden, für jede Datenstruktur gibt es andere Einsatzgebiete die für deren Eigenschaften optimal sind.
Array
Ein Array oder Feld ist eine sehr effiziente doch wenig dynamische Datenstruktur. In nahezu allen Programmiersprachen findet sich diese Datenstruktur wieder. Weiter ist auch ein dynamisches vergrößern oder verkleinern in einigen Programmiersprachen automatisch implementiert (z.B.: Javascript).
Gehen wir jedoch von Programmiersprachen wie Java oder C aus, so hat ein Array immer eine fixe Größe. Das heißt, zur Laufzeit (nach dem das Programm compiliert und gestartet wurde) kann diese nicht verändert werden.
Vorteile
- Der Speicheroverhead ist sehr gering - Es wird nur der Speicher benötigt, der für die Anzahl der Elemente benötigt wird.
- Geringe Zugriffszeit - Wird ein Element an einer Stelle angesprochen, so kann für den Zugriff die exakte Speicheradresse berechnet werden.
Nachteile
- Wenig flexibel - Wie bereits erwähnt, muss die Größe meist fix definiert werden. Eine Vergrößerung/Verkleinerung ist nicht möglich, ermöglicht die Programmiersprache dies, so hat dies zur Folge, dass das Array neu erstellt wird, und die Elemente kopiert werden müssen.
Einsatzgebiete
Überall dort, wo eine fixe Speichergröße benötigt und Effizienz wichtig ist, dort sollte die Verwendung von Arrays in Betracht gezogen werden.
- Bildmanipulation - Wird ein Bild zur Bearbeitung geladen, so kann die Bitmap in einem Array gespeichert werden. jedes Element im Array entspricht dann einem Pixel.
- Puffern von Daten - Beim Lesen und Schreiben werden Daten meist in einem Array zwischengespeichert (gepuffert). Danach kann die Bearbeitung erfolgen. Weiters kann bei jedem Lese oder Schreibvorgang erneut das selbe Array verwendet werden, was die Effizienz weiter erhöht. Für solche Operationen wird meist eine fixe Puffergröße verwendet, deswegen eignet sich das Array hierfür.
- Jegliches schachbrettartige Problem mit fixer Größe - Schiffe versenken, Schach,...
Liste
Die Liste ist eine sehr gebräuchliche Datenstruktur. Sie ist gekennzeichnet durch, je nach implementierung, gute Zugriffszeiten oder erhöhte Flexibilität.
Beziehen wir uns auf die Programmiersprache Java, so ist die Liste ein Interface, also eine Schnittstelle. Diese Schnittstelle definiert einige Methoden die eine Implementierung erfüllen muss. Einige davon wären:
E get(int index)- Gibt das Element an der Stelle index ausE remove(int index)- Löscht das Element an der Stelle indexboolean add(E element)- Fügt ein Element an das Ende der Liste hinzuboolean add(int index, E element)- Fügt ein Element an einer bestimmten Position ein, und schiebt nachfolgende Elemente nach rechts- ...
Hier ist nun ersichtlich, dass die Flexibilität der Liste ein essenzieller Bestandteil der Definition ist.
Anbei einige Implementierungen des Interfaces List.
ArrayList
Die ArrayList vereint die Eigenschaften einer Liste und eines . Die interne Implementierung verwendet ein von fixer Größe um Elemente zu speichern. Wird diese fixe Größe überschritten, so wird intern ein neues angelegt, je nach Implementierung mit einem gewissen Vergrößerungsfaktor. Nach dem Neuanlegen des internen , werden alle Elemente kopiert und in das neue eingefügt. Wird ein Element gelöscht oder an einer Stelle eingefügt, so müssen bestehende Elemente verschoben werden.
In Java wird die größe des internen Arrays nicht automatisch reduziert, wenn Elemente gelöscht werden. Dafür gibt es die Methode myArrayList.trim()
Vorteile
- Relativ geringer Speicheroverhead - Dies verhält sich ähnlich wie beim . Jedoch können in der ArrayList keine primitiven Datentypen gespeichert werden, sondern nur Objekte von . Dies bedeutet, es wird nur ein von Referenzen erstellt. In jedem Platz findet sich eine Referenz auf das wirkliche Objekt. Dies bedeutet in Bezug auf primitive Datentypen einen weit höheren Speicherbedarf als bei einem Array.
- Geringe Zugriffszeit - Wird ein Element an einer Stelle angesprochen, so kann für den Zugriff die exakte Speicheradresse berechnet werden.
Nachteile
- Ineffizientes Löschen - Laufzeit beim Löschen nicht optimal, Elemente müssen verschoben werden.
- Ineffizientes Einfügen - Laufzeit beim Einfügen von Elementen an einer gewissen Stelle langsam, wie beim löschen müssen alle nachfolgenden Elemente verschoben werden.
- Ineffizientes Hinzufügen, wenn internes voll - Laufzeit beim Hinzufügen von Elementen bei vollem langsam, ein neues muss erstellt und alle Elemente müssen in das neue kopiert werden
Code beispiel
List<Integer> myArrayList = new ArrayList<>();
myArrayList.add(1);
myArrayList.add(1);
myArrayList.add(1);
myArrayList.remove(0);
System.out.println("Element an der Stelle 2: "+myArrayList.get(1));
- Zeile 1) Die
ArrayListwird erzeugt und einer Variable des TypsListzugewiesen. Warum ist das möglich? WeilArrayListdas InterfaceListimplementiert. D.h.: EineArrayListist eineList. - Zeile 2) - 4) fügen der
ArrayListeinen int hinzu. Hier ist zu beachten, der primitive Datentyp int wird automatisch in die Klassejava.lang.Integerumgewandelt. Dieser mechanismus nennt sich Autoboxing. - Zeile 5) Das Element an der Stelle 0 wird aus der
ArrayListentfernt - Zeile 6) Ausgabe des Elements an der Stelle 2 (Index 1)
Einsatzgebiete
Die Einsatzgebiete überschneiden sich mit herkömmlichen Arrays. Benötigt man mehr flexibilität und soll nicht mit primitiven Datentypen gearbeitet werden, so kann anstatt eines Arrays die ArrayListe verwendet werden. Ist die Anzahl der Elemente start fluktuierend (oftmaliges löschen/einfügen/hinzufügen), so sollte man aus oben genannten Gründen auf eine andere Datenstruktur ausweichen.
LinkedList oder verkettete Liste
Die verkettete Liste ist eine sehr dynamische Datenstruktur. Ihre Größe ist flexibel. Die Daten werden in Knoten gehalten, welche im Falle der einfach verketteten Liste auf den Nachfolger und bei der doppelt verketteten Liste zusätzlich auf den Vorgänger Knoten zeigen. Elemente können einfach an bestimmten Stellen eingefügt oder gelöscht werden, es müssen lediglich die Nachfolger bzw. Vorgänger aktualisiert werden.
Vorteile
- Einfügen und Löschen effizient - Es müssen lediglich die Zeiger auf den Vorgänger/Nachfolger geändert werden.
- Speicherbedarf flexibel - Der Speicherbedarf wächst und schrumpft mit der Anzahl der Elemente.
Nachteile
- Zufälliger Zugriff langsam - Werden in der LinkedList Elemente mit ihrem Index angesprochen, so muss zuerst die komplette Liste bis zum entsprechenden Index durchlaufen werden.
- Speicheroverhead - Da die Daten in Knoten gespeichert werden müssen entsteht automatisch ein Speicheroverhead für die Datenstruktur des Knoten.
Einsatzgebiete
- Wenn die größe der Liste stark variiert, d.h. oftmals Elemente eingefügt, gelöscht und hinzugefügt werden und kein zufälliger Zugriff benötigt wird.
Code Beispiel
Datenstruktur Node selbst:
public class Node {
private Integer value;
private Node next;
public Node(Integer value) {
this.value = value;
}
public void setNext(Node next) {
this.next = next;
}
public Node next();
return this.next;
}
public Integer getValue() {
return this.value;
}
}
Hinzufügen eines Elements
public boolean add(Integer element) {
Node newNode = new Node(element);
if(root == null) {
root = newNode;
} else {
Node current = root;
while(current.next() != null) {
current = current.next();
}
current.setNext(newNode);
}
return true;
}
Holen eines Elements
public int get(int index) {
Node current = root;
for(int i=0; i<index && current != null; i++) {
current = current.next();
}
if(current == null) {
throw new IndexOutOfBoundsException();
}
return current.getValue();
}
Assoziativer Speicher
Der assoziative Speicher oder auch Map, oder assoziatives Array, ist eine Sammlung von Key, Value Paaren. Sie eignet sich sehr gut dafür, für einen bestimmten Schlüssel einen Wert zu hinterlegen. Die Operationen, einfügen, löschen, abrufen, sind Konstant und weisen im Normalfall ein Laufzeitverhalten von O(1) auf. Die Reihenfolge der Element ist nicht definiert.
Map<String, Integer> nameAgeMap = new HashMap<String, Integer>();
//Speichern in Map: Key = Luke, Value = 35
nameAgeMap.put("Luke", 35);
//Holen aus der Map mit dem Key = Luke
System.out.println(nameAgeMap.get("Luke"));
Bäume
Bäume sind Datenstrukturen, welche im Kontext von Suchstrukturen, automatisch einer gewissen Ordnung folgen. Bereits nach dem Einfügen sind diese Element sortiert.
Es gibt eine Vielzahl verschiedener Baumstrukturen, die sich in ihren Eigenschaften unterscheiden:
- Binärbaum oder Binärer Suchbaum
- AVL Baum
- Rot schwarz baum
- B*Baum
- ...
Elemente eines Baums
Betrachten wir die folgende Grafik, so können wir die Elemente leicht identifizieren. Weiters ist zu beachten, Bäume in der Informatik werden meist mit der Wurzel ganz oben dargestellt, nicht wie im echten Leben. Weiters wächst auch der Baum nach unten.
- Wurzel - Das erste Element im Baum
- Blatt oder äußerer Knoten - Knoten ganz außen ohne Nachkommen
- Innerer Knoten - Knoten dazwischen
Eigenschaften eines Baums
Im folgenden betrachten wir zwei verschiedene Eigenschaften von Bäumen, die Höhe und die Balance.
Höhe eines Baumes
Die höhe des Baumes ist die maximal auftretende Tiefe, also wieviele Element wächst der Baum nach unten. Somit hätte ein Baum mit nur einer Wurzel die Höhe von 0, das heißt er wächst 0 Ebenen nach unten. In der Graphentheorie ist eine Zuordnung der Höhe, nur auf nichtleere Bäume definiert.
Teilweise wird die Höhe auch um 1 erhöht, damit ein leerer Baum die Höhe 0 hat und ein Baum mit nur einer Wurzel die Höhe 1. Das soll uns aber jetzt nicht weiter beschäftigen.
Folgende Grafik illustriert wie die Höhe eines Baumes bestimmt wird.
Balance
Ob ein Binärer Suchbaum balanciert ist oder nicht, ist entscheidend für die Laufzeit der binären Suche.
Ein Baum ist balanciert wenn sich die Höhe aller Teilbäume nicht mehr als um einen gewissen Wert unterscheidet. Bei z.b.: AVL Bäumen darf die Höhendifferenz maximal 1 betragen, dies können wir auch für den Binärbaum annehmen
Um die Balance zu bestimmen, müssen wir alle Teilbäume betrachten, wir gehen den Baum von Unten nach Oben durch und schreiben zu jedem Knoten die Differenz der Höhe des linken und rechten Teilbaums. Folgende Grafik sollte das recht gut illustrieren.
Die Balance jedes Baumes (bzw. Teilbaumes) wird wie folgt berechnet: die Länge des rechten Teilbaumes Minus die Länge des linken Teilbaumes. Umso näher die Balance bei 0 ist, desto besser ausbalanciert ist der Baum. Philipp
Ist ein Baum nicht balanciert, so wächst die Suche nach einem Element, je nach grad der Entartung, bis zur Laufzeit O(n). Das ist die selbe Laufzeit wie bei der linearen Suche in einem Array oder einer Liste.
| Knoten | Linker Teilbaum | Rechter Teilbaum | Balance |
|---|---|---|---|
| C | C -> 0 | C -> 0 | 0 - 0 -> 0 |
| D | D - C -> 1 | D -> 0 | 0 - 1 -> -1 |
| F | F - D - C -> 2 | F - G -> 1 | 1 - 2 -> -1 |
| J | J - F - D - C -> 3 | J - P - V - S - Q -> 4 | 4 - 3 -> 1 |
Suche in einem Binärbaum
Das Laufzeitverhalten der Suche in einem Binärbaum entspricht immer seiner Höhe (je nach Höhendefinition + 1). Betrachten wir folgendes Beispiel:
- Die Höhe des Baumes beträgt 4, somit sind 5 Operationen nötig
- Wir suchen nach U
- Die Vergleiche und die Navigation fassen wir als eine Operation zusammen
- Vergleich mit J, P, V, S und zu guter letzt U
Die Höhe eines balancierten Baumes können wir vereinfacht mit log2(n) annehmen. Somit ist der Aufwand unserer Suche O(log2(n))
Code Beispiele
Sortierte Ausgabe eines binären Suchbaums (In-Order)
public void printInOrder() {
print(root);
}
public void printInOrder(Node node) {
if(node == null) {
return;
}
//Rekursiver Aufruf für den Linken Teilbaum
print(node.getLeft());
//Ausgabe des aktuellen Wertes
System.out.print(" "+node.getValue()+" ");
//Rekursiver Aufruf für den Linken Teilbaum
print(node.getRight());
}
Einfügen eines Elements
public void add(int value) {
add(root, new Node(value));
}
private void add(Node node, Node newNode) {
if(root == null) {
root = newNode;
return;
}
if(node.getValue() < newNode.getValue()) {
if(node.getLeft() == null) {
node.setLeft(newNode);
} else {
add(node.getLeft(), newNode);
}
} else {
if(node.getRight() == null) {
node.setRight(newNode);
} else {
add(node.getRight(), newNode);
}
}
}
Finden eines Elements
public boolean contains(int value) {
return contains(root, value);
}
private void contains(Node node, int value) {
if(node == null) {
return false;
}
if(node.getValue() == value) {
return true;
} else if(node.getValue() < value) {
return contains(node.getLeft(), value);
} else {
return contains(node.getRight(), value);
}
}
O Notation
Hier findet sich die O - Notation für einige gebräuchliche Operationen und dessen Erklärung. Man beachte, es muss immer vom schlechtesten Fall ausgegangen werden.
| Datenstruktur | O - Notation | Begründung |
|---|---|---|
| LinkedList | O(n) | Liste muss bis zum gewünschten Index durchlaufen werden |
| ArrayList | O(1) | Index kann berechnet werden |
| Array | O(1) | Index kann berechnet werden |
| Datenstruktur | O - Notation | Begründung |
|---|---|---|
| LinkedList | O(n) | Liste muss bis zum gewünschten Index durchlaufen werden, das Löschen selbst hat eine konstante Laufzeit, es müssen nur die Verknüpfungen aktualisiert werden |
| ArrayList | O(n) | Element kann direkt durch berechnung des Index gelöscht werden, jedoch müssen alle Nachfolgenden Elemente nach links verschoben werden |
| Array | O(n) | Element kann direkt durch berechnung des Index gelöscht werden, jedoch müssen alle Nachfolgenden Elemente nach links verschoben werden |
| Datenstruktur | O - Notation | Begründung |
|---|---|---|
| LinkedList | O(n) | Liste muss bis zum gewünschten Index durchlaufen werden, das Einfügen selbst hat eine konstante Laufzeit, ein neuer Knoten wird erstellt und die Verknüpfungen werden aktualisiert |
| ArrayList | O(n) | Element kann direkt durch berechnung des Index eingefügt werden, jedoch müssen alle Elemente ab diesem Index nach rechts verschoben werden |
| Array | O(n) | Element kann direkt durch berechnung des Index eingefügt werden, jedoch müssen alle Elemente ab diesem Index nach rechts verschoben werden |
Sortieralgorithmen
Sortieralgorithmen werden benötigt um Datenstrukturen nach gewissen Kriterien zu sortieren. Dazu müssen die Elemente natürlich vergleichbar sein, d.h. es muss möglich sein herauszufinden ob ein Element "größer" oder "kleiner" als ein anderes ist.
Eigenschaften
Sortieralgorithmen können über mehrere Eigenschaften verfügen.
In-Place
Das bedeutet der Sortieralgorithmus benötigt "keinen" weiteren Speicherplatz beim sortieren, bzw. wenn der Speicherbedarf konstant ist, und nicht mit der Anzahl der Elemente wächst. Z.b. der Sortieralgorithmus Mergesort, teilt die Daten der bestehenden Liste in Sublisten auf, er ist somit nicht In-Place.
Stabil
Ein Sortieralgorithmus arbeitet stabil, wenn dieser eine bestehende korrekte Ordnung nicht verändert.
Bubblesort
Bubblesort ist ein vergleichsweise akademischer Algorithmus. Er ist wenig effizient, arbeitet jedoch Stabil und In-Place. Folgende Grafik illustriert die Funktionsweise, man beachte dass bei jedem Durchlauf die Anzahl der Vergleiche um 1 abnimmt, da beim letzten Vergleich immer die höchste Zahl ganz rechts steht. Weiters kann die Sortierung abgebrochen werden, wenn in einem Durchlauf keine Zahl vertauscht wurde.
Code
Bubblesort in Java
public class Bubblesort {
public static void sort(int[] arr) {
int operations = 0;
int n = arr.length;
boolean swapped = false;
do {
swapped = false;
for (int i = 0; i < n - 1; i++) {
operations++;
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
// Letztes Element ist an der richtigen stelle, n um 1 reduzieren
n = n - 1;
} while (swapped);
System.out.println("Operations: " + operations);
}
public static void main(String[] args) {
int[] arr = new int[] { 1, 2, 3, 4, 5, 6 };
sort(arr);
arr = new int[] { 6, 5, 4, 3, 2, 1 };
sort(arr);
arr = new int[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
sort(arr);
}
}
Laufzeitanalyse
Für die Laufzeitanalyse verwenden wir die maximal mögliche Laufzeit. Betrachten wir hierfür folgendes Array: 10,8,5,3,2,1
- 1) Durchlauf: Die Zahl 10 wird mit 8,5,3,2 und 1 verglichen und vertauscht.
- 2) Durchlauf: Die Zahl 8 wird mit 5,3,2 und 1 verglichen und vertauscht, mit 10 muss nichtmehr verglichen werden.
- 3) Durchlauf: Die Zahl 5 wird mit 3,2 und 1 verglichen und vertauscht, mit 10, 8 muss nichtmehr verglichen werden.
- 4) Durchlauf: Die Zahl 3 wird mit 2 und 1 verglichen und vertauscht, mit 10, 8, 5 muss nichtmehr verglichen werden.
- 5) Durchlauf: Die Zahl 2 wird mit 1 verglichen und vertauscht, mit 10, 8, 5, 3 muss nichtmehr verglichen werden.
- Ende, die Zahl 1 muss nichtmehr verglichen werden.
Vergleichen und vertauschen betrachten wir nun als eine Operation.
- 1) Durchlauf -> 5 Operationen
- 2) Durchlauf -> 4 Operationen
- 3) Durchlauf -> 3 Operationen
- 4) Durchlauf -> 2 Operationen
- 5) Durchlauf -> 1 Operation
Das sind für ein Array der Länge 6, 15 Operationen.
Die allgemeine Formel lautet
- 1) (n-1) + (n-2) + ... 1
- 2) Das ist ja der kleine Gauß minus n: (n * (n + 1))/2 - n
- 3) (n * (n + 1))/2 - (2*n)/2
- 4) (n2 + n - 2*n)/2
- 5) (n2 - n)/2
- 6) 1/2*(n2 - n)
- 7) n2 - n -> Konstante Werte werden bei der O - Notation entfernt
- 8) n2 -> n ist zu n2 vernachlässigbar und wird entfernt
Laufzeit
Somit ist die Laufzeit von Bubblesort O(n2)
Laufzeit Bestcase
Liegt bereits eine sortierte Liste vor, so benötigt Bubblesort nur einen Durchlauf. Dabei erfolgen n - 1 vergleiche. Die Konstante wird entfernt.
Die Laufzeit im Bestcase ist O(n)
- ↑ https://de.wikipedia.org/wiki/Landau-Symbole
- ↑ https://de.wikipedia.org/wiki/Datenstruktur
- ↑ https://beginnersbook.com/2013/12/java-arraylist/
- ↑ https://www.java67.com/2016/01/how-to-implement-singly-linked-list-in-java-using-generics-example.html
- ↑ https://www1.pub.informatik.uni-wuerzburg.de/databases/Binaere_Suchbaeume/avl_trees/properties/height.html
- ↑ https://de.wikipedia.org/wiki/Balancierter_Baum