The Binary Tree

Die Bezeichnung "Binary Tree" hängt von seiner Datenstruktur ab. Er ist aufgebaut wie ein Baum mit Wurzel (Root=Ursprungsknoten), Zweigen (Nodes) und Blättern (Leafs= Nodes ohne Childnodes). Ein guter Vergleich ist ein Familien-Stammbaum. Der "Binary" Tree steht für Trees mit zwei Childnodes und der "Ternary" Tree für Trees mit drei Childnodes. Wir nutzen Trees für die Repräsentation von Daten in hierarchischen/ geordneten Strukturen. So beispielsweise für Datenbanken (trees for indexing), für Autocompletion(z.B. in Chrome, vergangene Websuchen), für Compilers (Syntax tree to parse expressions) oder für Compressions (JPEG, MP3).

Es wird zwischen "Binary Trees" und "Binary Search Trees" unterschieden. Bei "Binary Search Trees" sind die Knoten wie folgt geordnet: left< node< right
Das bedeutet, der linke Childnode ist in der Struktur immer kleiner als der Parentnode, welcher wiederum kleiner als der rechte Knoten ist.

Dadurch eigenen sich Binary Search Trees, wie der Name es schon vermuten lässt, ausgezeichnet für das finden von Werten.

Ablauf:
1. Wir suchen nach dem Wert 1
2. Ist 1 kleiner oder größer als der Root-Node?
3. Ja? -> also schauen wir den linken Subtree an
4. Dort wird der oberste Knoten angeschaut und wieder kommt die Frage: ist er der Knoten kleiner oder größer?
5. Das geht so lange, bis wir den Wert schließlich gefunden haben. Durch diese Vorgehensweise, konnten wir bereits zu Beginn der Suche die Hälfte der Suchoptionen ausschließen.

In linearen Datenstrukturen, wie z.B. der Linked List, gibt es eine klare Richtung zum Durchlaufen der Struktur. Bei Trees gibt es unterschiedliche Wege.

BREADTH FIRST/ LEVEL ORDER:
• Das etagenweise Durchlaufen, Level für Level...

DEPTH FIRST:
• Pre-Order (Root, Left, Right): In die Tiefe gehend. Erst der Elternknoten, dann alle seine linken Kindknoten und erst danach der rechte Subtree.
• In-Order (Left, Root, Right): Ausgabe der Werte in aufsteigender Reihenfolge. Wenn wir in absteigender Reihenfolge ausgeben wollen, dann: Right, Root, Left.
• Post-Order (Left, Right, Root): Wir gehen von den Blättern hoch zur Wurzel. Praktisch in Usecases, wo wir die Werte berechnen und sie hochspielen müssen bis zur Wurzel. Diese Bäume können mit "Rekursion" sehr einfach im Code nachgebildet werden.

ERMITTELN DER TIEFE & HÖHE VON TREES:
• Tiefe: Kann durch das Zählen der Edges ausgewiesen werden.
• Höhe: Kann durch das Zählen, vom untersten Blatt ausgehend, ausgewiesen werden.
  Height of Root-Node = Height of the Tree
  Formel: 1+ max(height(L), height(R))