www.r-krell.de
Webangebot für Schule und Unterricht, Software, Fotovoltaik und mehr

Willkommen/Übersicht  >  Informatik  >   Informatik-Seite f)

Informatik mit Java

Teil f): Abstrakter Datentyp Baum
(z.B. als binärer Sortier-, AVL- oder Rechen-Baum
sowie als vielfach-verzweigter Spielbaum)

AnimationDie Überschriften a) bis e) verweisen auf die vorhergehenden Seiten, die Überschrift g) auf die folgende Seiten:

a)  Grundlegendes zu Java, benötigte Software (inkl. Downloadadressen) und Installation
b)  Erste Java-Programme (u.a. Autorennen u. Aufzug) sowie Verweise (Links) auf fremde Java-Seiten
c)  Sortieren und Suchen in Java sowie grafische Oberflächen mit der Java-AWT
d)  Adressbuch- und Fuhrpark-Verwaltung sowie Datei-Operationen mit Java
e)  Lineare abstrakte Datentypen Keller, Schlange, Liste und Sortierte Liste (sowie Tiefen- u. Breitensuche)

f) Abstrakter Datentyp Baum

g) Abstrakter Datentyp Graph: Typische Graphenprobleme, Wegsuche, Breiten- und Tiefensuche.
h) Bau eines Compilers Java -> 1_AMOR (Syntaxdiagramm, Scanner, Parser, Variablentabelle, Codeerzeuger)

Eine vollständige Übersicht aller Java-Seiten gibt's auf der Informatik-Hauptseite!


zum Seitenanfang / zum Seitenende

Abstrakter Datentyp Baum als sortierter Datenspeicher

Idee

