Binärer Suchbaum

Arbeiten mit Interface (Dokumentation)

Die Klasse Binary Search Tree<Content Type extends Comparable Content<Content Type>> Mithilfe der generischen Klasse BinarySearchtree können beliebig viele Objekte des Typs Content Type in einem Binärbaum (binärer Suchbaum) entsprechend einer Ordnungsrelation verwaltet werden. Ein Objekt der Klasse BinarySearchtree stellt entweder einen leeren Baum dar oder verwaltet ein Inhaltsobjekt vom Typ Content Type sowie einen linken und einen rechten Teilbaum, die ebenfalls Objekte der Klasse BinarySearchtree sind. Die Klasse der Objekte, die in dem Suchbaum verwaltet werden sollen, muss das generische Interface Comparable Content implementieren. Dabei muss durch Überschreiben der drei Vergleichsmethoden isLess, isEqual, isGreater (s. Dokumentation des Interfaces) eine eindeutige Ordnungsrelation festgelegt sein. Beispiel einer solchen Klasse: public class Entry implements Comparable Content <Entry> {    int wert;    // diverse weitere Attribute    public boolean is Less (Entry pContent) { return this.getWert() < pContent.getWert(); }    public boolean isEqual (Entry pContent) { return this.getWert() == pContent.getWert(); }    public boolean isGreater (Entry pContent) { return this.getWert() > Content.getWert(); }    public int getWert() { return this. wert;}

Die Objekte der Klasse ContentType sind damit vollständig geordnet. Für je zwei Objekte c1 und c2 vom Typ ContentType gilt also insbesondere genau eine der drei Aussagen: cl.isLess (c2) cl.isEqual (c2) cl.isGreater(c2) (Sprechweise: el ist kleiner als c2) (Sprechweise: cl ist gleichgroß wie c2) (Sprechweise: cl ist größer als c2) Alle Objekte im linken Teilbaum sind kleiner als das Inhaltsobjekt des Binärbaumes. Alle Objekte im rechten Teilbaum sind größer als das Inhaltsobjekt des Binärbaumes. Diese Bedingung gilt auch in beiden Teilbäumen.

Methoden

Dokumentation der generischen Klasse Binary Search Tree<Content TYpe extends Comparable Content<Content Type>> Konstruktor BinarySearchTree () Der Konstruktor erzeugt einen leeren Suchbaum.

Anfrage boolean isEmpty() Diese Anfrage liefert den Wahrheitswert true, wenn der Suchbaum leer ist, sonst liefert sie den Wert false.

Auftrag void insert (Content Type p pContent) Falls bereits ein Objekt in dem Suchbaum vorhanden ist, das gleichgroß ist wie Content, passiert nichts. Andernfalls wird das Objekt pContent entsprechend der Ordnungsrelation in den Baum eingeordnet. Falls der Parameter null ist, ändert sich nichts.

Anfrage ContentType search (ContentType pContent) Falls ein Objekt im binären Suchbaum enthalten ist, das gleichgroß ist wie pContent, liefert die Anfrage dieses, ansonsten wird null zurückgegeben. Falls der Parameter null ist, wird null zurückgegeben.

Auftrag void remove (Content Type p pContent) Falls ein Objekt im binaren Suchbaum enthalten ist, das gleichgroß ist wie pContent, wird dieses entfernt. Falls der Parameter null ist ändert sich nichts.

Anfrage ContentType getContent() Diese Anfrage liefert das Inhaltsobjekt des Suchbaumes. Wenn der Suchbaum leer ist, wird null zurückgegeben.  

Anfrage Binary Search Tree<Content Type> getLeft Tree () Diese Anfrage liefert den linken Teilbaum des binären Suchbaumes. Der binäre Suchbaum ändert sich nicht. Wenn er leer ist, wird null zurückgegeben  

Anfrage Binary Search Tree<Content Type> get Right Tree () Diese Anfrage liefert den rechten Teilbaum des Suchbaumes. Der Suchbaum ändert sich nicht. Wenn er leer ist, wird null zurückgegeben.

Interface

Durch ein Interface wird eine Menge von Methoden festgelegt, es werden allerdings keine Implementierungen dieser Methoden angegeben. Eine Klasse, die das Interface implementiert, muss alle durch das Interface festgelegten Methoden implementieren. Von Interfaces können keine Instanzen erzeugt werden.

Methoden

Das generische Interface (Schnittstelle) Comparable Content<Content Type> Das generische Interface Comparable Content muss von Klassen implementiert werden, deren Objekte in einen Suchbaum (Binary Search Tree) eingefügt werden sollen. Die Ordnungsrelation wird in diesen Klassen durch Überschreiben der drei implizit abstrakten Methoden isGreater, is Equal und isLess festgelegt. Das Interface comparableContent gibt folgende implizit abstrakte Methoden vor:  

Anfrage boolean is Greater (Content Type p Comparable Content) Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation größer als das Objekt p ComparableContent ist, wird true geliefert. Sonst wird false geliefert.  

Anfrage boolean isEqual (Content Type p Comparable Content) Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation gleich dem Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert  

Anfrage boolean is Less (Content Type p Comparable Content) Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation kleiner als das Objekt p ComparableContent ist, wird true geliefert. Sonst wird false geliefert.

Praktische Benutzung

Die Klasse, welche der zu verwaltenden Objekte entspricht, implementier die Klasse ComparableContent. In dieser Klasse müssen die isGreater, isLess und isEqual Methoden implementiert werden.   Beispiel: public class Benutzerprofil implements ComparableContent<Benutzerprofil>{}

Pseudocode Methoden

Suchen Inhalt suche (Inhalt gesuchter Inhalt)    falls (baum leer oder gesuchterInhalt == null) dann       return null    falls (gesucht Inhalt < wurzel inhalt) dann       linker Teilbaum.suche (gesuchter Inhalt)    sonst       falls (gesucht Inhalt > wurzel inhalt) dann          rechter Teilbaum. suche (gesuchter Inhalt)       sonst //wenn also gesuchter Inhalt == wurzel inhalt          return wurzel inhalt       ende falls     ende falls ende falls  

Einfügen Inhalt einfuegen (Inhalt neuer Inhalt)     falls (neuerInhalt != null) dann         falls (baum leer) dann             fülle den baum mit neuerInhalt         sonst             falls (neuer Inhalt < wurzel inhalt) dann                 linker Teilbaum. einfuegen (neuer Inhalt)             sonst                 falls (neuer Inhalt > wurzel inhalt) dann                     rechterTeilbaum.einfuegen (neuer Inhalt)                 ende falls             ende falls         ende falls     ande falls

Entfernen void entferne (Inhalt exInhalt)     falls (exInhalt != null und baum nicht leer) dann         falls (exInhalt == wurzel inhalt) dann             falls (baum hat keine Teilbäume) dann                 leere den baum             sonst                 falls (rechter Teilbaum ist leer) dann                     rücke linken Teilbaum an die Position des zu entfernenden Knote                 sonst                     falls (linker Teilbaum ist leer) dann                         rücke rechten Teilbaum an die Position des zu entfernenden Knotens                     sonst // falls es also zwei Teilbäume gibt                         setze Maximum des linken Teilbaums an die Position des zu löschenden Knotens                         entferne (Maximum des linken Teilbaums)                     ende falls                 ende falls             ende falls         sonst             falls (exInhalt < wurzel inhalt) dann                 linker Teilbaum. entferne (Inhalt)             sonst                 rechter Teilbaum.entferne (exInhalt)             ende falls         ende falls     ende falls

Vererbung

public class Unterklasse extends Oberklasse Besipiel: public class Schueler extends Person

Im Konstruktor einer Unterklasse muss immer als erste Anweisung  der Konstruktor der Oberklasse (Superklasse) aufgerufen werden. super(Parameterliste); Beispiel: public Schueler (String pName*, String pKlasse){    super(pName);    klasse = pKlasse ; } *aus der Klasse Person

Mit dem Schlüsselwort super kann die Unterklasse Methoden der Oberklasse aufrufen. Beispiel: super.isGreater(ContentType pContent);

Mit dem Schlüsselwort @Override können Methoden der Oberklasse überschrieben werden Beispiel: @Override public tolleMethode(ContentType pContent){}

Darstellung