< Liste Inhalt

Bäume

Bäume sind in der Informatik hierarchische Datenstrukturen.
Die Elemente in einem Baum heißen Knoten und die Verbindungen nennt man Kanten.

Benennung

Den obersten Knoten in einem Baum nennt man Wurzel.
Eine Kante verbindet genau zwei Knoten, den oberen Knoten nennt man Eltern-Knoten den unteren Kind-Knoten.
Jeder Knoten (außer der Wurzel) hat genau einen Eltern-Knoten.
Einen Knoten ohne Kind-Knoten nennt man Blatt.
Ein Knoten hat die Tiefe n wenn er n Kanten von der Wurzel entfernt ist.
Die Wurzel hätte also die Tiefe 0, allerdings verwendet man in der Schule oft das Wort Höhe für Tiefe und beginnt bei 1 statt bei 0 wie es richtige Informatiker tun.

Bennenung der Baumelemente — Dieser Baum hat 4 Blätter.

Teilbäume

Nimmt man einen Knoten des Baums und alle seine Kinder und Kindeskinder so hat man einen Teil des Baums und nennt ihn Teilbaum.
Im Bild unten ist der Teilbaum des „Eltern-Knoten von Knoten 5 und 6 und der Teilbaum der rechten Kinds der Wurzel farbig hinterlegt.

Binärbäume

In einem Binärbaum haben alle Knoten maximal 2 Kind-Knoten.
Ein Binärbaum heißt voll, wenn jeder Knoten genau zwei Kinder hat oder ein Blatt-Knoten (keine Kinder) ist.
Ein Binärbaum, welcher voll ist und alle Blätter in der gleichen Tiefe sind heißt vollständig.

kein Binärbaum — Dies ist **kein** Binärbaum, da die Wurzel 3 Kinder hat auch *K 2* hat mehr als 2 Kinder.

voller Binärbaum — Dies sind Binärbäume, der erste ist voll, der zweite vollständig, der dritte nichts von beidem.

vollständiger Binärbaum — Dies sind Binärbäume, der erste ist voll, der zweite vollständig, der dritte nichts von beidem.

Sortierte Binärbäume

Ein Binärbaum ist sortiert, wenn für jeden Knoten gilt, dass das der Wert im linken Kind kleiner und der Wert im rechten Kind größer ist als der Wert in seiner Wurzel (es kann auch andersherum sortiert werden: links größer und rechts kleiner).

geordneter Baum mit Zahlen — Zwei sortiert Bäume, einer mit Text und einer mit Zahlen.

geordneter Baum mit Text — Zwei sortiert Bäume, einer mit Text und einer mit Zahlen.

Suchen im sortierten Baum

Um zu überprüfen, ob ein Wert in einem sortieren Baum vorhanden ist, beginnt man bei der Wurzel.
Ist der Wert der Wurzel der gesuchte Wert, so ist man fertig.
Ansonsten überprüft man, ob der gesuchte Wert kleiner als die Wurzel ist, dann nimmt man den linken Kind-Knoten, andernfalls den rechten.
Jetzt überprüft man wieder den aktuellen Knoten: Hat er den gesuchte Wert, so ist man fertig. Ist der gesuchte Wert kleiner als der im Knoten, so nimmt man dessen linken Knoten, um weiter zu suchen, sonst den rechten.
Dies setzt man fort, bis man den gesuchten Wert im Baum gefunden hat oder man keinen Knoten hat um weiter zu suchen.

Beispiel:
Gegeben ist folgender sortierter Baum, in welchem wir zuerst den Wert 6 suchen und dann den Wert 13.

Baum in dem gesucht wird — Ein sortierter Binärbaum in welchem die Werte 6 und 13 gesucht werden.

Suchen wir nach der 6, so beginnen wir bei der Wurzel.
Die Wurzel hat den Wert 8 und es gilt 6<8 somit gehen wir zum linken Kind-Knoten.
Dieser Knoten hat den Wert 4. Da 6>4 gehen wir hier zum rechten Kind-Knoten.
Dieser Knoten hat den gesuchten Wert 6.
Der gesuchte Wert kommt somit im Baum vor.

Pfad zur gesuchten 6 — Die 6 wird gefunden, nachdem die 8, 4 und 6 besucht wird.

Suchen wir nach der 13, so beginnen wir bei der Wurzel.
Die Wurzel hat den Wert 8 und es gilt 13>8 somit gehen wir zum rechten Kind-Knoten.
Dieser Knoten hat den Wert 12. Da 13>12 gehen wir wieder zum rechten Kind-Knoten.
Dieser Knoten existiert nicht.
Der gesuchte Wert kommt somit nicht im Baum vor.

Bewertung der Suche im sortierten Baum: Ist ein Binärbaum ausgewogen, so hat er bei n Knoten eine Tiefe von log₂(n). Da jede Suche maximal den Pfad von der Wurzel zu einem Blatt nimmt, ist die Suche hier viel schneller als die lineare Suche in einem Array.
Bei 1024 Werte werden in einem solchen Baum nur 10 Knoten überprüft anstatt von 1024 bei der linearen Suche.
Bei 10 000 000 Knoten braucht man im Baum 24 Vergleiche und hat eine immense Zeitersparnis.

Bei einem sortieren Baum kann es vorkommen, dass er zu einer Liste „degeneriert”. Hier hätte man keine Zeitersparnis.
Daher ist es wichtig bei Suchbäumen auf Ausgewogenheit zu achten.
Die Algorithmen hierfür fürhern aber über den Bildungsplan hinaus, wer Lust hat suche nach AVL-Bäumen.

Einfügen in einen sortiert Binärbaum