Das auf der letzten Seite („Informatik mit Java", Teil e) - vierter ADT) bei den sortierten Listen erwähnte Problem, dass der Computer auch in einer sortierten Liste nicht rascher als in einer unsortierten Liste suchen kann, weil er sich trotzdem immer von Anfang an Element um Element entlang der Verkettung weiter hangeln muss, legt eine andere Art der Verkettung nahe: Für das Halbierungsverfahren (binäre Suche) wäre es günstiger, direkt zum mittleren Element der geordneten Liste springen zu können, dann von dort wahlweise zur Mitte der ersten oder zweiten Hälfte gelangen zu können, usw. Verschiebt man die Knoten so, dass die Verkettungspfeile wieder gerade gezeichnet werden können, führt die zur Baumstruktur, wo jeder Knoten bis zu zwei Nachfolger hat. Das oberste (mittlere) Element wird als Wurzel bezeichnet.



Grafik: von der Liste zum Baum



zum Seitenanfang / zum Seitenende

Knoten und Elemente

Neben den beiden Zeigern li und re auf die Nachfolge-Knoten (oder null) enthält jeder Knoten als Inhalt ein beliebiges sortierbares Objekt,



// Java-Baum-Programm, für IF12M  -- Krell, 2.6.04, 10.8.04  --  www.r-krell.de

public class F_Knoten
{
  F_ObjektMitOrdnung inhalt;    
// gespeicherte Informationen
  
F_Knoten li, re;              // Zeiger auf andere Knoten im Baum.
  

  
public F_Knoten (F_ObjektMitOrdnung neuerInhalt)  // Konstruktor für neuen Knoten..
  
{                      // .. erleichtert das Erzeugen, da neuer Knoten immer als Blatt
    
inhalt = neuerInhalt;
    li = 
null;           // d.h. beide Nachfolger eines neuen Baumknotens
    
re = null;           // sind zunächst null!
  
}
}

d.h. der inhalt ist ein Objekt, für das die Ordnungsrelation vergleicheMit definiert ist. Genau wie auf der Seite „Informatik mit Java", Teil e) lässt sich dies über ein Interface sicher stellen: Aus Bequemlichkeit ist hier direkt noch ein Anzeige- bzw. Ausgabemethode angefügt, die von anderen Objekten (z.B. einer Oberfläche aus) aufgerufen werden kann.



// Java-Baum-Programm, für IF12M  -- Krell, 2.6.04, 10.8.04  --  www.r-krell.de

public interface F_ObjektMitOrdnung      // wie E_ObjektMitOrdnung  + zeigeObjekt
{
  
public double vergleicheMit (Object anderes, char sortKrit);
  
// Hiermit wird -- ähnlich wie durch compareTo für Strings -- die Reihenfolge
  // zweier Objekte festgelegt. Anders als bei der vordef. Java-Methode bzw. Com-
  // parable kann noch ein Sortierkriterieum gewählt werden. Speichert man z.B.
  // Schüler mit Namen, Vornamen, Zeugnisnote und Alter, so soll mit dem zu über-
  // gebenden Buchstaben ausgesucht werden, welches Datenfeld der Sortierschlüssel
  // ist. Bei sortKrit='v' könnte z.B. alphabet. nach Vornamen sortiert werden,
  // während bei 'z' Schüler nach ihren Zeugnisnoten verglichen/geordnet werden.
  // Details müssen natürlich bei den konkreten Klassen formuliert werden, die
  // dieses Interface implementieren.
  // a.vergleicheMit(b, sortKrit) < 0 bedeutet a<b; ==0 <=> a=b; >0 <=> a>b
  // bezüglich des gewählten Sortierkriteriums.
  
  
public String zeigeObjekt ();
  
// gibt die wesentlichen Informationen des Elements in einer Textzeile aus
}

Eine mögliche Inhalts- bzw. Element-Klasse, die dieses Interface implementiert, ist die schon im Applet von sortierten Listen verwendete Klasse für Objekte mit zwei verschiedenen Datenfeldern, einem Text und einer Kommazahl:



// Java-Baum-Programm, für IF12M  -- Krell, 2.6.04, 10.8.04  --  www.r-krell.de

public class F_BeispObjekt implements F_ObjektMitOrdnung, java.io.Serializable //Serializ. f. Datei-Op
{
  String text;
  
double zahl;
  
  
public F_BeispObjekt (String wort, double kommazahl)
  {
    text = wort;
    zahl = kommazahl;
  }
  
  
public double vergleicheMit (Object anderes, char sortKrit)
  {
    
switch (sortKrit)
    {
      
case 't' return (text.compareTo( ((F_BeispObjekt)anderes).text ));
      
case 'z' return (zahl - ((F_BeispObjekt)anderes).zahl);
      
default  return (0);
    }
  }

  
public String zeigeObjekt ()
  {
    
return (text+"/"+zahl);
  }
}


Damit sind die Vorarbeiten erledigt: wir wissen jetzt, was in den Baum soll und wonach er sortiert wird. Nun können wir uns dem Aufbau des eigentlichen Baums zu wenden:




zum Seitenanfang / zum Seitenende

Die Klasse Sortierbaum -- Aufbau und Verwaltung des Baums

Zunächst soll noch mal ein Überblick gegeben werden, was der Sortierbaum enthalten und können soll. Dabei sind schon ein paar zusätzliche Methoden genannt, die für die Datenspeicherung nicht unbedingt nötig sind. Die Methoden istLeer, sortRein, zeigeGesucht und löscheGesucht haben natürlich genau den gleichen Kopf (die gleiche 'Signatur') wie die entsprechenden Methoden bei der sortierten Liste. Letztlich soll es dem Benutzer ja egal sein, ob der sortierte Datenspeicher mit einer Liste oder mit einem Baum realisiert wird. Beim Baum wird er sich allerdings über die raschere Ausführung der Methoden freuen können (vorausgesetzt, der Baum ist einigermaßen ausgewogen und nicht zur Liste entartet):



// Java-Baum-Programm, für IF12M  -- Krell, 12.7.04, 10.8.04  --  www.r-krell.de

public class F_Sortierbaum
{
  
// ------------------- Eigenschaften bzw. Datenfelder --------------:

  
F_Knoten wurzel;   // "Zeiger" auf den obersten Knoten im Baum
  
char sortKrit;     // Sortierkriterium, nach dem der Baum aufgebaut wird
    
    
  // --------------------- Methoden ----------------------------------:

  
public F_Sortierbaum (char sortierKriterium)
  
// Konstruktor: legt neuen leeren Baum an
  
{
    wurzel = 
null;
    sortKrit = sortierKriterium;
  }  

  
// -----------------------------------------------------------------
  // die folgenden Methoden sind noch nicht funktionsfähig, sondern sollen
  // nach und nach „gefüllt" werden:

  
public boolean istLeer ()   // prüft, ob der Baum ganz leer ist

  
public void sortRein (F_ObjektMitOrdnung element)
  
// erzeugt an richtiger Stelle neuen Knoten im Baum und füllt diesen mit element
 

  
public F_ObjektMitOrdnung zeigeGesucht (F_ObjektMitOrdnung gesuchtesElement)
  
// nennt das vollständige Element, das mit gesuchtesElement bzgl. sortKrit übereinstimmt
 

  
public F_ObjektMitOrdnung löscheGesucht (F_ObjektMitOrdnung löschElement)
  
// entfernt Knoten mit Übereinstimmung mit löschElement bzgl. sortKrit aus dem Baum
 

  
// -----------------------------------------------------------------
  // Die vorstehenden Methoden reichen zur Benutzung des Baums als sortierter Datenspeicher.
  // Zur zusätzlichen Übung können noch die im nachfolgenden Applet eingebauten Methoden
  // geschrieben werden:

  
public int knotenZahl()  // nennt die Anzahl der Knoten im Baum
 

  
public int ebenenZahl()  // nennt die Anzahl der Ebenen im Baum
 

  
public String lwrAusgabe ()
  
// gibt die Elemente linear in einem String in LWR-Reihenfolge („Inorder") aus
 

  
public String wlrAusgabe ()
  
// gibt die Elemente linear in einem String in WLR-Reihenfolge („Preorder") aus
 
 
  
public String lrwAusgabe ()
  
// gibt die Elemente linear in einem String in LRW-Reihenfolge („Postorder") aus
 
 
  
public String ebenenweiseAusgabe()
  
// gibt die Elemente linear in einem String aus wie zeilenweise aus dem Baum gelesen
 

  
public String aufDisk1 (String dateiName)
  
// speichert Baum in einer Datei mit angegebenem Namen und meldet Erfolg/Misserfolg
 

  
public String vonDisk1 (String dateiName)
  
// holt Baum aus der Datei mit angegebenem Namen und meldet Erfolg/Misserfolg,
  // wobei die Struktur erhalten werden soll, d.h. genau der mit aufDisk1 gespeicherte Baum
  // wieder hergestellt werden soll
 
 
  
public String aufDisk2 (String dateiName)
  
// speichert Baum in einer Datei mit angegebenem Namen und meldet Erfolg/Misserfolg
 

  
public String vonDisk2 (String dateiName)
  
// holt Baum aus der Datei mit angegebenem Namen und meldet Erfolg/Misserfolg, 
  // wobei zwar alle Elemente des mit aufDisk1 gespeicherten Baums wieder hergestellt
  // werden sollen, der Baum jetzt aber optimale (ausgewogene) Form haben soll
 



zum Seitenanfang / zum Seitenende

Ehrgeizige Leserinnen und Leser sollten jetzt die Lektüre dieser Seite abbrechen, und selbst die skizzierten Methoden schreiben. Als Tipp sei noch erwähnt, dass sich rekursive Methoden gut eignen. Zur Motivation können Sie hier noch ausprobieren, wie die Methoden funktionieren sollen:

Interaktiver Test eines Sortier-Baums (mit Java-Applet)

Es werden aus Anwendersicht die gleichen Methoden wie bei der sortierten Liste benutzt, aber intern wird eine andere Speicherstruktur verwendet!

Wer mit seiner Implementation fertig ist, findet auf der folgenden Extraseite zu einigen, aber nicht zu allen Methoden die ausgeführten Quelltexte. Und durch die Extraseite soll erreicht werden, dass der vorzeitige Blick auf eine mögliche Lösung die eigene Kreativität nicht zu früh bremst! Also bitte erst nach eigenen ernsthaften Überlegungen nachsehen:

Java-Quelltext der Klasse Sortierbaum (Auszüge)

Im Baum muss man zum Einsortieren, Finden oder Entfernen eines Elements höchstens einmal von der Wurzel entlang eines Astes bis zur richtigen Stelle nach unten gehen, d.h. höchstens bis zur untersten Ebene gelangen. Beim ausgewogenen oder ausgeglichenen Baum ist die Ebenzahl ~ log2(Elementzahl). Oben wurde mit den Methoden aufDisk2 und vonDisk2 zwar schon eine Möglichkeit angedeutet, für einen ausgewogenen Baum zu sorgen (wie Sie im Applet auch ausprobieren konnten oder können). Allerdings ist diese Art der Strukturverbesserung selbst recht aufwändig. Inzwischen kennt man offenbar verschiedene Möglichkeiten einer geschickteren Höhenbalancierung; das älteste und wohl bekannteste Verfahren ist das von Adelson-Velskij und Landis 1962 erdachte AVL-Verfahren, das auf einer Reihe fremder Webseiten (die in neuen Fenstern geöffnet werden) studiert werden kann:

Applets für AVL-Bäume
Im August 2004 (und im Dezember 2009 noch erreichbar!) fand ich u.a. auf folgenden Seiten Informationen und Applets zu AVL-Bäumen. Bitte informieren Sie mich, wenn Sie noch eine bessere Seite vorschlagen wollen oder falls die genannten Seiten nicht mehr erreichbar sind bzw. sich die Inhalte geändert haben, damit ich die Links aktualisieren oder entfernen kann. Da ich auf fremde Seiten keine Einfluss habe, übernehme ich dafür auch keine Verantwortung oder Haftung.

Binär- und AVL-Bäume Wirtschafts-Uni Wien Bebilderte Beschreibung aller wichtigen normalen und der AVL-Baumoperationen mit Java-Quelltext und Applet
OOP-Projekt AVL-Bäume FH Regensburg Grafisch gelungenes Applet mit dokumentiertem Quelltext
AVL-Baum Uni/TH Karlsruhe (ALFI) Applet für AVL-Baum-Operationen mit kurzer Beschreibung
AVL-Tree TU Braunschweig & Uni Mannheim Java-Applet (der dort angegeben Link zu Quelltexten funktioniert aber nicht mehr)

Das AVL-Verfahren nimmt schon beim Aufbau des Baums (also in sortRein, aber nur innerhalb des gerade besuchten Astes) erforderlichenfalls eine strukturverbessende Ausgleichsoperationen vor (von denen es die vier Typen LL, RR, RL und LR gibt). Trotzdem behält sortRein den logarithmischen Aufwand und der so aufgebaute Baum garantiert auch für die anderen Operationen logarithmischen Aufwand - wenngleich mit einem geringfügig größeren Vorfaktor als beim ideal ausgewogenen Baum. Auf weitere AVL-Details soll hier aber nicht eingegangen werden; in der Literatur und auf den vorstehend genannten und vielen weiteren Internetseiten von Universitäten bzw. von Uni-Dozentinnen und -Dozenten findet man mehr. Hier reicht, dass Bäume die idealen Speicher für sortierte Daten sind und ihre Aufgabe gut und zuverlässig erfüllen.

Abschließend sei noch bemerkt, dass in der Bibliothek der Java-SDK seit 1.2 auch ein Sortierbaum mitgeliefert wird, nämlich TreeMap, der offenbar auch über eine automatische Balancierung verfügt, weil für die Zugriffe auf seine Elemente logarithmischer Aufwand garantiert wird. Für Einzelheiten wird auf die Java-Dokumentation verwiesen.




zum Seitenanfang / zum Seitenende

Bäume zum Rechnen



Binäre Bäume (also solche, wo jeder Knoten maximal zwei Nachfolger hat) können aber nicht nur als sortierte Datenspeicher verwendet werden. Sie eigenen sich auch, um etwa die im Mathematikunterricht der Klassen 5 bis 7 verwendeten Rechenbäume zu realisieren. Beim Rechenbaum geht es um die Hierarchie der auszuführenden Rechenoperationen in einem Term - damit wird z.B. „Punkt- vor Strichrechnung" visualisiert: An einem Knoten mit einem Rechenzeichen hängen die durch die Operation verknüpften Zahlen bzw. (Unter-)Terme. Deswegen dürfen die Zahlen natürlich nicht im Baum nach ihrem Wert sortiert angeordnet werden - es handelt sich also nicht um einen Sortierbaum! - sondern müssen entsprechend ihrer Stellung im Term bzw. der Priorität der damit ausgeführten Verknüpfung in den Baum (s.u., Aufgabe 3c)).

Aufgabenblatt mit einführenden Übungen für einfachen Rechenbaum
Beschränkt man sich - wie in den Aufgaben 2 und 3 des vorgestellten Übungsblattes - auf die Eingabe von einstelligen Ganzzahlen und die vier Grundrechenarten und erlaubt weder Leerzeichen noch Klammern bei der Termeingabe, so ist das geforderte Programm für einen Rechenbaum nicht allzu schwer zu erstellen: Jedes Zeichen des Terms bzw. Eingabe-Strings ist ein eigene Sinneineinheit. Die Prioritäten sind noch überschaubar, die Ausgabe des Terms (wenn der Baum einmal aufgebaut ist) gelingt mit einem der vom Sortierbaum bekannten Traversierungsverfahren (WLR, RWL oder RLW) (Aufgabe 3a)). Ein anderes Traversierungsverfahren zusammen mit einer mehrseitigen Verzweigung (switch..case) für die vier Rechenarten kann zur Ergebnisberechnung verwendet werden (Aufgabe 3b)). Da das Ergebnis und jedes Zwischenergebnis allerdings durchaus mehrstellig und (wegen der Division) auch eine Kommazahl sein kann, werden programmintern die Zahlen am besten immer als Kommazahlen dargestellt. Wie im Übungsblatt erwähnt, bietet sich daher für die Bauminhalte eine Klasse ähnlich F_BeispObjekt an (s.o.).

