Binärer Suchbaum: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(60 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 5: Zeile 5:


[[File:Binbaum.jpg|thumb|Binärer Suchbaum mit 15 Elementen |600px]]
[[File:Binbaum.jpg|thumb|Binärer Suchbaum mit 15 Elementen |600px]]
=Definition=
=Definition=
Ein binärer Suchbaum ist ein [[allgemeiner Binärbaum ab Abi 2017|Binärbaum]] mit einer zusätzlichen Eigenschaft:
Ein binärer Suchbaum ist ein [[allgemeiner Binärbaum ab Abi 2017|Binärbaum]] mit einer zusätzlichen Eigenschaft:
Zeile 11: Zeile 10:
* Diese Eigenschaft gilt auch für alle Teilbäume eines binären Suchbaumes.
* Diese Eigenschaft gilt auch für alle Teilbäume eines binären Suchbaumes.
Wie ''kleiner'' bzw. ''größer'' definiert werden, hängt dabei vom Anwendungszusammenhang ab; bei Personen kann z.B. das Alter oder die alphabetische Ordnung des Nachnamens das wesentliche Ordnungskriterium sein.
Wie ''kleiner'' bzw. ''größer'' definiert werden, hängt dabei vom Anwendungszusammenhang ab; bei Personen kann z.B. das Alter oder die alphabetische Ordnung des Nachnamens das wesentliche Ordnungskriterium sein.
=Erklärvideos=
* [https://youtu.be/Hv2gABx0KAo Video 1: CelebritiesVerwaltung - Implementationsdiagramm]
* [https://youtu.be/Cz1Nv8B1RH4 Video 2: CelebritiesVerwaltung - Implementierung]
=Fachbegriffe=
Wurzel, linker Teilbaum, rechter Teilbaum, Schnittstelle (interface), eine Schnittstelle implementieren (implements), abstrakt (abstrakte Methode)


=Eigenschaften eines Suchbaumes=
=Eigenschaften eines Suchbaumes=
* In Binären Suchbäumen kann man sehr schnell Elemente finden (daher der Name...); vgl. [[binärer Suchbaum ab Abi 2017#Suchen von Elementen in einem Binären Suchbaum|Suchen von Elementen in einem Binären Suchbaum]]
'''Suchen:'''
* Der Inorder-Durchlauf (Links -> Wurzel -> Rechts) eines Suchbaumes ergibt genau die alphabetische Ordnung. (Zu den verschiedenen Durchlaufarten durch Binärbäume: s. [[allgemeiner Binärbaum ab Abi 2017#Traversierung|Traversierung von Binärbäumen]])
 
Binäre Suchbäume haben den Vorteil, dass man in ihnen <u>sehr schnell suchen</u> kann: <br/>Man muss nicht den ganzen Baum zu durchsuchen, sondern kann - ausgehend von der Wurzel - einen Pfad bis zum Blatt abgehen. Je nachdem, ob das gesuchte Element kleiner oder größer ist als der gerade betrachtete Knoten, biegt man rechts (bzw. links) ab.
 
Der Geschwindigkeitsvorteil ist enorm und wird immer größer, je größer der Baum wird.<br/>(Vorausgesetzt, der Baum ist balanciert.)
 
Bei einem perfekt balancierten Baum sieht das so aus:
* Bei 1.000 Elementen braucht man nur 10 Vergleiche
* Bei 1.000.000 Elementen braucht man nur 20 Vergleiche
* Bei n Elementen braucht man log<sub>2</sub>(n) Vergleiche.
 
 
'''Sortierte Liste:'''
 
Der Inorder-Durchlauf (Links -> Wurzel -> Rechts) eines Suchbaumes ergibt genau die alphabetische Ordnung. (Zu den verschiedenen Durchlaufarten durch Binärbäume: s. [[allgemeiner Binärbaum ab Abi 2017#Traversierung|Traversierung von Binärbäumen]])


=Schnittstelle des Zentralabiturs=
=Schnittstelle des Zentralabiturs=
Zeile 21: Zeile 41:
Die Schnittstelle des Zentralabiturs besteht aus zwei Klassen:
Die Schnittstelle des Zentralabiturs besteht aus zwei Klassen:
* <code>BinarySearchTree</code> ist der eigentliche binäre Suchbaum.
* <code>BinarySearchTree</code> ist der eigentliche binäre Suchbaum.
* <code>Item</code>: In einen <code>BinarySearchTree</code> können nur Objekte eingefügt werden, die die Schnittstelle <code>Item</code> implementieren. <code>Item</code> erzwingt die Implementierung der Methoden <code>isEqual</code>, <code>isGreater</code> und <code>isLess</code>. Dadurch wird festgelegt, wie Objekte in den Suchbaum einsortiert werden.
* <code>ComparableContent</code>: In einen <code>BinarySearchTree</code> können nur Objekte eingefügt werden, die das [[Interface]] <code>ComparableContent</code> implementieren. <code>ComparableContent</code> erzwingt die Implementierung der Methoden <code>isEqual</code>, <code>isGreater</code> und <code>isLess</code>. Dadurch wird festgelegt, wie Objekte in den Suchbaum einsortiert werden.
* Die Methoden von <code>CompararableContent</code> sind alle '''abstrakt''': Das heißt, sie haben selber keine Implementierung, sie erzwingen aber eine Implementierung von jeder Klasse, die von <code>CompararableContent</code> erbt.
=Beispiel: Verwendung von <code>BinarySearchTree</code> und <code>ComparableContent</code>=
In einer Bibliothek soll der Buchbestand in einem Binären Suchbaum gespeichert werden, damit man schnell nach einem bestimmten Buchtitel suchen kann. Das heißt, das Ordnungskriterium für den Suchbaum ist die alphabetische Ordnung nach dem Titel der Bücher.


=Beispiel: Verwendung von <code>BinarySearchTree</code> und <code>Item</code>=
Im Detail sind für die Bibliothek folgende Methoden vorgesehen:
Objekte der Klasse <code>Buch</code> sollen in einen binären Suchbaum eingefügt bzw. nach bestimmten Titeln gesucht werden. Dabei soll das Ordnungskriterium die alphabetische Ordnung nach dem Titel sein.  
* '''suchen:''' Man übergibt einen Buchtitel und erhält das Buch
* '''buecherListeEinfuegen:''' Man übergibt eine Liste von Büchern, die - gemäß dem Ordnungskriterium Titel - richtig in den binären Suchbaum eingefügt werden.
Für die einzelnen Bücher werden lediglich Titel und Regalnummer gespeichert; die Regalnummer soll man nachträglich ändern können, den Titel nicht.
Objekte der Klasse <code>Buch</code> sollen in einen binären Suchbaum eingefügt bzw. nach bestimmten Titeln gesucht werden. Dabei soll das Ordnungskriterium die alphabetische Ordnung nach dem Titel sein.


Dafür muss die Klasse <code>Buch</code> die Schnittstelle <code>Item</code> implementieren und die Methoden <code>isEqual</code>, <code>isGreater</code> und <code>isLess</code> so überschreiben, dass die Bücher nach dem Titel verglichen werden.
==Implementationdiagramm==
[[File:BinarySearchTree_Bibliothek_Implementationsdiagramm.png|Implementationsdiagramm Bibliothek |686px]]


<code>
'''Erläuterungen:'''
  public class Buch <u><b>implements Item</b></u>{
* Bibliothek hat (=besitzt) einen <code>BinarySearchTree</code>, in dem nur Objekte vom Typ <code>Buch</code> gespeichert werden können.
* <code>Buch</code> muss das [[Interface]] <code>ComparableCont</code> implementieren, damit es überhaupt im <code>BinarySearchTree buecherBaum</code> gespeichert werden kann.
* Das hat als Konsequenz: <code>Buch</code> muss die Methoden <code>isEqual</code>, <code>isGreater</code> und <code>isLess</code> so überschreiben, dass die Bücher nach dem Titel verglichen werden.
 
==Implementierung==
 
<code>
  public class Buch <u><b>implements ComparableContent<Buch></b></u>{
   private String titel;
   private String titel;
   private int regalNr;
   private int regalNr;
Zeile 50: Zeile 84:
   }
   }
   
   
   <b><u>public boolean isEqual(Item pItem) {</u>
   <b><u>public boolean isEqual(Buch pContent) {</u></b>
      <u>Buch pBuch = (Buch)pItem;</u>
       <b>return (titel.equals(pBuch.getTitel());</b>
       boolean ergebnis = false;
      if(titel.equals(pBuch.getTitel())){
        ergebnis = true;
      }
      return ergebnis;
   }
   }
   
   
   <u>public boolean isLess(Item pItem) {</u>
   <b><u>public boolean isLess(Buch pContent) {</u></b>
      <u>Buch pBuch = (Buch)pItem;</u>
       <b>return(titel.compareTo(pBuch.getTitel())<0);</b>
       boolean ergebnis = false;
      if(titel.compareTo(pBuch.getTitel())<0){
        ergebnis = true;
      }
      return ergebnis;
   }
   }
   
   
   <u>public boolean isGreater(Item pItem) {</u>
   <b><u>public boolean isGreater(Buch pContent) {</u></b>
      <u>Buch pBuch = (Buch)pItem;</u>
       <b>return(titel.compareTo(pBuch.getTitel())>0);</b>
       boolean ergebnis = false;
  }
      if(titel.compareTo(pBuch.getTitel())>0){
        ergebnis = true;
      }
      return ergebnis;
  }</b>
  }
  }
</code>
</code>


Jetzt können z.B. in einer Klasse <code>Bibliothek</code> Objekte der Klasse <code>Buch</code> in einen <code>BinarySearchTree</code> eingefügt werden:
Jetzt können z.B. in einer Klasse <code>Bibliothek</code> Objekte der Klasse <code>Buch</code> in einen <code>BinarySearchTree</code> eingefügt werden:


<code>
<code>
   public class Bibliothek{
   public class Bibliothek{
    
    
       //hier werden die Buecher gespeichert
       //hier werden die Buecher gespeichert
       BinarySearchTree buecherBaum;
       BinarySearchTree<Buch> buecherBaum;
   
   
       public Bibliothek(){
       public Bibliothek(){
         buecherBaum = new BinarySearchTree();
         buecherBaum = new BinarySearchTree<Buch>();
       }   
       }   
   
   
       '''public void uebertrageListeInBaum(List buecherListe)'''{
       '''public void uebertrageListeInBaum(List<Buch> buecherListe)'''{
         for(buecherListe.toFirst(); buecherListe.hasAccess(); buecherListe.next()){
         for(buecherListe.toFirst(); buecherListe.hasAccess(); buecherListe.next()){
             Buch aktuellesBuch = (Buch)buecherListe.getObject();
             Buch aktuellesBuch = buecherListe.getContent();
             <u>buecherBaum.insert(aktuellesBuch);</u>
             <u>buecherBaum.insert(aktuellesBuch);</u>
         }
         }
Zeile 102: Zeile 121:
           // nach dem kann man dann suchen
           // nach dem kann man dann suchen
           <u>Buch dummyBuch = new Buch(pTitel, -1);</u>
           <u>Buch dummyBuch = new Buch(pTitel, -1);</u>
       
           Buch ergebnis = <u>buecherBaum.search(dummyBuch);</u>
          // Die Methode search gibt ein Item zurueck
          // Casten in ein Buch!
           Buch ergebnis = <u>(Buch)buecherBaum.search(dummyBuch);</u>
           return ergebnis;
           return ergebnis;
       }
       }
   }
   }
</code>
</code>


'''Erläuterungen zur Methode <code>public Buch suche(String pTitel)</code>''':
'''Erläuterungen zur Methode <code>public Buch suche(String pTitel)</code>''':
Zeile 115: Zeile 131:
Die Implementierung sieht auf den ersten Blick etwas eigenwillig aus, ist aber die einfachste und schnellste. Warum wird das so gemacht?
Die Implementierung sieht auf den ersten Blick etwas eigenwillig aus, ist aber die einfachste und schnellste. Warum wird das so gemacht?


* In Objekten vom Typ <code>BinarySearchTree</code> kann man nur nach Objekten vom Typ <code>Item</code> suchen.
* In Objekten vom Typ <code>BinarySearchTree<Buch></code> kann man nur nach Objekten vom Typ <code>Buch</code> suchen.
* D.h. man muss erst ein <code>dummyBuch</code> erstellen, das den gewünschten Titel trägt.
* D.h. man muss erst ein <code>dummyBuch</code> erstellen, das den gewünschten Titel trägt.
* Da <code>Buch</code> die Schnittstelle <code>Item</code> implementiert, kann man mithilfe von <code>dummyBuch</code> die Methode <code>search</code> aufrufen.
* Da <code>Buch</code> das [[Interface]] <code>ComparableContent</code> implementiert, kann man mithilfe von <code>dummyBuch</code> die Methode <code>search</code> aufrufen.
* <code>search</code> gibt dann ein Objekt vom Typ <code>Item</code> zurück; das muss man dann erst in ein <code>Buch</code> casten.
* <code>search</code> gibt dann das "richtige" gesuchte Buch zurück.
* WICHTIG: <code>ergebnis</code> ist das "richtige" Buch; <code>dummyBuch</code> wurde nur dafür erstellt, damit man nach einem Titel suchen kann!
* WICHTIG: <code>ergebnis</code> ist das "richtige" Buch; <code>dummyBuch</code> wurde nur dafür erstellt, damit man nach einem Titel suchen kann!


=Implementationsdiagramm=
=ComparableContent: Java-Quellcode=
[[File:Implementationsdiagramm-BinarySearchTree.png|thumb|Implementationsdiagramm |438px]]
Das [[Interface]] <code>ComparableContent</code> stellt sicher, dass nur Objekte in einen '''binären Suchbaum''' eingefügt werden, die man miteinander vergleichen kann. (Ohne Objekte als ''größer'', ''gleich'' oder ''kleiner'' vergleichen zu können, wäre ein binärer Suchbaum natürlich sinnlos, man könnte keine Sortierung auf linke und rechte Teilbäume vornehmen.)
* Der BinarySearchTree ''hat'' ein Objekt <code>binTree</code> vom Typ <code>BinaryTree</code>, um die Knoten zu speichern.  
<code>
* <code>binTree</code> enthält nur Objekte vom Typ <code>Item</code>.
   public interface ComparableContent<ContentType> {
 
     public boolean isEqual(ContentType pContent);
==Item: Java-Quellcode==
     public boolean isLess(ContentType pContent);
Wenn <code>Item</code> als Interface aufgefasst wird (Begründung: s.o.), dann ist die Implementierung denkbar einfach:
     public boolean isGreater(ContentType pContent);
<code>
   public interface Item {
     public boolean isEqual(Item pItem);
     public boolean isLess(Item pItem);
     public boolean isGreater(Item pItem);
   }
   }
</code>
</code>


* Die Methoden werden in <code>Item</code> nur deklariert, aber nicht implementiert!
* Die Methoden werden in <code>ContentType</code> sind '''abstrakte Methoden''', d.h. sie werden nur deklariert, aber nicht implementiert!
* Jede Klasse, die Item implementiert (Syntax: <code>public MyClass '''implements Item'''</code>), muss diese drei Methoden überschreiben und eine Implementierung anbieten.
* Jede Klasse, die <code>ComparableContent</code> implementiert (Syntax: <code>public MyClass '''implements ComparableContent'''</code>), muss diese drei Methoden überschreiben und eine Implementierung anbieten.


=Suchen (search)=
=Innerer Aufbau eines BinarySearchTree=
Die Klasse <code>BinarySearchTree</code> bietet die Methode <code>search</code>, um Elemente im Baum zu suchen.
Am einfachsten lässt sich ein BinarySearchTree konstruieren, wenn der BinarySearchTree einen BinaryTree besitzt und alle Aufgaben an ihn delegiert:
[[File:BinarySearchTree_innerer_Aufbau.png]]


Binäre Suchbäume haben den Vorteil, dass man in ihnen sehr schnell Elemente suchen kann: Man muss nicht den ganzen Baum zu durchsuchen, sondern kann - ausgehend von der Wurzel - einen Pfad bis zum Blatt abgehen. Je nachdem, ob das gesuchte Element kleiner oder größer ist als der gerade betrachtete Knoten, biegt man rechts (bzw. links) ab.
''(Eine erbt-Beziehung ist <u>nicht</u> möglich, da es Methoden in BinaryTree gibt, die die Suchbaumstruktur des BinarySearchTree zerstören würden, z.B. setLeftTree.)''


==Implementierung (LK)==
==Implementierung von search (LK)==
Die Methode <code>search</code> lässt sich - genauso wie die Methode <code>insert</code> - mit einem Pfaddurchlauf realisieren:


<code>
<code>
  public Item search(Item pItem){
'''public ContentType search(ContentType pContent) {'''
      // eine Referenz auf das Binärbaum-Attribut deklarieren
    BinaryTree<ContentType b = myTree;
      BinaryTree bt = this.binTree;
    while( ! b.isEmpty()){
      // so lange weitergehen, bis man auf einen leeren Baum stoesst
      ContentType wurzel = b.getContent();
      while(!bt.isEmpty()){
      if(pContent.isEqual(wurzel)){
        Item wurzelItem = (Item)bt.getObject();
        // gefunden!
        // ueberpruefen, ob man das richtige gefunden hat
        return wurzel;
        if(wurzelItem.isEqual(pItem)){
      }
            return wurzelItem;
      if(pContent.isLess(wurzel)){
        }
          // links abbiegen
        // weiter nach unten gehen
          b = b.getLeftTree();
        if(pItem.isLess(wurzelItem)){
      }
            bt = bt.getLeftTree();
      else{
        }
          // rechts abbiegen
        else{
          b = b.getRightTree();
            bt = bt.getRightTree();
      }
        }
    }
      }
    // nicht gefunden!
      // bt ist leer
    return null;
      // d.h. das gesuchte pItem wurde nicht gefunden.
  }
      return null;
</code>
  }
</code>


=Einfügen (insert)=
== Implementierung von insert(LK) ==
Um Elemente in einen binären Suchbaum einzufügen, muss man ausgehend von der Wurzel einen Pfad bis zu einem leeren Knoten abgehen. Je nachdem, ob das gesuchte Element kleiner oder größer ist als der gerade betrachtete Knoten, biegt man rechts (bzw. links) ab. Sobald man einen leeren Knoten gefunden hat, ist man an der richtigen Stelle, wo man das Element einfügen kann.
Die Methode <code>insert</code> lässt sich - genauso wie die Methode <code>search</code> - mit einem Pfaddurchlauf realisieren:


== Implementierung (LK) ==
<code>
<code>
    public void insert(ContentType pContent) {
public void insert(Item pItem) {
        BinaryTree<ContentType> b = myTree;
      // eine Referenz auf das Attribut binTree (vom Typ BinaryTree) deklarieren
        '''while(!b.isEmpty()){'''
      // in diesem Attribut werden die Knoten des BinarySearchTree verwaltet!
            ContentType wurzel = b.getContent();
      BinaryTree bt = binTree;
             '''// UPDATE von b'''
      // so lange weitergehen, bis man auf einen leeren Knoten stoesst
             if(pContent.isLess(wurzel)){
      while(!bt.isEmpty()){
                '''b = b.getLeftTree();'''
        Item wurzelItem = bst.getObject();
            }
        // ueberpruefen, ob man das richtige gefunden hat
            else{
        if(wurzelItem.isEqual(pItem)){
                '''b = b.getRightTree();'''
             // es ist nichts zu tun!
            }
             return;
        }
        }
        // jetzt ist man beim richtigen leeren Knoten angekommen!
        // weiter nach unten gehen
        b.setContent(pContent);
        if(pItem.isLess(wurzelItem)){
    }
            bt = bt.getLeftTree();
  </code>
        }
        else{
            bt = bt.getRightTree();
        }
      }
      // jetzt ist man bei einem leeren Knoten angekommen
      bt.setObject(pItem);
      return;
  }
</code>


=Löschen (remove)=
=Löschen (remove)=


Die Klasse <code>BinarySearchTree</code> bietet neben der Methode <code>insert</code> auch die Methode </code>remove</code>, mit der man ein Element aus einem Suchbaum löschen kann - und die Suchbaumstruktur bleibt gewahrt!
Die Klasse <code>BinarySearchTree</code> bietet neben der Methode <code>insert</code> auch die Methode <code>remove</code>, mit der man ein Element aus einem Suchbaum löschen kann - und die Suchbaumstruktur bleibt gewahrt!


Das ist sehr angenehm, denn das Löschen von Elementen aus einem Suchbaum ist eine SEHR mühsame Angelegenheit, weil man genau darauf achten muss, dass die Suchbaum-Struktur nicht zerstört wird.
Das ist sehr angenehm, denn das Löschen von Elementen aus einem Suchbaum ist eine SEHR mühsame Angelegenheit, weil man genau darauf achten muss, dass die Suchbaum-Struktur nicht zerstört wird.
Zeile 216: Zeile 217:


Das Löschen von Knoten aus binären Suchbäumen ist insofern nicht ganz einfach, als man darauf achten muss, dass die Struktur des binären Suchbaums nicht zerstört wird.  
Das Löschen von Knoten aus binären Suchbäumen ist insofern nicht ganz einfach, als man darauf achten muss, dass die Struktur des binären Suchbaums nicht zerstört wird.  
'''<font color='green'> TODO: Implementierung des Löschens auf Abi 2017 anpassen!!!</font>'''


===Strategie===
===Strategie===
Zeile 240: Zeile 244:
# <code>public BinaryTree findeK1Vorgaenger(BinaryTree pTree)</code>
# <code>public BinaryTree findeK1Vorgaenger(BinaryTree pTree)</code>


===Implemtierung===
===Implementierung===
<code>
<code>
   public void loeschen(BinaryTree b, String zahl) {
   public void loeschen(BinaryTree b, String zahl) {
     if(b.isEmpty())
     if(b.isEmpty())
Zeile 359: Zeile 363:
       return ergebnis;
       return ergebnis;
   }
   }
</code>
</code>

Aktuelle Version vom 11. März 2024, 17:57 Uhr


Binärer Suchbaum mit 15 Elementen

Definition

Ein binärer Suchbaum ist ein Binärbaum mit einer zusätzlichen Eigenschaft:

  • die Elemente im linken Teilbaum sind kleiner als die Wurzel; die Elemente im rechten Teilbaum sind größer als die Wurzel.
  • Diese Eigenschaft gilt auch für alle Teilbäume eines binären Suchbaumes.

Wie kleiner bzw. größer definiert werden, hängt dabei vom Anwendungszusammenhang ab; bei Personen kann z.B. das Alter oder die alphabetische Ordnung des Nachnamens das wesentliche Ordnungskriterium sein.

Erklärvideos

Fachbegriffe

Wurzel, linker Teilbaum, rechter Teilbaum, Schnittstelle (interface), eine Schnittstelle implementieren (implements), abstrakt (abstrakte Methode)

Eigenschaften eines Suchbaumes

Suchen:

Binäre Suchbäume haben den Vorteil, dass man in ihnen sehr schnell suchen kann:
Man muss nicht den ganzen Baum zu durchsuchen, sondern kann - ausgehend von der Wurzel - einen Pfad bis zum Blatt abgehen. Je nachdem, ob das gesuchte Element kleiner oder größer ist als der gerade betrachtete Knoten, biegt man rechts (bzw. links) ab.

Der Geschwindigkeitsvorteil ist enorm und wird immer größer, je größer der Baum wird.
(Vorausgesetzt, der Baum ist balanciert.)

Bei einem perfekt balancierten Baum sieht das so aus:

  • Bei 1.000 Elementen braucht man nur 10 Vergleiche
  • Bei 1.000.000 Elementen braucht man nur 20 Vergleiche
  • Bei n Elementen braucht man log2(n) Vergleiche.


Sortierte Liste:

Der Inorder-Durchlauf (Links -> Wurzel -> Rechts) eines Suchbaumes ergibt genau die alphabetische Ordnung. (Zu den verschiedenen Durchlaufarten durch Binärbäume: s. Traversierung von Binärbäumen)

Schnittstelle des Zentralabiturs

Schnittstelle BinarySearchTree (PDF)

Erläuterungen zur Schnittstelle

Die Schnittstelle des Zentralabiturs besteht aus zwei Klassen:

  • BinarySearchTree ist der eigentliche binäre Suchbaum.
  • ComparableContent: In einen BinarySearchTree können nur Objekte eingefügt werden, die das Interface ComparableContent implementieren. ComparableContent erzwingt die Implementierung der Methoden isEqual, isGreater und isLess. Dadurch wird festgelegt, wie Objekte in den Suchbaum einsortiert werden.
  • Die Methoden von CompararableContent sind alle abstrakt: Das heißt, sie haben selber keine Implementierung, sie erzwingen aber eine Implementierung von jeder Klasse, die von CompararableContent erbt.

Beispiel: Verwendung von BinarySearchTree und ComparableContent

In einer Bibliothek soll der Buchbestand in einem Binären Suchbaum gespeichert werden, damit man schnell nach einem bestimmten Buchtitel suchen kann. Das heißt, das Ordnungskriterium für den Suchbaum ist die alphabetische Ordnung nach dem Titel der Bücher.

Im Detail sind für die Bibliothek folgende Methoden vorgesehen:

  • suchen: Man übergibt einen Buchtitel und erhält das Buch
  • buecherListeEinfuegen: Man übergibt eine Liste von Büchern, die - gemäß dem Ordnungskriterium Titel - richtig in den binären Suchbaum eingefügt werden.

Für die einzelnen Bücher werden lediglich Titel und Regalnummer gespeichert; die Regalnummer soll man nachträglich ändern können, den Titel nicht. Objekte der Klasse Buch sollen in einen binären Suchbaum eingefügt bzw. nach bestimmten Titeln gesucht werden. Dabei soll das Ordnungskriterium die alphabetische Ordnung nach dem Titel sein.

Implementationdiagramm

Implementationsdiagramm Bibliothek

Erläuterungen:

  • Bibliothek hat (=besitzt) einen BinarySearchTree, in dem nur Objekte vom Typ Buch gespeichert werden können.
  • Buch muss das Interface ComparableCont implementieren, damit es überhaupt im BinarySearchTree buecherBaum gespeichert werden kann.
  • Das hat als Konsequenz: Buch muss die Methoden isEqual, isGreater und isLess so überschreiben, dass die Bücher nach dem Titel verglichen werden.

Implementierung


public class Buch implements ComparableContent<Buch>{
  private String titel;
  private int regalNr;
  
  public Buch(String pTitel, int pRegalNr){
     titel = pTitel;
     regalNr = pRegalNr;
  }

  public int getRegalNr() {
     return regalNr;
  }

  public void setRegalNr(int regalNr) {
     this.regalNr = regalNr;
  }

  public String getTitel() {
     return titel;
  }

  public boolean isEqual(Buch pContent) {
     return (titel.equals(pBuch.getTitel());
  }

  public boolean isLess(Buch pContent) {
     return(titel.compareTo(pBuch.getTitel())<0);
  }

  public boolean isGreater(Buch pContent) {
     return(titel.compareTo(pBuch.getTitel())>0);
  }
}

Jetzt können z.B. in einer Klasse Bibliothek Objekte der Klasse Buch in einen BinarySearchTree eingefügt werden:


 public class Bibliothek{
  
     //hier werden die Buecher gespeichert
     BinarySearchTree<Buch> buecherBaum;

     public Bibliothek(){
        buecherBaum = new BinarySearchTree<Buch>();
      }  

     public void uebertrageListeInBaum(List<Buch> buecherListe){
        for(buecherListe.toFirst(); buecherListe.hasAccess(); buecherListe.next()){
           Buch aktuellesBuch = buecherListe.getContent();
           buecherBaum.insert(aktuellesBuch);
        }
     }
    
     public Buch suche(String pTitel){
         // man muss erst ein Dummy-Buch erzeugen
         // nach dem kann man dann suchen
         Buch dummyBuch = new Buch(pTitel, -1);
         Buch ergebnis = buecherBaum.search(dummyBuch);
         return ergebnis;
     }
 }

Erläuterungen zur Methode public Buch suche(String pTitel):

Die Implementierung sieht auf den ersten Blick etwas eigenwillig aus, ist aber die einfachste und schnellste. Warum wird das so gemacht?

  • In Objekten vom Typ BinarySearchTree<Buch> kann man nur nach Objekten vom Typ Buch suchen.
  • D.h. man muss erst ein dummyBuch erstellen, das den gewünschten Titel trägt.
  • Da Buch das Interface ComparableContent implementiert, kann man mithilfe von dummyBuch die Methode search aufrufen.
  • search gibt dann das "richtige" gesuchte Buch zurück.
  • WICHTIG: ergebnis ist das "richtige" Buch; dummyBuch wurde nur dafür erstellt, damit man nach einem Titel suchen kann!

ComparableContent: Java-Quellcode

Das Interface ComparableContent stellt sicher, dass nur Objekte in einen binären Suchbaum eingefügt werden, die man miteinander vergleichen kann. (Ohne Objekte als größer, gleich oder kleiner vergleichen zu können, wäre ein binärer Suchbaum natürlich sinnlos, man könnte keine Sortierung auf linke und rechte Teilbäume vornehmen.)


 public interface ComparableContent<ContentType> {
   public boolean isEqual(ContentType pContent);
   public boolean isLess(ContentType pContent);
   public boolean isGreater(ContentType pContent);
 }

  • Die Methoden werden in ContentType sind abstrakte Methoden, d.h. sie werden nur deklariert, aber nicht implementiert!
  • Jede Klasse, die ComparableContent implementiert (Syntax: public MyClass implements ComparableContent), muss diese drei Methoden überschreiben und eine Implementierung anbieten.

Innerer Aufbau eines BinarySearchTree

Am einfachsten lässt sich ein BinarySearchTree konstruieren, wenn der BinarySearchTree einen BinaryTree besitzt und alle Aufgaben an ihn delegiert: BinarySearchTree innerer Aufbau.png

(Eine erbt-Beziehung ist nicht möglich, da es Methoden in BinaryTree gibt, die die Suchbaumstruktur des BinarySearchTree zerstören würden, z.B. setLeftTree.)

Implementierung von search (LK)

Die Methode search lässt sich - genauso wie die Methode insert - mit einem Pfaddurchlauf realisieren:


public ContentType search(ContentType pContent) {
   BinaryTree<ContentType b = myTree;
   while( ! b.isEmpty()){
      ContentType wurzel = b.getContent();
      if(pContent.isEqual(wurzel)){
        // gefunden!
        return wurzel;
      }
      if(pContent.isLess(wurzel)){
         // links abbiegen
         b = b.getLeftTree();
      }
      else{
         // rechts abbiegen
         b = b.getRightTree();
      }
   }
   // nicht gefunden!
   return null;
 }

Implementierung von insert(LK)

Die Methode insert lässt sich - genauso wie die Methode search - mit einem Pfaddurchlauf realisieren:


   public void insert(ContentType pContent) {
       BinaryTree<ContentType> b = myTree;
       while(!b.isEmpty()){
           ContentType wurzel = b.getContent();
           // UPDATE von b
           if(pContent.isLess(wurzel)){
               b = b.getLeftTree();
           }
           else{
               b = b.getRightTree();
           }
       }
       // jetzt ist man beim richtigen leeren Knoten angekommen!
       b.setContent(pContent);
   }

Löschen (remove)

Die Klasse BinarySearchTree bietet neben der Methode insert auch die Methode remove, mit der man ein Element aus einem Suchbaum löschen kann - und die Suchbaumstruktur bleibt gewahrt!

Das ist sehr angenehm, denn das Löschen von Elementen aus einem Suchbaum ist eine SEHR mühsame Angelegenheit, weil man genau darauf achten muss, dass die Suchbaum-Struktur nicht zerstört wird.

Im folgenden wird dargestellt, wie das Löschen von Elementen aus einem Binären Suchbaum funktioniert.

Implementierung einer Löschmethode

Beispiel: Löschen der 34

Diese Methode ist nicht relevant für das Zentralabitur!

Das Löschen von Knoten aus binären Suchbäumen ist insofern nicht ganz einfach, als man darauf achten muss, dass die Struktur des binären Suchbaums nicht zerstört wird.

TODO: Implementierung des Löschens auf Abi 2017 anpassen!!!


Strategie

Standardfall

  1. Den richtigen Knoten suchen: K0. Außerdem braucht man den Vorgänger von K0
  2. Suche im linken Teilbaum von K0 den Knoten, der am weitesten rechts ist: K1. Außerdem braucht man den Vorgänger von K1
  3. Hänge den (linken!) Nachfolger von K1 an den Vorgänger von K1.
  4. K1 ersetzt jetzt K0, d.h. der Inhalt von K1 wird jetzt in den Knoten K0 geschrieben.


Ausnahmefälle

  1. K0 ist ein Blatt → einfach löschen.
  2. Die Wurzel des Gesamtbaumes enthält das zu löschende Element
    1. TODO
  3. K0 hat keinen linken Teilbaum → Der Nachfolger von K0 ersetzt K0, d.h.:
    1. Im Vorgänger von K0 wird der Nachfolger von K0 als (richtigen!) Nachfolger eingetragen.

benötigte Methoden

  1. public boolean istBlatt(BinaryTree pTree)
  2. public BinaryTree findeK0Vorgaenger(BinaryTree pTree, Object pObject)
  3. public BinaryTree findeK1Vorgaenger(BinaryTree pTree)

Implementierung


 public void loeschen(BinaryTree b, String zahl) {
   if(b.isEmpty())
   {
     return;
   }
 
   // wenn das zu loeschende Element die Wurzel ist:
   // 1. an einen Vater-Knoten anhaengen
   // 2. loeschen
   // 3. vaterknoten wieder wegnehmen	
   if(b.getObject().equals(zahl)){
     BinaryTree vater = new BinaryTree("-999999");
     vater.setRightTree(b);
     loeschen(vater, zahl);
     b = vater.getRightTree();
     return;
   }
 
   BinaryTree K0vorgaenger = this.findeVorgaengerKnoten(b,zahl );
   System.out.println("Vorgänger von K0:" + K0vorgaenger.getObject());
 
   boolean K0haengtLinksAmVorgaenger = true;
   BinaryTree K0 = K0vorgaenger.getLeftTree();
   if(!K0vorgaenger.getRightTree().isEmpty() && 
     zahl.equals(K0vorgaenger.getRightTree().getObject()))
   {	
     K0 = K0vorgaenger.getRightTree();
     K0haengtLinksAmVorgaenger = false;
   }

   String K0String = (String) K0.getObject();
   System.out.println("K0String: "+K0String);
 
   if(istBlatt(K0)){
     System.out.println("istBlatt!");
     if(K0haengtLinksAmVorgaenger){
       K0vorgaenger.setLeftTree(new BinaryTree());
     }
     else{
       K0vorgaenger.setRightTree(new BinaryTree());
     }
     return;
   }

   if(K0.getLeftTree().isEmpty()){
     K0.setObject(K0.getRightTree().getObject());
     K0.setLeftTree(K0.getRightTree().getLeftTree());
     K0.setRightTree(K0.getRightTree().getRightTree());
     return;
   }

   BinaryTree K1vorgaenger = vorgaengerVonAmWeitestenRechts(K0.getLeftTree());
   System.out.println("K1vorgaenger: " + K1vorgaenger.getObject());
   BinaryTree K1 = K1vorgaenger.getRightTree();
   System.out.println("K1: " + K1.getObject());

   K1vorgaenger.setRightTree(K1.getLeftTree());
   K0.setObject(K1.getObject());

   return;
 }

 private boolean istBlatt(BinaryTree pTree) {
   boolean ergebnis = pTree.getLeftTree().isEmpty() && pTree.getRightTree().isEmpty(); 
   System.out.println("istBlatt("+pTree.getObject()+"): "+ergebnis);
   return ergebnis;
 }

 private BinaryTree vorgaengerVonAmWeitestenRechts(BinaryTree pTree) {
   System.out.println("vorgaengervonAmWeitestenRechts("+pTree.getObject()+")");
   if(pTree.getRightTree().isEmpty()){
     System.err.println("Fehler in vorgaengerVonAmWeitestenRechts");
     return null;
   }
   if(pTree.getRightTree().getRightTree().isEmpty()){
     return pTree;
   }
   BinaryTree ergebnis = this.vorgaengerVonAmWeitestenRechts(pTree.getRightTree());
     return ergebnis;
   }

   private BinaryTree findeVorgaengerKnoten(BinaryTree pTree, String zahl)
   {
     System.out.println("findeVorgaengerKnoten("+pTree.getObject()+", "+zahl+")");
     if(zahl.equals(pTree.getObject())){
       System.err.println(zahl+"ist die Wurzel von pTree selber!!!");
       return null;
     }
     boolean gefunden = false;
     int zahl1 = Integer.parseInt(zahl);

     BinaryTree ergebnis = pTree;
     while(gefunden == false){
       String wurzelString = (String) ergebnis.getObject();
       int wurzelInt = Integer.parseInt(wurzelString);

       System.out.println("wurzelInt" + wurzelInt);
       System.out.println("zahl" + zahl);
       System.out.println("ergebnis.getObject(): " + ergebnis.getObject());

       if(zahl.equals(ergebnis.getRightTree().getObject()) || 
          zahl.equals(ergebnis.getLeftTree().getObject()))
       {
         gefunden = true;
       }
       else
       {
         if(zahl1 < wurzelInt){
           ergebnis = ergebnis.getLeftTree();
         }
         else{
           ergebnis = ergebnis.getRightTree();
         }
       }
     }
     return ergebnis;
 }