Das Einfügen funktioniert ähnlich wie das Suchen. Man sucht nach dem Wert, der eingefügt werden soll.
Kommt man hier zu einem nicht existierenden Knoten, so ist dies der Ort an dem der neue Knoten eingefügt wird.

Man kann das Vorgehen um einen Wert in einen Baum einzufügen und die Sortierung aufrecht zu erhalten wie folgt als Algorithmus beschreiben:

Nimm die Wurzel als akutellen Knoten
Vergleiche den neuen Wert mit dem aktuellen Knoten
Ist er kleiner nimm das linke Kind als aktuellen Knoten, sonst den rechten.
Existiert der aktuelle Knoten nicht, so fügt man hier den neuen Wert ein,
sonst weiter bei 2.

Im folgenden Beispiel wird in einen Baum, der nur aus dem Wurzel-Knoten mit dem Wert 10 besteht, nacheinander die Zahlen 15, 11, 8, -5, 7, 100 und 9 eingefügt.

Anwendungsbeispiele für Bäume

Neben dem Wahrscheinlichkeitsbaum, den wir aus der Mathematik kennen, gibt es für Bäume nahezu unendlich viele Anwendungsbeispiele. Sie können überall verwendet werden, wo es (abstrakte) Hierarchien gibt.

Aufgaben

Ist es ein Baum?
1. Der Knoten E hat zwei Eltern-Knoten, somit ist es kein Baum.
  Jeder Knoten (außer der Wurzel) hat genau einen Eltern-Knoten.
2. Der Knoten C hat keinen Eltern-Knoten, somit ist es kein Baum.
  Somit wäre A und C ein Wurzel-Knoten. Damit sind es hier zwei Bäume mit A und C als Wurzeln.
Teilbäume
1. Markieren Sie den rechten Teilbaum der Wurzel und beide Teilbäume des Knotens B.
  
  Der rechte Teilbaum der Wurzel umfasst alle Knoten in dem farbigen Viereck.
  Die Teilbäume von B sind farbig hinterlegt
2. Wie sieht ein Baum aus, in dem jeder Knoten nur einen Teilbaum hat?
  
  Wie eine Liste, da jeder Knoten nur einen Kind-Knoten hat ist es genau wie bei Listen-Knoten.
  Einen solchen Baum nennt man auch entartet oder degeneriert.
In einen Baum werden nacheinander die Zahlen 50, 20, 60, 10, 25, 57 und 101 eingefügt.
Geben Sie nach jedem Einfügen an, ob der Baum voll und/oder vollständig ist.
1. Er ist voll, da jeder Knoten 0 oder 2 Kinder hat.
  Er ist vollständig, da er voll ist und jeder Blatt-Knoten die gleiche Tiefe hat.
2. Er ist nicht voll, da der Knoten mit der 50 nur ein Kind hat.
  Da er nicht voll ist kann er nicht vollständig sein.
3. Er ist voll, da jeder Knoten 0 oder 2 Kinder hat.
  Er ist vollständig, da er voll ist und jeder Blatt-Knoten die gleiche Tiefe hat.
4. Er ist nicht voll, da der Knoten mit der 20 nur ein Kind hat.
  Da er nicht voll ist kann er nicht vollständig sein.
  Die Blätter 60 und 10 befinden sich auch nicht auf der gleichen Ebene.
5. Er ist voll, da jeder Knoten 0 oder 2 Kinder hat.
  Er ist nicht vollständig, da die Blätter 10 und 60 unterschiedliche Tiefen haben.
6. Er ist nicht voll, da der Knoten mit der 60 nur ein Kind hat.
  Da er nicht voll ist kann er nicht vollständig sein.
  Zwar sind alle Blätter auf der gleichen Tiefe aber Knoten 60 fehlt ein Teilbaum.
7. Er ist voll, da jeder Knoten 0 oder 2 Kinder hat.
  Er ist vollständig, da er voll ist und jeder Blatt-Knoten die gleiche Tiefe (3) hat.
Erstellen Sie die gesuchten Bäume
1. Fügen Sie in einen geordneten Baum folgende Knoten in der gegebenen Reihenfolge ein: 5, 4 und 6
2. Fügen Sie in einen geordneten Baum folgende Knoten in der gegebenen Reihenfolge ein: 4, 5 und 6
3. Fügen Sie in einen geordneten Baum folgende Knoten in der gegebenen Reihenfolge ein: 712, 100, 20, 158 und 157
4. Fügen Sie in einen geordneten Baum folgende Knoten in der gegebenen Reihenfolge ein: 10, 5, 12, 6, 11, 13 und 4

Ein Baum kann als Tabelle angegeben werden.
Hier hat jeder Knoten einen Index.
Seine Kinder werden nur mit diesem Index angegeben.

Rekonstruieren Sie den Baum aus folgender Tabelle:

Index Inhalt linkes Kind rechtes Kind

1 1 2 3

2 2 4

3 4

4 3

Index	Inhalt	linkes Kind	rechtes Kind
1	1	2	3
2	2		4
3	4
4	3

Rekonstruieren Sie den Baum aus folgender Tabelle:

Index	Inhalt	linkes Kind	rechtes Kind
1	Wurzel	2	3
2	Teilbaum 1		4
3	Teilbaum 2	5	6
4	Blatt 1
5	Blatt 2
6	Blatt 3

Rekonstruieren Sie den Baum aus folgender Tabelle:

Index Inhalt linkes Kind rechtes Kind

1 Voll 2 3

2 ist 4 5

3 tatsächlich

4 dieser

5 Baum
Rekonstruieren Sie den Baum aus folgender Tabelle:

Index Inhalt linkes Kind rechtes Kind

1 degeneriert 2

2 K1 3

3 K2 4

4 K3