Wer sich selbst an diesem einfachen Rechenbaum versuchen will, findet hier einige vorbereitete Javadateien (mit geeigneten Objekten und einer Oberfläche) zum Herunterladen. Letztlich gestartet werden muss Rb_Start.java mit der main-Methode, Ergänzungen sind aber nur in Rb_Rechenbaum.java nötig.

Download: Java-Texte rb_rechenbaum.zip (5 kB) für den einfachen Rechenbaum

Die Aufgabe sollte durchaus von einer Lk-Schülerin bzw. einem Lk-Schüler der 12 bewältigt werden können.

Lässt man hingegen auch Leerzeichen, Vorzeichen und echte Kommazahlen (ggf. noch in wissenschaftlicher Schreibweise, d.h. mit Zehnerpotenzen) in der Eingabe zu, muss der Eingabe-String mit einem Scanner in Sinneinheiten (Token) zerlegt werden. Der in der Java-SDK enthaltene StringTokenizer ist dazu ungeeignet; die Dokumentation des dabei erwähnten StreamTokenizers ermutigte nicht gerade zu seiner Verwendung. Mit den Ideen eines endlichen Automaten ist der Scanner letztlich nicht schwierig und kann schematisch aus dem Automatengraph in Java übersetzt werden.
Deutlich anspruchsvoller war der Aufbau des Baums, wobei Klammern am besten rekursiv einen neuen (Teil-)Baum starten. Die Prioritäten sollten aber systematisch geklärt werden -- eine Erweiterung des ad-hoc-Zugangs des einfachen Rechenbaums ist wenig sinnvoll und endet vermutlich im Chaos. Ist der Baum einmal erzeugt, so ist die Berechnung des Resultats dann zum Glück nicht schwieriger als beim einfachen Baum. Umständlicher ist es wieder, aus dem aufgebautem Baum den Term zu erzeugen, wenn man nur unbedingt nötige Klammern ausgeben will. Zunächst müssen von Hand Tabellen aufgestellt und schließlich in die Programmiersprache umgesetzt werden, bei welchen der 32 Kombinationen eines Rechenzeichens im Knoten und den Rechenzeichen in seinem linken bzw. rechten Nachfolger Klammern nötig sind bzw. auf Klammern verzichtet werden kann. Letztlich lässt sich aber auch diese Herausforderung bewältigen, wobei unzulässige Eingaben nicht zum Programmabsturz, sondern zu aussagekräftigen Fehlemeldungen führen sollten:

