07 – Binärbäume

 

Binärbäume besitzen eine rekursive Datenstruktur mit dem folgenden Aufbau:

Dabei enthält “data” Informationen, die einen Datentyp haben, auf dem ein Vergleichsoperator definiert ist (z.B. können Zahlen nach ihrer Größe oder Buchstaben nach ihrer Position im Alphabet angeordnet werden). Im Programmtext unten wird dieses Vergleichbare Element “comparable e” genannt.

Größere Elemente werden stets rechts angehängt, kleinere links. Dabei hat im Binärbaum jeder Knoten jeweils maximal zwei Nachfolger und genau einen Vorgänger (Ausnahme: oberster Knoten). Im folgenden werden die vergleichbaren Elemente der Knoten durch Buchstaben repräsentiert.

Vorgehen beim Aufbau des Baumes:

H einfügen (erster Knoten):

D einfügen (ist kleiner als H und kommt somit an die Verbindung “left”)

M einfügen (ist größer als H und kommt somit an die Verbindung “right”)

B einfügen (ist kleiner als H und kleiner als D, kommt also an die Verbindung “left” von D)

F und P einfügen:

Bezeichnung der Elemente des Baumes

Algorithmen auf Binärbäumen

Einfügen neuer Knoten mit insert

Die Einzufügenden Daten werden über einen Schlüssel (Comparable e) identifiziert. Bei diesem Schlüssel handelt es sich um den schon oben erwähnten Vergleichswert, zum Beispiel den Wert einer Zahl.

Der Funktion muss außerdem ein Startknoten (Node n) übergeben werden, bei dem mit dem Einfüge-”Versuch” begonnen werden soll. Hierbei handelt es sich beim Aufruf durch den Benutzer meist um den Wurzelknoten.

Die Funktion überprüft zunächst, ob der angegebene Knoten n schon existiert:

wenn Knoten n nicht existiert
	...

Wenn nicht, kann an genau dieser (bisher leeren) Stelle der neue Knoten angelegt werden:

wenn Knoten n nicht existiert
	Knoten n = neuer Knoten(Schlüssel)

Wenn der Knoten schon existiert (Normalfall), dann muss überprüft werden, ob der übergebene Schlüssel größer oder kleiner ist als die im Knoten n gespeicherten Informationen. Davon hängt dann ab, ob der neue Knoten links oder rechts am Knoten n angefügt werden soll. Wir testen als erstes, ob der Schlüssel kleiner ist. Wenn er das ist, wird der Einfügebefehl an den linken Nachfolger des aktuellen Knotens n weitergegeben:

wenn der übergebene Schlüssel kleiner ist als die Informationen im Knoten n
	linker Nachfolger von n -> einfügen(Schlüssel, linker Nachfolger von n)

Wenn der Schlüssel größer als die Informationen im Knoten n sind, wird der Einfügebefehl an den rechten Nachfolger des aktuellen Knotens n weitergegeben:

wenn der übergebene Schlüssel größer ist als die Informationen im Knoten n
	rechter Nachfolger von n -> einfügen(Schlüssel, rechter Nachfolger von n)

Das war schon der ganze Algorithmus. In Java sieht er wie folgt aus:

private Node insert(Comparable e, Node n)
{ // fügt einen neuen Knoten in den Baum ein
	if (n == null)
		// wenn der aktuelle Knoten leer ist, wird er zum neuen Knoten
		n = new Node(e,null,null);
	else if (e.compareTo(n.data) < 0)
		// wenn er nicht leer ist und größere Daten hat als der
		// Schlüssel, wird der Befehl nach links weitergegeben
		n.left = insert(e, n.left);
	else if (e.compareTo(n.data) > 0)
		// wenn er nicht leer ist und kleinere Daten hat als der
		// Schlüssel, wird der Befehl nach rechts weitergegeben
		n.right = insert(e, n.right);
	return n;
}

Das Entfernen von Knoten geschieht mit der Funktion remove(). Diese ist etwas komplizierter und nur unten im Programmtext genauer dokumentiert.

Möglichkeiten zum Traversieren

Es gibt drei ähnliche Möglichkeiten, einen Binärbaum zu traversieren:

  1. Das In-Order-Verfahren
  2. Das Pre-Order-Verfahren
  3. Das Post-Order-Verfahren

Auf diese drei Möglichkeiten wollen wir nun genauer eingehen.

In-Order-Traversierung

Diese Methode beruht darauf, dass am Ende die Knoten in aufsteigender Reihenfolge sortiert ausgegeben werden sollen.
Zu diesem Zweck wird der Ausgabebefehl vom Wurzelknoten aus so lange an den linken Nachfolger weitergereicht (da dieser kleiner ist), bis der kleinste Knoten erreicht ist (es gibt keinen kleineren Nachfolger mehr).
Dieser Knoten mit dem kleinsten Wert gibt dann seinen Wert aus und reicht den Ausgabebefehl entweder an den rechten Nachfolger weiter, oder wenn dieser nicht existiert an den Vorgänger.
Der Vorgängerknoten bekommt also den Befehl irgendwann zurück. Nach links weitergegeben hat er ihn schon, daher führt er ihn nun selber aus und gibt ihn anschließend nach rechts oder an den Vorgänger weiter.
Dies führt zu einer aufsteigenden Sortierung der Ausgabewerte. Im Beispiel:

