Allgemeines
- Kante, die von Knoten A nach Knoten B geht
- A – Vater ( Vorgänger, parent )
- B – Sohn ( Kind, child )
- Zwei Knoten vom selben Vater – Brüder ( siblings, Geschwister )
- Grad eines Knotens – Anzahl direkter Nachfolger
- Grad eines Baumes – max. Knotengrad aller Knoten
- Blätter – Knoten vom Grad 0
- innere Knoten Grad > 0
- jeder Knoten hat genau 1 Vorgänger
- Stufe eines Knotens – Pfadlänge von der Wurzel
Wurzel – Stufe 0
Knoten – Stufe des direkten Vorgängers K + 1 - Höhe h – max. Stufen der Baumknoten + 1
- Gewicht w – Anzahl aller Blätter
- Menge mehrerer Bäume – Wald
Wurzel W
Blätter G, B, A, L, Q, F, I
Innere Knoten G, B, W
Höhe max. Stufe + 1, h = 4
Binärbaum
- endliche Menge von Elementen
- ist entweder leer oder hat ausgezeichnetes Element (Wurzel)
- außerdem
- übrige Elemente in 2 disjunkte Untermengen zerlegbar
- Untermengen sind selbst Binärbäume
Binärbäume mit disjunkten Untermengen
links iO – rechts nicht iO, da B weder als linkes noch als rechtes Kind erkennbar ist
Untermengen sind nicht disjunkt
B und C haben gleiche Untermenge E
Spezielle Binärbäume
- ähnlich – selbe Struktur
- äquivalent – selbe Struktur und selbe Information
- vollständig
- jeder Knoten der Stufe h-1 ist ein Blatt
- jeder Knoten der Stufe < h-1 hat nicht leere linke und rechte Unterbäume
- max. Anzahl Knoten auf Stufe k ist 2k ( 0 ≤ k ≤ h – 1 )
- max. Anzahl Knoten bei Höhe h ist 2h– 1 ( h ≥ 1 )
- strikt – jeder innere Knoten besitzt nicht-leere linke & rechte Unterbäume
- ausgeglichen, wenn für alle k ≥ 0 gilt:
- jedes Blatt ist auf Stufe k oder k + 1
- jeder Knoten auf Stufe < k hat nicht-leere linke & rechte Unterbäume
- fast vollständig, wenn für für alle k ≥ 0 gilt:
- jedes Blatt ist auf Stufe k oder k + 1
- jeder Knoten auf Stufe < k hat nicht-leere linke & rechte Unterbäume
- falls innerer Knoten Nachfolger (nicht direkter Nachfolger) auf Stufe k + 1 besitzt,
dann ist linker Unterbaum vollständig mit Blättern Stufe k + 1
strikt
ausgeglichen
ausgeglichen
strikt
ausgeglichen
fast vollständig
[…] unter Bäume (ungerichteter, azyklischer, zusammenhängender Graph) September 28th, 2011 in IT, Studium | tags: […]