Oberfläche mit Beispiel für erweiterten Rechenbaum

Oberfläche mit Beispiel für erweiterten Rechenbaum

Oberfläche mit Beispiel für erweiterten Rechenbaum

Oberfläche mit Beispiel für erweiterten Rechenbaum

Oberfläche mit Beispiel für erweiterten Rechenbaum

Oberfläche mit Beispiel für erweiterten Rechenbaum


zum Seitenanfang / zum Seitenende

Spielbäume



MühlebrettAbschließend sei noch erwähnt, dass es nicht nur binäre Bäume gibt. Betrachtet man z.B. ein Zwei-Personen-Spiel wie etwa Mühle, so kann der erste Spieler („Weiß") seinen ersten Stein auf eine von 24 leere Ecken oder Kreuzungen setzten. Sollen in einem Baum die möglichen Stellungen des Spiels verwaltet werden, so gehen vom Wurzelknoten (leeres Brett, Weiß am Zug) also 24 Verzweigungen zu den 24 möglichen Spielständen mit einem weißen Stein aus, wobei dann Schwarz am Zug ist. Schwarz hat jetzt nur 23 Möglichkeiten, seinen Stein zu setzten, bevor wieder Weiß am Zug ist. Es wird schnell klar, dass dieser Baum u.U. sehr viele Knoten aufnehmen muss, und eben kein binärer Baum mehr ist. Statt zweier fester Zeiger li und re auf die Nachfolger wie beim Binärbaum empfiehlt sich hier für jeden Knoten eine dynamische Liste auf die (je nach Spielsituation ja oft unterschiedlich vielen) Nachfolge-Knoten.

Tatsächlich überfordert aber bei den meisten Spielen der Aufbau des vollständigen Baums (selbst wenn man symmetrische Stellungen zusammenfasst) auch die schnellsten Rechner (sonst wäre das Spiel gegen den Computer auch langweilig, weil der Rechner bei vollem Überblick nicht verlieren würde). In der Praxis kann der Baum nur bis zu einer gewissen, geringen Tiefe aufgebaut werden und die Erfolgsaussichten jedes Zweiges müssen ohne genaue Kenntnis der Folgen durch mehr oder weniger gute heuristische Bewertungsverfahren abgeschätzt werden. In diesen Verfahren unterscheiden sich auch unterschiedliche Programme zum gleichen Spiel und zumindest bei geringer Baumtiefe haben auch menschliche Spielerinnen und Spieler so durchaus noch eine Chance gegen den Computer...

Können nach unterschiedlichen Zugfolgen gleiche Spielstände erreicht werden, die auch nur durch einen Knoten dargestellt werden, auf den von mehreren Stellen gezeigt wird, so erzeugt man Maschen und gibt die Gliederung in Ebenen auf: die neu entstandene Struktur ist dann kein Baum mehr, sondern wird als Graph bezeichnet. Graphen werden im Teil g) meiner Seiten „Informatik mit Java" behandelt.




zurück zur Informatik-Hauptseite

(Die anderen Java-Seiten werden entweder mit dem Menü hier am Seitenanfang oder
am besten auch auf der Informatik-Hauptseite ausgewählt)


zum Anfang dieser Seite
Willkommen/Übersicht  -  Was ist neu?  -  Software  -  Mathematik  -  Physik  -  Informatik  -   Schule: Lessing-Gymnasium und -Berufskolleg  -  Fotovoltaik  -  & mehr  -  Kontakt: e-Mail,  News-Abo, Gästebuch, Impressum  -  Grußkarten, site map, Download und Suche

Diese Seite ist Teil des Webangebots http://www.r-krell.de. Sie können diese Seite per e-Mail weiter empfehlen (tell a friend).