Ausgabe: B D F H M P

Die Funktion, die die Knoten mit der Methode “In-Order” ausgibt, heißt displayInOrder. Dieser Funktion muss ein Knoten n übergeben werden, bei dem die Ausgabe beginnen soll. Dies ist im Allgemeinfall der Wurzelknoten.

Die Funktion überprüft zunächst, ob der übergebene Knoten überhaupt existiert:

wenn Knoten n existiert
	...

Wenn er existiert, wird der Befehl an den linken Nachfolger weitergegeben. Ob der linke Nachfolger existiert muss an dieser Stelle nicht geprüft werden, da für diesen ja die Funktion erneut aufgerufen wird und am Anfang der Funktion die Existenzkontrolle steht. Also:

wenn Knoten n existiert
	displayInOrder(linker Nachfolger von n)

Von diesem linken Nachbarn wird der Befehl wiederum weitergereicht, bis er irgendwann einen nicht existenten Knoten erwischt. Dieser tut einfach nichts und gibt den Befehl an die letzte Stelle zurück. Dort wird nun die Ausgabe durchgeführt:

	Knoten n -> gib Knotendaten aus

und anschließend der Befehl an den rechten Nachbarn weitergereicht:

wenn Knoten n existiert
	displayInOrder(rechter Nachfolger von n)

Das war auch schon die ganze Funktion. Zusammengefasst:

Funktion displayInOrder(Knoten n)
{
	wenn Knoten n existiert
	{
		displayInOrder(linker Nachfolger von n)
		Knoten n -> gib Knotendaten aus
		displayInOrder(rechter Nachfolger von n)
	}
}

In Java sieht das ganze so aus:

private void displayInOrder(Node n)
{ // gibt Inhalt des Baums im InOrder Verfahren aus
	 if (n!=null)
	 {
		 displayInOrder(n.left);
		 System.out.print(n.data+" ");
		 displayInOrder(n.right);
	 }
}

Pre-Order-Traversierung

Beim Pre-Order-Verfahren wird der Ausgabebefehl als erstes ausgeführt und dann an den linken und rechten Nachfolger weitergegeben.
Durch dieses Vorgehen erhält man am Schluss keine aufsteigende Sortierung, sondern eine Aufzählung der Knoten in der Reihenfolge, in der sie “gefunden” wurden. Im Beispiel:

Ausgabe: H D B F M P

Der Algorithmus in Java:

private void displayPreOrder(Node n)
{ // gibt Inhalt des Baums im PreOrder Verfahren aus
	if (n!=null)
	{
		System.out.print(n.data+" ");
		displayPreOrder(n.left);
		displayPreOrder(n.right);
	}
}

Post-Order-Traversierung

Beim Post-Order-Verfahren wird der Befehl erst an den linken Nachfolger weitergegeben, dann an den rechten. Erst danach wird der Inhalt des aktuellen Knotens ausgegeben.
Dies ermöglicht zum Beispiel die Speicherung von Formeln:

Ausgabe: 2 5+6 √ *

Der Algorithmus in Java:

private void displayPostOrder(Node n)
{ // gibt Inhalt des Baums im PostOrder Verfahren aus
	 if (n!=null)
	 {
		displayPostOrder(n.left);
		displayPostOrder(n.right);
		System.out.print(n.data+" ");
	 }
}

Komplexität der Operationen im Binärbaum

Die Komplexität der Traversieralgorithmen ist immer O(n).

Wir wenden uns daher der nicht so eindeutigen Funktion insert() zu:

worst-case
Im ungünstigsten Fall sind die Knoten, die in den Baum eingefügt werden sollen, schon vorsortiert. Dies entspricht genau dem worst-case des Quicksort-Algorithmus.

Beispiel:

Der Binärbaum entartet in diesem Fall zu einer ineffizienten Speicherung einer linearen Liste, der Gesamtaufwand zum Aufbau des Baumes ist dann O(n2).

best-case
Im günstigsten Fall wird der Baum so aufgefüllt, dass jeder Knoten genau zwei Nachfolger hat (bis auf die Blätter).
In diesem Fall ergibt sich:

Für die Höhe h des Baumes ergibt sich:

n = 2^h -1\quad  \Rightarrow \quad n-1 = 2^h \quad  \Rightarrow \quad \log _2 \left( {n-1} \right) = h

Neue Knoten werden immer unten angefügt, es müssen also von der Wurzel aus h Knoten durchlaufen werden.
Der Aufwand zum einfügen eines Knotens ist dann nur O(log n), der Gesamtaufwand zum Aufbau des Baumes also O(n log n).

Normalfall

Im Normalfall liegt die Komplexität zwischen dem Optimalfall und dem ungünstigsten Fall:

O\left( {n\log n} \right) \leq K \leq O\left( {n^2 } \right)

Implementierung in Java

