Programmieren, Algorithmen und Datenstrukturen 2 (Vorlesung 17)

Fortgeschrittenes Suchen

• Für die Algorithmenanalyse ist oft der durchschnittliche Fall am wichtigsten
• Stirling-Zahl (1. Art)
  • Anzahl der Permutationen einer n-elementigen Menge, die genau k Zyklen haben (Wikipedia)

Bäume

→ Mathematische Struktur, Graph

• Knoten
  • sind miteinander verbunden
  • haben
• Kanten
• Pfad
  • Weg von einem Knoten zu einem anderen über eine oder mehrere Kanten
  • In einem Baum gibt es immer genau einen Pfad
  • Kanten sind zunächst ungerichtet

Wurzelbaum

• Knoten sind als Wurzel gekennzeichnet
  • Gegenteil: freier Baum
• Kanten zeigen zur Wurzel oder von ihr weg (es kann auch beides der Fall sein)
  • Kanten sind gerichtet
• Die Wurzel befindet sich oben
  • ein Knoten y liegt über dem Knoten x, wenn er sich näher an der Wurzel befindet
• Jeder Knoten bildet die Wurzel für einen weiteren Teilbaum
• Jeder Knoten, der nicht die Wurzel ist, hat einen Vorgänger (Knoten direkt über ihm) und Nachfolger (Knoten direkt unter ihm)
• Knoten ohne Nachfolger heißen Blätter

• Knotenebene
  • Ebene der Wurzel ist „0“
  • Ebene ist der Abstand vom Knoten zur Wurzel
• Pfadlänge
  • Summer aller Ebenen
• Höhe eines Wurzelbaums
  • Die höchste Ebene unter allen Knoten

Geordneter Baum

• Reihenfolge der Nachfolger jedes Knotens ist systematisch festgelegt

M-wertiger Baum

• Jeder Knoten muss eine bestimmte Anzahl „M“ von Nachfolgern haben
• Pseudoknoten, äußerer Knoten
  • werden als Nachfolger von Knoten gesetzt, die keine „M“ Nachfolger haben
  • werden im Vergleich zu den runden „inneren“ Knoten eckig dargesetellt
• Nullkanten
  • Kanten zu Pseudoknoten
• Blätter haben nur Pseudoknoten als Nachfolger

Binärbaum

• geordneter M-wertiger Baum mit M=2
• 2 Typen von Knoten:
  • Äußere Knoten
  • Innere Knoten
• geordnet
  • linker Nachfolger
  • rechter Nachfolger
  • jeder Knoten hat genau 2 Nachfolger
• Blätter haben 2 äußere Knoten als Nachfolger
• äußere Pfadlänge
  • Summe der Ebenen aller äußeren Knoten
• innere Pfadlänge
  • Summe der Ebenen aller inneren Knoten

Die Implementierung eines Binärbaums in C++ sieht wie folgt aus:

struct node { char c; node* left; node* right; }

• Ein Binärbaum von N Knoten hat N-1 Kanten
• Ein Binärbaum von N inneren Knoten hat N+1 äußere Knoten
• Ein Binärbaum mit N inneren Knoten hat 2N Kanten
• Die äußere Pfadlänge eimes Binärbaums mit N inneren Knoten ist um 2N größer als seine innere Pfadlänge
• Die Höhe eines Binärbaums mit N inneren Knoten beträgt
  • mindestens log2 (N)
  • höchstens N
• Die innere Pfadlänge eines Binärbaums mit N inneren Knoten beträgt mindestens log2 (N/4) und höchstens N (N-1) / 2