TU Darmstadt

Binäre Bäume

von

Daniel Brücher

2005

Inhaltsverzeichnis 1

Vorwort 2

Teil I 2
Begriffsklärung: 3
Suche in binären Bäumen: 5
Erstellen eines binären Suchbaumes: 10
Einfügen in binären Suchbäumen: 12
Löschen in binären Suchbäumen 14

Teil II 18
Hausaufgabe 18
Pseudocode löschen 18
Arbeitsauftrag - Klassenliste: 19
Komplexität 22

Literaturangaben 26

Vorwort

Bäume sind eine der wichtigsten Datenstrukturen der Informatik. Es geht darum Schülern einen erweiterten Einblick in das Thema zu geben und auf das wissenschaftliche Arbeiten vorzubereiten.
Im Rahmen der SPS 2 wurde dieses Skript geschrieben, dass dem Schüler ein „Nachlernen“ ermöglichen soll. Des weiteren kann es von einem Lehrer dazu genutzt werden seine Unterrichtseinheit zu dem Thema zu planen und sich an die hier gegebenen Erklärungen und Definitionen anzulehnen.
Nach den Unterrichtseinheiten sollen die Schüler in der Lage sein, einfache Operationen am binären Baum durchzurühren (Suche nach Elementen und löschen von Elementen), sowie dazu in der Lage sein, selbst einen binären Baum zu erstellen.

Teil I

Das nun euch vorliegende Skript behandelt das Thema „binäre Bäume“. 
Es werden dir die Grundstrukturen und Grundbegriffe von binären Bäumen näher gebracht werden. Wir haben dieses Skript so erstellt, dass ihr möglichst wenig Vorwissen braucht und falls doch etwas unklar sein sollte, dann fragt bei eurem Lehrer nach oder sucht im Internet, welches voll von nützlichen Informationen sein kann, wenn man es richtig nutzt.

Im ersten Teil dieses Skriptes werden wir bestimmte Begriffe klären, die wir brauchen um mit Binären Bäumen arbeiten zu können. Wir zeigen schrittweise, wie man im Binären Baum sucht, einen solchen erstellt und daraus wieder Elemente löscht. 

Im zweiten Teil, bekommt ihr die Gelegenheit binäre Bäume zu erstellen und die erlernten Operationen noch einmal selbst auszuführen.
Danach werden wir schauen, was an Bäumen so vorteilhaft ist.

Anmerkung:

Die teils unterschiedliche Zeichengröße der Knoten ist bedeutungslos, sondern ist nur darauf zurückzuführen die Inhalte entsprechend zu umschließen. 

Die Werte, welche im Knoten stehen und die wir als Kriterium für die Sortierung verwenden bezeichnet man als Schlüsselwert des Knotens, der Einfachheit halber sagen wir bei einem Knoten mit dem Schlüsselwert „a“, der Knoten „a“.

Begriffsklärung:

Bäume sind grundlegende Datenstrukturen in der Informatik und spielen in vielen Algorithmen (z.B. Such- und Sortieralgorithmen) eine Rolle. Dieses Skript beschränkt sich auf binäre Bäume.

Bäume bestehen aus Knoten (als Kreise dargestellt), die miteinander durch Kanten (dargestellt als Pfeile) verbunden sind.

Führt von Knoten A zu Knoten B eine Kante, sagt man:

A ist Vorgänger von B
B ist Nachfolger von A

Binäre Bäume sind Bäume mit höchstens zwei Nachfolgern pro Knoten; einem linken und einem rechten Nachfolger.
Ein Binärbaum ist entweder leer oder besteht aus einem Knoten oder aus einem Knoten und bis zu zwei Binärbäumen. Diese Bäume werden als linker und rechter Teilbaum bezeichnet.

In jedem Baum gibt es genau einen Knoten ohne Vorgänger, diesen nennt man Wurzel. Von der Wurzel aus gibt es zu jedem Knoten genau einen Weg. Ein Knoten ohne Nachfolger wird Blatt genannt.

Die Länge eines Weges wird als Anzahl der Kanten in diesem Weg definiert. Die Länge eines längsten Weges von der Wurzel zu einem Blatt wird als Höhe des Baumes definiert.

Knoten die weder Blatt noch Wurzel sind, nennt man innere Knoten.

Binärer Suchbaum:
Ein binärer Suchbaum ist ein binärer Baum mit folgender Eigenschaft: Die Knoten des linken Teilbaums eines Knotens enthalten nur kleinere Werte und die Knoten des rechten Teilbaums eines Knotens nur größere Werte als der Knoten selbst.

Diese Regel muss für alle Knoten gelten- nur dann ist der Baum auch ein binärer Suchbaum.

[....]