Insgesamt ist der Binärbaum schon nicht mehr so leicht zu programmieren wie die bisher besprochenen Datentypen. Allerdings haben wir die wichtigsten Funktionen oben besprochen, alles andere ist eigentlich nur Beiwerk.

Hier die komplette Klasse Binärbaum:

import java.util.*;
import java.text.*;
import java.io.*;		

public class BinTree
{
	private Node root;  // Knoten für die Wurzel, Klasse weiter unten

	public BinTree()
	{ // Konstruktor
		root = null;
	}

	public boolean isEmpty()
	{ // gibt true zurück wenn es keine Wurzel gibt (Baum leer)
		return root==null;
	}

	public void clear()
	{ // Löscht die Wurzel und leert damit den Baum
		root=null;
	}

	private Node remove(Comparable e, Node n)
	{ // Knoten soll entfernt werden, der den Schlüssel "e" hat
		if (n == null)
			// Baum ist schon leer, es kann nichts entfernt werden
			return n;
		else if(e.compareTo(n.data) < 0)
			// gesuchter Schlüssel ist kleiner als die Daten des aktuellen
			// Knotens, daher geht der Befehl weiter an den linken Nachbarn
			n.left= remove(e, n.left);
		else if (e.compareTo(n.data) > 0)
			// gesuchter Schlüssel ist größer als die Daten des aktuellen
			// Knotens, daher geht der Befehl weiter an den rechten Nachbarn
			n.right= remove(e, n.right);
		else if (n.left != null &amp;amp;&amp;amp; n.right != null)
			// der gesuchte Knoten wurde gefunden und er hat zwei Nachfolger.
			// der "größere" Nachbar wird gesucht und verbunden, anschließend
			// wird der aktuelle Knoten aus dem Baum gelöst
			n.data = disconnectSucc(n);
		else if (n.left == null)
			// der gesuchte Knoten wurde gefunden und er hat keinen linken N.
			// es muss also einfach der Knoten auf den rechten Nachfolger
			// gesetzt werden
			n = n.right;
		else
			// der gesuchte Knoten wurde gefunden und er hat keinen rechten N.
			// es muss also einfach der Knoten auf den linken Nachfolger
			// gesetzt werden
			n = n.left;

		return n;
	}

	private Comparable disconnectSucc(Node n)
	{ // Funktion löst die Verbindung des Knotens n
		 Node succParent = n;
		 Node succ = n;
		 Node curr = n.right;
		 // Nachfolger lokalisieren
		 while (curr != null)
		 {
			 succParent = succ;
			 succ = curr;
			 curr = curr.left;
		 }
		 if (succ == succParent.right)
			 // wenn der Knoten rechter Nachfolger des Vorgängers ist
			 succParent.right = succ.right;
		 else
			 succParent.left = succ.right;

		 return succ.data; // Daten des gelösten Knotens werden zurückgegeben
	}

	private Node insert(Comparable e, Node n)
	{ // fügt einen neuen Knoten in den Baum ein
		if (n == null)
			// wenn der aktuelle Knoten leer ist, wird er zum neuen Knoten
			n = new Node(e,null,null);
		else if (e.compareTo(n.data) < 0)
			// wenn er nicht leer ist und größere Daten hat als der
			// Schlüssel, wird der Befehl nach links weitergegeben
			n.left = insert(e, n.left);
		else if (e.compareTo(n.data) > 0)
			// wenn er nicht leer ist und kleinere Daten hat als der
			// Schlüssel, wird der Befehl nach rechts weitergegeben
			n.right = insert(e, n.right);
		return n;
	}

	private boolean find(Comparable e, Node n)
	{ // rekursiver Suchalgorithmus, der den Knoten mit Schlüssel "e" findet
		if	(n == null)
			return false;
		else if (e.compareTo(n.data) == 0)
			return true;
		else if (e.compareTo(n.data) < 0)
			return find(e, n.left);
		else
			return find(e,n.right);
	}

	private void displayInOrder(Node n)
	{ // gibt Inhalt des Baums im InOrder Verfahren aus
		 if (n!=null)
		 {
			 displayInOrder(n.left);
			 System.out.print(n.data+" ");
			 displayInOrder(n.right);
		 }
	}		 

	private void displayPostOrder(Node n)
	{ // gibt Inhalt des Baums im PostOrder Verfahren aus
		 if (n!=null)
		 {
			displayPostOrder(n.left);
			displayPostOrder(n.right);
			System.out.print(n.data+" ");
		 }
	}

	private void displayPreOrder(Node n)
	{ // gibt Inhalt des Baums im PreOrder Verfahren aus
		if (n!=null)
		{
			System.out.print(n.data+" ");
			displayPreOrder(n.left);
			displayPreOrder(n.right);
		}
	}	

	private class Node
	{ // Knoten mit drei Variablen und drei Möglichkeiten der Initialisierung
		public Comparable data;
		public Node left;
		public Node right;

		public Node()
		{
			this(null, null, null);
		}

		public Node(Comparable e)
		{
			this(e, null, null);
		}

		public Node(Comparable e, Node leftn, Node rightn)
		{
			data = e;
			left = leftn;
			right = rightn;
		}
	} // end class Node
} // end class BinTree