Trees

Agenda

• Intro
• Binary Tree
• Binary Search Tree
• Heap (Optional)

Intro

Was ist ein Tree?

Ein Tree (Baum) ist eine hierarchische Datenstruktur. Dies ermöglicht eine effiziente Navigation und Suche durch den Baum.

Es handelt sich um eine Sammlung von Knoten, die durch Kanten verbunden sind und eine hierarchische Beziehung zwischen den Knoten aufweisen.

Beispiel Baum

Begriffe I

• Root Node
• Child Node
• Parent Node
• Leaf Node
• Level

Begriffe II

• Ancestor Node
• Descendant Node
• Sibling
• Neighbor
• Subtree

Anwendungen von Bäumen

• Dateisystem → ls -la | dir
• DOM → F12
• Abstract Syntax Tree

Arten

• Binary tree (Binärbaum)
• Ternary tree (Ternärer Baum)
• Quadtree (Quaternärbaum)
• N-Tree/Generic Tree

Trees vs Arrays vs Lists

• Access Time: Arrays < Tree < LinkedList
• Modify Time: LinkedList < Tree < Array
• Space Limit: LinkedList & Tree > Array

Binary Tree

Was ist ein Binary Tree?

Bei einem Binary Tree kann jeder Node maximal zwei Child Nodes haben. Sie werden als left und right bezeichnet.

Node Struktur

public class Node {
  public int number;
  public Node left;
  public Node right;
}

ähnlich wie Linked List

Binary Tree Eigenschaften

• 0 bis 2 Knoten
• Keine Ordnung innerhalb des Baumes

Binary Tree Operationen

• traverse → alle Elemente besuchen
• insert → Element hinzufügen
• delete → Element entfernen
• search → Element suchen

Tree Traversals

• Depth First Search
• Breadth First Search

Depth First Search (DFS)

• Pre-Order-Traversal
• In-Order-Traversal
• Post-Order-Traversal

Beispiel Tafel: 7, 23, 3, 5, 4, 18, 21

Demo - Binary Tree DFS

Welche Datenstruktur haben wir implizit benutzt?

Breadth First Search (BFS)

• Gegenteil von DFS
• Beispiel Tafel

Welche Datenstruktur werden wir nutzen?

Demo - Binary Tree BFS

Vergleichen von Binary Trees

• Werte
• Struktur

Compare Beispiel: 1, 4, 9 an der Tafel BFS & DFS

DFS bewahrt die Struktur des Baumes

Demo - Binary Tree Compare DFS

Binary Search Tree

Was ist ein Binary Search Tree (BST)?

• Binary Tree mit Sortierung
• Left <= Node
• Node < Right

Beispiel: BST an der Tafel 17, 15, 50, 4, 16, 25, 21, 30

BST Operationen

• Search
• Insert
• Delete

Demo - Binary Search Tree

Heap

Was ist ein Heap?

• Binary Tree mit schwacher Sortierung
• jeder Nachfolger ist kleiner (MaxHeap)
• jeder Nachfolger ist größer (MinHeap)

Beispiel: MinHeap an der Tafel 50, 71, 100, 101, 80, 200, 101

Heap Eigenschaften

• Nennt man auch Priotity Queue
• Kein Traversieren
• Root ist immer Max/Min

Heap Operationen

• insert → Baum anpassen
• delete → Baum anpassen

Heap Insert

1. Am Ende einfügen
2. nach oben verschieben

Beispiel: Insert 3

Heap Delete

1. root zwischenspeichern
2. letztes Element mit root tauschen
3. nach unten verschieben

Beispiel: Delete

Heap Probleme

• Wie kommen wir an das Ende?
• Wie bekommen wir Parent?
• Wie bekommen wir Childs?

Array to the rescue!

Demo - Heap