IT – Bäume

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

 

Eine Antwort auf „IT – Bäume“

Kommentar verfassen