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