Binäre Bäume

Seite 2

Vorwort

Bäume sind eine der wichtigsten D atenstrukturen 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.

Daniel R. Brücher

Seite 3

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

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.

Daniel R. Brücher

Seite 4

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.

Die nachfolgende Grafik veranschaulicht die eben erklärten Begriffe:

Daniel R. Brücher

Seite 5

Suche in binären Bäumen:

Stelle dir vor, du bist ein Forscher und hast ein Tier gefunden dessen Namen du nicht kennst. Du kennst nur einige Eigenschaften des Tieres.

Mit einem Baum wie dem untenstehenden kannst du sehr leicht den Namen des Tieres herausfinden. In jedem dieser Knoten steht ein Kriterium (bzw. Wert) mit dem du die Eigenschaft deines Tieres überprüfst. Ist die Überprüfung positiv gehst du links entlang.

Diese Suche ist so sehr intuitiv. Du überprüfst an jedem Knoten den du durchläufst ob das enthaltene Kriterium Wahr oder Falsch ist und wählst dementsprechend deinen nächsten Knoten aus den du besuchst.

Dieses Beispiel ist sehr speziell. Im nächsten Schritt suchen wir eine Zahl in einem Baum- dabei verwenden wir genau das selbe Schema wie in der Suche zuvor!

Daniel R. Brücher

Seite 6

Die gesuchte Zahl sei 60. Wir überprüfen ob der Wert den wir im Baum suchen <= dem ersten Wert des Baumes ist. Da diese Aussage 60 <= 50 falsch ist gehen wir im Baum rechts entlang. Wir überprüfen nun den Wert des nächsten Knotens (80) mit dem Wert des Knotens den Wir suchen. Ist 60 <= 80 ? Die Aussage ist wahr, deshalb wählen wir den nächsten Knoten auf der linken Seite.

Wenn wir jetzt wieder den Wert des Knotens überprüfen merken wir, dass wir den gesuchten Knoten gefunden haben!

Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus:

Suche nach Element a= 8:

Daniel R. Brücher

Seite 7

Vergleichen mit dem Wert der Wurzel, falls a= w: Element gefunden