SibiWiki - Benutzerbeiträge [de]

SQL-Aufgaben-10

2025-05-05T19:23:44Z

Mgrifka: /* Exkurs: InstaHub */

[[Kategorie:Datenbanken]]
[[Kategorie:Informatik]]
[[Kategorie:Informatik-10]]

Dies ist eine Sammlung von [[SQL-10|SQL]]-Aufgaben zur Beispieldatenbank Schule.

* Die Aufgaben sind nach technischen Gesichtspunkten und Schwierigkeitsgrad gegliedert.

* '''Erläuterungen''' zu SQL am Beispiel der Datenbank "Schule" finden sich im Artikel [[SQL-10]].

=Beispieldatenbank Schule=
* An der Beispieldatenbank Schule können alle möglichen Datenbankabfragen durchprobiert werden.
* Die Beispieldatenbank ist mit Absicht sehr schmal gehalten, damit man die Ergebnisse von SQL-Abfragen noch überprüfen kann.
* Testen kann man SQL-Abfragen auf der Datenbank Schule: '''[http://sibiwiki.de/sql/ hier klicken]'''. Die Zugangsdaten gibt's bei Herrn Kaibel
** ''Wer nicht am SIBI ist, kann hier einen SQL-Dump der Beispieldatenbank Schule herunterladen: [[Datei:Beispieldatenbank-schule.zip]]''

[[Datei:Beispieldatenbank-schule.jpg]]

=Eine Tabelle=
Die folgenden Aufgaben beziehen sich auf nur eine Tabelle.
==SELECT, FROM, WHERE, ORDER BY, DISTINCT, LIKE (mit %) ==
# Eine Liste aller Lehrer mit Name und Vorname, alphabetisch sortiert nach dem Namen.
# Eine Liste der Räume: Raumnummer und Anzahl der Plätze, sortiert nach der Anzahl der Plätze und zwar so, dass die großen Räume zuerst kommen.
# Eine Liste der Unterrichtsfächer; jedes Fach soll in der Liste nur einmal erscheinen.
# Eine Liste der Räume, deren Raumnummer mit "R" beginnt.

==Aggregatfunktionen: COUNT, SUM, AVG, MAX, MIN==
# Wieviele Schüler gibt es insgesamt?
# Wieviele Stunden Unterricht werden insgesamt erteilt?
# Wieviele Stunden Sport werden erteilt?
# Wieviele Plätze hat der größte Raum?
# Wieviele Plätze haben die Räume in der oberen Etage durchschnittlich?

==GROUP BY, AS==
Die folgenden Abfragen benutzen ''zusätzlich'' die Befehle GROUP BY und AS.
# Eine Liste der Etagen, in der vermerkt ist, wieviele Räume es jeweils in der Etage gibt. Die Ergebnistabelle soll die Überschriften "Etage" und "Raeume" haben.
# Eine Liste aller Unterrichtsfächer, in der steht, wieviele Stunden sie jeweils unterrichtet werden; die Unterrichtsfächer mit vielen Stunden sollen oben stehen. Die Ergebnistabelle soll die Überschriften "Fach" und "Stundenzahl" haben.

=Mehrere Tabellen=

==SELECT, FROM, WHERE==
Hier werden nur die Befehle SELECT, FROM und WHERE benutzt.
# Eine Liste der Schüler, aus der hervorgeht, in welcher Klasse sie jeweils sind.
# Eine Liste der Klassen, jeweils mit Klassenlehrer.
# Eine Liste der Unterrichtsfächer der Klasse 8B.
# Eine Liste der Räume, in denen die 8B Unterricht hat.
# Eine Liste der Schüler, die in Raum R112 Unterricht haben.

==ORDER BY, GROUP BY, COUNT, SUM, AVG, MAX, MIN, AS==

# Eine Liste der Klassen mit der Anzahl der Schüler; sortiert nach der Anzahl der Schüler.
# Eine Liste der Klassen, aus der hervorgeht, wieviele Stunden Unterricht die jeweilige Klasse hat. Die Liste soll nach der Anzahl der Stunden sortiert sein.
# Eine Liste der Räume, aus der hervorgeht, wie viele Stunden Unterricht in jedem Raum erteilt wird.

== Exkurs: InstaHub ==
Fotos, die per Link als Werbung in euren InstaHub eingebunden werden können:
[[Datei:SIBI Eyeliner.png|mini]]
[[Datei:Beardpflege im dramatischen Licht.png|mini]]
[[Datei:SiBi SuperMove im Gelände.png|mini]]
[[Datei:Trump.png|mini]]
[[Datei:ElonCar.jpg|mini]]

Datei:ElonCar.jpg

2025-05-05T19:23:39Z

Mgrifka:

eloncar

Datei:Trump.png

2025-05-05T19:23:18Z

Mgrifka:

trump

2019-02-24T12:47:10Z

Mgrifka: /* Methodendeklaration / Methodenkopf */

[[Kategorie:Informatik]]
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Informatik-EF]]
[[Kategorie:Informatik-Q1]]

=Allgemeines=
Hier werden die grundlegenden Sprachelemente von Java '''im Detail''' erklärt.

Wer wissen möchte, wie eine '''ganze Klasse''' aussieht:
* [[Klasse]]

= Anforderungen Zentralabitur =
Das Zentralabitur fordert die Kenntnis von bestimmten Basis-Sprachelementen, die hier aufgeführt sind.

Im folgenden werden diese und weitere Basis-Sprachelemente erläutert.

'''Stand: 2012 (im April 2013 noch aktuell)'''

* Klassendefinitionen
* Beziehungen zwischen Klassen
** gerichtetete Assoziation
** Vererbung
* Attribute und Methoden (mit Parametern und Rückgabewerten)
* Wertzuweisungen
* Verzweigungen (if, switch)
* Schleifen (while, for, do-while)

= Klasse, Objekt, Klassendefinition =
''Auf dieser Seite werden Klassen, Objekte etc. Schritt für Schritt erklärt.

''Den erläuterten kompletten Quellcode einer Java-Klasse findet man hier: [[Klasse in Java]]''

* Von einer '''Klasse''' können viele '''Objekte''' erzeugt werden.
* Beispiel: Es gibt eine Klasse <code>Crab</code>, von der man viele einzelne Objekte erzeugen kann.
* Java: Definiton einer Klasse:
<code>
public class Crab
{
// Attribute

// Konstruktor

// Methoden
}
</code>

= Attribute =
* Attribute beschreiben, welche Eigenschaften bzw. Teil-Objekte die Objekte einer Klasse haben.
* Jedes Attribut kann für jedes einzelne Objekt einer Klasseeinen anderen Wert, den Attribut-Wert haben.
** Beispiel: Die eine Krabbe hat die Geschwindigkeit 5, die andere Krabbe hat die Geschwindigkeit 10.
* Attribute haben einen Attribut-Typ. Für Geschwindigkeiten ist beispielsweise ein Zahltyp sinnvoll, etwa <code>int</code> für ganze Zahlen. Für Namen eignet sich <code>String</code>.
* Java:
** Attribute werden direkt nach der Klassen-Deklaration notiert.
** Attribute sind in der Regel <code>private</code>, d.h. sie können nicht ohne Weiteres von Außen verändert werden.

'''Beispiel 1:'''

Objekte der Klasse <code>Crab</code> können unterschiedliche Geschwindigkeiten haben.

Dafür gibt es das Attribut <code>geschwindigkeit</code>

<code>
public class Crab
{
// Attribute
private int geschwindigkeit;

// Konstruktor

// Methoden
}
</code>

'''Beispiel 2:'''

Objekte der Klasse <code>Baum</code> bestehen aus einen Quadrat (für den Stamm) und einem Kreis (für die Krone).

<code>
public class Baum
{
// Attribute
private Quadrat stamm;
private Kreis krone;

// Konstruktor

// Methoden
}
</code>

= Konstruktor =
'''Aufruf des Konstruktors:'''
* Um ein neues Objekt einer Klasse zu erzeugen, ruft man den Konstruktor der Klasse auf, z.B.:
* Java: <code>Crab neueKrabbe = new Crab();</code>

'''Deklaration des Konstruktors:'''
* In der Deklaration des Konstruktors wird festgelegt, was passiert, wenn ein Objekt der Klasse erzeugt wird.
* Der Konstruktor heißt genauso wie die Klasse.
* Der Konstruktor hat '''keinen''' Rückgabetyp, also auch kein <code>void</code>.

Beispiel:
<code>
public class Crab
{
// Attribute
private int geschwindigkeit;

// Konstruktor
public Crab()
{
turn(50);
}

// Methoden
}
</code>

Dadurch wird jede Krabbe bei der Erzeugung um 50 Grad gedreht.

== Konstruktor mit Parameter ==
Man kann im Konstruktor einen Parameter übergeben, z.B. um direkt bei der Erzeugung die Eigenschaft eines Objektes festzulegen.

Beispiel:
<code>
public class Crab
{
// Attribute
private int geschwindigkeit;

// Konstruktor
public Crab(int pGeschwindigkeit)
{
geschwindigkeit = pGeschwindigkeit;
}

// Methoden
}
</code>

Dadurch muss man bei der Erzeugung der Krabbe die Geschwindigkeit festlegen.

'''Aufgerufen''' wird dieser Konstruktor dann z.B. so:

<code>Crab neueKrabbe = new Crab(3);</code>

Damit hat <code>neueKrabbe</code> die Geschwindigkeit 3.

= Methoden =
In Methoden wird festgelegt, was man mit einem Objekt der Klasse machen kann.

'''Beispiel:'''
Für ein Objekt der Klasse Krabbe soll die Geschwindigkeit festgelegt werden können. Außerdem soll man die Geschwindigkeit auslesen können.
<code>
public class Crab
{
// Attribute
private int geschwindigkeit;

// Konstruktor
public Crab()
{
turn(50);
}

// Methoden
'''public void setzeGeschwindigkeit(int neueGeschwindigkeit)'''
{
geschwindigkeit = neueGeschwindigkeit;
}

'''public int gibGeschwindigkeit()'''
{
return geschwindigkeit;
}
}
</code>

== Methodendeklaration / Methodenkopf ==
Methoden werden durch den '''Methodenkopf (auch: die Methodensignatur)''' deklariert.

D.h. für Objekte der Klasse kann man dann die Methode aufrufen.

==Erklärvideo==

Hier gibt es ein '''[https://youtu.be/JVeAUGX60-A Erklärvideo zu Klassen, Objekten, Attritbuten & Methoden (auf youtube)]'''. '' (Objekt- und Klassendiagramme kommen auch vor.)

Außerdem gibt es hier ein [[Medium:VAB-01 Informatik10 KlassenObjekteAttributeMethoden.pdf|Arbeitsblatt zum Video (PDF)]]. Zu Teilen der Aufgaben gibt es die Lösung im Video, die anderen Aufgaben werden erst im Unterricht besprochen.
'''Beispiel:'''
<code>
public class Automat {
private int eingeworfen;

...

'''public void geldEinwerfen(int betragInCent)'''
{
eingeworfen = eingeworfen + betragInCent;
}

'''private double steuern(int betrag)'''
{
double ergebnis = betrag * 0.19;
return ergebnis;
}

'''public int geldZurueck()'''
{
int ergebnis = eingeworfen;
eingeworfen = 0;
return ergebnis;
}
}
</code>

Der '''Methodenkopf''' ist immer gleich aufgebaut:
# '''Zugriffsmodifikator''': <code>public</code> oder <code>private</code>.
## Auf <code>public</code>-Methoden darf man auch von außen zugreifen; sie sind '''öffentlich'''.
## Auf <code>private</code>-Methoden darf nur die Klasse selbst zugreifen, d.h. von außen ist diese Methode nicht sichtbar! Das ist z.B. sinnvoll für Hilfsmethoden, die nicht jeder benutzen soll.
# '''Rückgabetyp''': <code>void</code> für ''nichts'' bzw. ein Datentyp (wie z.B. <code>int</code>) oder auch eine Klasse.
## Im Rückgabetyp wird festgelegt, ob und was die Methode zurückgibt. So sollten Methoden, die etwas berechnen, das Ergebnis auch zurückgeben.
## Die Methode <code>public void geldEinwerfen(int betragInCent)</code> gibt ''nichts'' zurück. <code>'''void'''</code> ist das Schlüsselwort für ''nichts''.
## Die Methode <code>public int summe(int a, int b) </code> gibt <code>int</code> zurück, d.h. eine ganze Zahl. Methoden, die etwas zurückgeben, brauchen am Ende der Methode ein '''return-Statement''', z.B.: <code>return ergebnis;</code>
# '''Methodenname''': Methodennamen sind Verben, denn Methoden bezeichnen Tätigkeiten! Außerdem ist es üblich, Methodennamen '''klein''' zu schreiben.
# '''Parameter''': In der Klammer nach dem Methodenname findet sich der (bzw. die Parameter).
## Bei den Parametern wird erst der '''Parameter-Typ''' (z.B. <code>int</code>) und dann der '''Parameter-Name''' angegeben.
## Mehrere Parameter werden durch Komma getrennt, z.B. <code>public int summe(int a, int b)</code>
## Methoden ohne Parameter haben leere Klammern, z.B.: <code>public int gelZurueck()</code>

== Parameter ==
* Manche Methoden brauchen eine zusätzliche Information, um richtig arbeiten zu können.
* Das ist hier der Fall bei der Methode <code>setzeGeschwindigkeit</code>: Damit sie sinnvoll arbeiten kann, muss man angeben können, wie groß die Geschwindigkeit sein soll.
* Dafür haben Methoden Parameter, in diesem Fall <code>neueGeschwindigkeit</code>.
* Bei Parametern muss immer der Typ festgelegt werden; man spricht von Parameter-Typ.
** Der Parameter-Typ von <code>neueGeschwindigkeit</code> ist <code>int</code>, also eine ganze Zahl.
* Wenn eine Methode mit Parameter aufgerufen wird, dann muss man den Parameter übergeben.
<code>
Crab neueKrabbe = new Crab();
// jetzt kommt der Methodenaufruf mit Parameterübergabe!
neueKrabbe.setzeGeschwindigkeit(10);
</code>
* Bei Methoden ohne Parameter steht nach dem Methoden-Namen nur <code>()</code>. Das ist wichtig, um sie von Attribute zu unterscheiden!

== Rückgabetyp einer Methode ==
Für eine Methode wird immer der Rückgabetyp festgelegt.
* <code>void</code>: Wenn die Methode '''nichts''' zurückgibt (bei einer verändernden Methode).
** Beispiel: <code>public void setzeGeschwindigkeit(int neueGeschwindigkeit)</code>
* <code>int</code>: Wenn die Methode eine ganze Zahl (<code>int</code>) zurückgibt.
** Beispiel: <code>public int gibGeschwindigkeit()</code>
* Statt <code>int</code> kann auch jeder andere Typ oder auch eine Klasse (z.B. <code>Crab</code>) der Rückgabe-Typ einer Methode sein.
** Beispiel: <code>public Crab gibKopie()</code> : Diese Methode würde eine Kopie der Krabbe (also ein Objekt der Klasse <code>Crab</code>) zurückgeben.

== sondierende Methode / verändernde Methode ==
* '''sondierende Methode (=get-Methode)''': Dieser Methodentyp ''gibt eine Information über das Objekt zurück''. Diese Methode braucht einen Rückgabetyp (d.h. nicht <code>void</code>) und ein return-Statement.
** Beispiel: <code>public int gibGeschwindigkeit()</code>
* '''verändernde Methode (=set-Methode)''': Dieser Methodentyp ''verändert das Objekt''. Häufig hat dieser Methodentyp einen (oder mehrere) '''Parameter'''. Sie hat zumeist den Rückgabetyp <code>void</code>, denn sie gibt in der Regel nichts zurück.
** Beispiel: <code>public void setzeGeschwindigkeit(int pGeschwindigkeit)</code>

== Methodenaufruf ==
Methoden der gleichen Klasse werden durch ihren Methodennamen aufgerufen.

'''VORSICHT:'''
Wenn man eine sondierende Methode aufruft, dann muss man sich für das Ergebnis interessieren!

'''Beispiel:'''

Im Beispiel ruft die Methode <code>groessteZahl</code> dreimal die Methode <code>gibGroessereZahl</code> auf. Das Ergebnis des Aufrufs wird jeweils in einer lokalen Variable (z.B. <code>groessere12</code> gespeichert, um damit weiter zu rechnen.
<code>
public class Rechner{
public int groessteZahl(int z1, int z2, int z3, int z4)
{
int groessere12 = gibGroessereZahl(z1, z2);
int groessere34 = gibGroessereZahl(z3, z4);
int ergebnis = gibGroessereZahl(groessere12, groessere34);
return ergebnis;
}

public int gibGroessereZahl(int a, int b){
int ergebnis;
if(a > b)
{
return a;
}
else
{
return b;
}
}
}
</code>

===Methoden für Objekte anderer Klassen aufrufen ===
Man kann auf für ein Objekt einer anderen Klasse eine Methode aufrufen; damit wird eine Aufgabe '''delegiert'''.

'''Beispiel :'''
<code>
public class Baum
{
// Attribute der Klasse Baum
private Kreis krone;
private Quadrat stamm;

// Konstruktor der Klasse Baum
public Baum()
{
stamm = new Quadrat();
'''stamm.bewegeZuPosition(110,120)''';
'''stamm.sichtbarMachen()''';
krone = new Kreis();
'''krone.bewegeZuPosition(100,100)''';
'''krone.sichtbarMachen()''';
}
}
</code>

'''Erklärung:'''
* <code>stamm</code> ist ein Objekt vom Typ <code>Quadrat</code>; deshalb verfügt <code>stamm</code> über die Methode <code>sichtbarMachen()</code>.
* Im Konstruktor von <code>Baum</code> wird diese Methode mithilfe des Punktes aufgerufen:
** Attributname -> Punkt -> Methodenname.
*
Ein Objekt der Klasse <code>Haus</code> ruft in einem Objekt der Klasse <code>Quadrat</code> die Methode

=lokale Variable=
* '''Lokale Variablen sind nur in dem Block gültig, in dem sie deklariert wurden.'''
* Lokale Variablen kann man (im Gegensatz zu Attributen) nicht in der ganzen Klasse benutzen.
* Man benutzt lokale Variablen, um Informationen zu speichern, die man nur kurzfristig braucht.
** U.a. werden lokale Variablen immer dann eingesetzt, wenn eine Methode ein Ergebnis berechnen und dann zurückgegeben soll.

'''Beispiel aus der Klasse <code>Baum.java</code>:'''
<code>
public boolean hatGrueneBlaetter()
{
// '''lokale Variable'''
// die lokale Variable ergebnis deklarieren
// und mit true initialisieren
// ergebnis wird am Ende zurueckgegeben!
'''boolean ergebnis = true;'''

if(istRot == true)
{
// wenn der Baum rot ist...
// ... hat er keine gruenen Blaetter!
ergebnis = false;
}
// return-Statement: der zurueckgegebene Wert muss den Typ haben
// wie im Methodenkopf angegeben. (Hier: boolean)
return ergebnis;
}

</code>

= Wertzuweisungen =
* Attributen und lokalen Variablen können Werte zugewiesen werden.
* Beispiel 1:
** <code>geschwindigkeit = 10;</code>
** Damit wird dem Attribut <code>geschwindigkeit</code> der Wert 10 zugewiesen.
* Beispiel 2:
** <code>geschwindigkeit = neueGeschwindigkeit;</code>
** Damit wird dem Attribut <code>geschwindigkeit</code> der Wert <code>neueGeschwindigkeit</code> zugewiesen.
* Beispiel 3:
** <code>geschwindigkeit = geschwindigkeit + 1;</code>
** Damit wird dem Attribut <code>geschwindigkeit</code> der Wert <code>geschwindigkeit+1</code> zugewiesen,
** d.h. die Geschwindigkeit wird '''um 1 erhöht'''!

* Allgemein:
** '''links vom Gleichzeichen''' steht das Attribut (bzw. die lokale Variable), der ein neuer Wert zugewiesen wird.
** '''rechts vom Gleichzeichen''' steht der neue Wert.

= Verzweigungen (if, switch) =
== if - else ==
Beispiel: die folgende Methode überprüft, welche von zwei Zahlen die größere ist.

Es passiert folgendes: Wenn (<code>if</code>) <code>a</code> größer als <code>b</code> ist, dann wird <code>ergebnis</code> auf <code>a</code> gesetzt, sonst (<code>else</code>) auf <code>b</code>.

<code>
public int bestimmeDieGroessere(int a, int b)
{
int ergebnis;
'''if(a > b)'''
{
ergebnis = a;
}
'''else'''{
ergebnis = b;
}
return ergebnis;
}
</code>

'''VORSICHT:'''
Gleichheit überprüft man mit '''doppeltem''' Gleichzeichen:
<code>
// Wenn x gleich drei ist, ...
if(x '''==''' 3)
{
...
}
</code>

== switch ==
//TODO

= Schleifen (while, for, do-while) =
Bei Schleifen kommen die Fähigkeiten der Computer besonders zur Geltung: Schleifen ermöglichen es, dass man Aktionen mehrfach (d.h. auch 1.000 oder 1.000.000 mal) wiederholt.
== for-Schleife ==
Die for-Schleife ist eine '''Zählschleife'''. Sie wird eingesetzt, wenn man zählen kann, wie oft Aktionen wiederholt werden sollen. Dafür gibt es eine '''Zählvariable''', die häufig <code>i</code> heißt, aber jeder andere Name ist auch denkbar.

'''Beispiel:'''

Die folgende for-Schleife gibt die Zahlen 0, 3, 6, ...., 999 an die Konsole aus.

<code>
for(int i=0; i<=333; i++)
{
System.out.println(3*i);
}
</code>

'''Erläuterung:'''

* Die Klammer nach dem <code>for</code> hat drei Teile:
** ''Deklaration und Initialisierung der Zählvariable <code>i</code>:'' i startet bei 0.
** ''Schleifenbedingung:'' Die Schleife wird so lange wiederholt, wie i <= 333 ist.
** ''Veränderung bei jedem Schleifendurchlauf:'' i wird bei jedem Schleifendurchlauf um eins erhöht. (<code>i++</code> bedeutet dasselbe wie <code>i = i+1</code>). D.h. i nimmt nacheinander folgende Werte an: 0, 1, 2, ..., 333.
** Im Schleifenrumpf wird mit <code>System.out.println(i);</code> jeweils das Dreifache von <code>i</code> an die Konsole ausgegeben, d.h.: 0, 3, 6, ..., 999.

==while-Schleife==
Die while-Schleife ist eine '''bedingte'''Schleife. Sie wird eingesetzt, wenn Aktionen wiederholt werden sollen, solange die '''Schleifenbedingung''', erfüllt ist.

'''Beispiel:'''

Die folgende while-Schleife beginnt bei <code>zahl = 1</code>. <code>zahl</code> wird dann so lange an die Konsole ausgegeben und verdoppelt, wie <code>zahl</code> kleiner als 1000 ist. D.h. die Ausgabe ist: 1, 2, 4, ..., 256, 512.

<code>
int zahl = 1;
while(zahl < 1000)
{
System.out.println(zahl);
zahl = zahl * 2;
}
</code>

'''Erläuterung:'''
* Die Klammer nach dem <code>while</code> enthält die Bedingung: Wiederhole, solange zahl kleiner 1000 ist.
* Im Schleifenrumpf wird dann <code>zahl</code> an die Konsole ausgegeben und dann mit <code>zahl = zahl * 2;</code> verdoppelt.

= Beziehungen zwischen Klassen =
TODO
== gerichtetete Assoziation ==
TODO
== Vererbung ==
TODO

Klasse

2019-02-24T12:45:05Z

Mgrifka: /* Was ist eine Klasse? */

[[Kategorie:Informatik-EF]]
[[Kategorie:Informatik]]

= Was ist eine Klasse? =
Eine Klasse stellt eine Vorlage (eine Art Bauplan) für Objekte dar, in denen festgelegt wird, welche Eigenschaften ([[Java_Basis-Sprachelemente#Attribute|Attribute]]) die Objekte haben sollen und was man mit den Objekten machen können soll ([[Java_Basis-Sprachelemente#Methoden|Methoden]]).

Ausgehend von einer Anforderungsdefinition plant man eine Klasse. I.d.R. beginnt man, indem man ein [[Klassendiagramm]] zeichnet und das dann in Java umsetzt.

==Erklärvideo==

Hier gibt es ein '''[https://youtu.be/JVeAUGX60-A Erklärvideo zu Klassen, Objekten, Attritbuten & Methoden (auf youtube)]'''. '' (Objekt- und Klassendiagramme kommen auch vor.)

Außerdem gibt es hier ein [[Medium:VAB-01 Informatik10 KlassenObjekteAttributeMethoden.pdf|Arbeitsblatt zum Video (PDF)]]. Zu Teilen der Aufgaben gibt es die Lösung im Video, die anderen Aufgaben werden erst im Unterricht besprochen.

= Beispiel 1: Die Klasse <code>Baum.java</code>=
Hier werden beispielhaft das Klassendiagramm und der Quelltext der Klasse <code>Baum</code> dokumentiert.

Im Detail erläutert werden die einzelnen Sprachelemente hier: [[Java Basis-Sprachelemente]].

== Klassendiagramm der Klasse <code>Baum.java</code>==

Detaillierte Erläuterungen zu Klassendiagrammen findet man [[Klassen- und Implementationsdiagramm|hier]].

{| class="wikitable"
! '''Baum'''
|-
| - stamm: Quadrat

- krone: Kreis

- istRot: boolean

|-
| + Baum()

+ sichtbarMachen()

+ horizontalBewegen(pDistanz: int)

+ fruehling()

+ herbst()

+ hatGrueneBlaetter(): boolean
|}

== Quelltext der Klasse <code>Baum.java</code>==

Für Erläuterungen einfach auf die Links in den Kommentaren klicken!

<code>
'''// Klassendeklaration'''
public class Baum
{

'''// [[Java_Basis-Sprachelemente#Attribute|Attribute]]'''
private Quadrat stamm;
private Kreis krone;
private boolean istRot;

'''// [[Java_Basis-Sprachelemente#Konstruktor|Konstruktor]]'''
public Baum()
{
'''// Aufruf eines Konstruktors: Schluesselwort new'''
stamm = new Quadrat();

'''// Aufruf einer Methode fuer ein anderes Objekt.'''
'''// Attributname -> Punkt -> Methodenname
'''// Es wird ein Parameter uebergeben (30)'''
stamm.groesseAendern(30);

'''// hier werden zwei Parameter uebergeben; getrennt durch Kommas.'''
stamm.bewegeZuPosition(30,60);

'''// hier wird ein String als Parameter uebergeben: "schwarz"'''
stamm.farbeAendern("schwarz");
krone = new Kreis();
krone.bewegeZuPosition(20,20);
krone.groesseAendern(50);
krone.farbeAendern("gruen");
istRot = false;

'''//Aufruf einer Methode der Klasse Baum'''
sichtbarMachen();
}

'''// [[Java_Basis-Sprachelemente#Methoden|Methoden]]'''

'''// Methode OHNE Rueckgabe und OHNE Parameter: Schluesselwort void, leere Klammern ()'''
public void sichtbarMachen()
{
stamm.sichtbarMachen();
krone.sichtbarMachen();
}

'''//Methode mit einem Parameter: (Parametertyp Parametername)'''
public void horizontalBewegen(int distanz)
{
'''//der Parameter wird weiterverwendet'''
stamm.horizontalBewegen(distanz);
krone.horizontalBewegen(distanz);
}

'''// Methode OHNE Rueckgabe und OHNE Parameter: Schluesselwort void, leere Klammern ()'''
public void herbst()
{
krone.farbeAendern("rot");
istRot = true;
}

'''// Methode OHNE Rueckgabe und OHNE Parameter: Schluesselwort void, leere Klammern ()'''
public void fruehling()
{
krone.farbeAendern("gruen");
istRot = false;
}

'''//Methode mit einem Rueckgabetyp: boolean'''
public boolean hatGrueneBlaetter()
{
'''// [[Java_Basis-Sprachelemente#lokale_Variable|lokale Variable]]'''
// die lokale Variable ergebnis deklarieren
// und mit true initialisieren
// ergebnis wird am Ende zurueckgegeben!
boolean ergebnis = true;

if(istRot == true)
{
// wenn der Baum rot ist...
// ... hat er keine gruenen Blaetter!
ergebnis = false;
}
// '''return-Statement: der zurueckgegebene Wert muss den Typ haben'''
// '''wie im Methodenkopf angegeben. (Hier: boolean)
return ergebnis;
}

}
</code>

=Beispiel 2: Die Klasse <code>Benutzer</code>=
== Anforderungsbeschreibung einer Klasse <code>Benutzer</code> ==
Ein paar Oberstufenschüler planen, ein asoziales Netzwerk zu gründen. Die Nutzer des Netzwerkes sollen durch eine Klasse <code>Benutzer</code> realisiert werden. Zu jedem Nutzer sollen folgende Informationen gespeichert werden:
* Nachname und Vorname des Nutzers
* Alter des Nutzers
* ob der Nutzer Brillenträger ist
* der andere Nutzer des Netzwerks, auf dessen Profil der Nutzer am häufigsten geklickt hat

Außerdem sollen folgende Aktionen auf <code>Benutzer</code>-Objekte angewendet werden können:
* man soll den Vornamen und Nachnamen eines <code>Benutzer</code>-Objektes auslesen können (-> [[Java_Basis-Sprachelemente#sondierende_Methode / verändernde_Methode|get-Methode]])
* man soll das Alter eines Nutzers eintragen bzw. ändern können (-> [[Java_Basis-Sprachelemente#sondierende_Methode / verändernde_Methode|set-Methode]])
* falls ein Benutzer nun Brillenträger ist, soll man den entsprechenden Attributwert ändern können
* falls ein Benutzer einen neuen Lieblingsnutzer hat, soll dieser eingetragen werden können

== Klassendiagramm der Klasse <code>Benutzer</code> ==
Im Klassendiagramm wurden aus Platzgründen nur Teile der sinnvollen Methoden aufgeführt.

Detaillierte Erläuterungen zu Klassendiagrammen findet man [[Klassen- und Implementationsdiagramm|hier]].

{| class="wikitable"
! Benutzer
|-
| - nachname: String

- vorname: String

- alter: int

- brillentraeger: boolean

- lieblingsnutzer: Benutzer
|-
| + Benutzer(pNachname: String, pVorname: String, pAlter: int)

+ getNachname(): String

+ getVorname(): String

+ traegtNunBrille()

+ setLieblingsNutzer(pNeuerLiebling: Benutzer)
|}

== Umsetzung der Klasse in Java ==
<code>
public class Benutzer
{
// Attribute
private String nachname;
private String vorname;
private int alter;
private boolean brillentraeger;
private Benutzer lieblingsnutzer;

// Konstruktor
public Benutzer(String pNachname, String pVorname, int pAlter)
{
nachname = pNachname;
vorname = pVorname;
alter = pAlter;
brillentraeger = false;
lieblingsnutzer = null;
}

// weitere Methoden
public String getNachname()
{
return nachname;
}

public String getVorname()
{
return vorname;
}

public void traegtNunBrille()
{
brillentraeger = true;
}

public void setLieblingsNuetzer(Benutzer pNeuerLiebling)
{
lieblingsnutzer = pNeuerLiebling;
}
}
</code>

2017-05-08T17:26:44Z

Mgrifka: /* Definition */

[[Kategorie:endliche Automaten]]
[[Kategorie:Informatik-Q2]]
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Informatik]]

=Definition=
Eine '''Grammatik''' G wird durch ein 4-Tupel (N, T, S, P) definiert:
* N ist die Menge der '''Nichtterminalsymbole'''.
* T ist die Menge der '''Terminalsymbole'''.
* S ∈ N ist das '''Startsymbol'''.
* P ist die Menge der '''Produktionsregeln'''.

'''reguläre''' Grammatik: Grammatiken, bei denen alle Produktionen die folgenden Formen haben, sind regulär:
* A → aB      ''d.h. Nichtterminalsymbol wird ersetzt durch ein Terminalsymbol gefolgt von einem Nichtterminalsymbol'''
* A → a      ''d.h. Nichtterminalsymbol wird ersetzt durch ein Terminalsymbol.''
* A → ε      ''d.h. Nichtterminalsymbol wird ersetzt durch nichts. (ε steht für nichts.)''

=Beispiele=

==KGB-Sprache==

Die KGB-Sprache besteht aus allen Ziffernfolgen, die irgendwo die Zahlenkette "007" enhalten.

Die Grammatik G der KGB-Sprache kann wie folgt definiert werden:

* G= (N, T, S, P)
* '''Nichtterminalsymbole''' N = {S, A, B, C}
* '''Terminalsymbole''' T = {0,...,9}
* '''Startsymbol''' S = S
* '''Produktionsregeln P = {'''
** S → 0A | 0S | 1S | 2S | ... | 9S
** A → 0B
** B → 7C
** C → ε | 0C | ... | 9C
* '''}'''

===Beispiel für die Ableitung eines Wortes===
Dass das Wort "060074" zu der KGB-Sprache gehört, lässt sich durch folgende Ableitung zeigen:
* S → 0S → 06S → 060A → 0600B → 06007C → 06007
Bei der letzten Ableitung wurde das C durch nichts (ε) ersetzt.

==Beispiel für eine nicht-reguläre Grammatik==
Die folgende Grammatik für den KGB-Automaten ist nicht regulär:

* G= (N, T, S, P)
* '''Nichtterminalsymbole''' N = {S, A}
* '''Terminalsymbole''' T = {0,...,9}
* '''Startsymbol''' S = S
* '''Produktionsregeln P = {'''
** S → 007A | 0S | 1S | 2S | ... | 9S
** A → ε | 0A | ... | 9A
* '''}'''

Die unterstrichene Regel verstößt gegen die Anforderungen, denn vor dem Nicht-Terminalsymbol sind drei Terminalsymbole!

''Hinweis:''

''Diese nicht-reguläre Grammatik lässt sich in eine reguläre Grammatik überführen.''

''Das gilt aber nicht für jede nicht-reguläre Grammatik!''

=Beziehung zu deterministischen endlichen Automaten=
* '''Zu jeder [[reguläre Grammatik|regulären Grammatik]] gibt es einen deterministischen endlichen Automaten.''' 
** Dazu erstellt man aus der regulären Grammatik erst einen [[Nicht-deterministischer endlicher Automaten|Nicht-deterministischen endlichen Automaten]], indem man aus jedem Nichtterminalsymbol einen Zustand macht und aus jeder Produktionsregel einen Übergang.
** Aus dem [[Nicht-deterministischer endlicher Automaten|Nicht-deterministischen endlichen Automaten]] kann man einen deterministischen endlichen Automaten erstellen. Das ist mühsam, aber es ist bewiesen, dass das immer geht!
* '''Zu jedem deterministischen endlichen Automaten gibt es eine [[reguläre Grammatik]].'''
** Diese lässt sich leicht aus dem Übergangsgraphen konstruieren, indem man aus jedem Zustand ein Nichtterminalsymbol macht und aus jedem Übergang eine Regel (mit einem Terminalsymbol und einem Nichtterminalsymbol).

=Beziehung zu regulären Sprachen=
Aus der Beziehung zu den deterministischen endlichen Automaten folgt direkt:
* '''Jede reguläre Grammatik erzeugt eine reguläre Sprache.'''
** ''Denn zu jeder regulären Grammatik gibt es einen deterministischen endlichen Automaten, und dieser erkennt eine reguläre Sprache.''
* '''Zu jeder regulären Sprache gibt es eine reguläre Grammatik.'''
** ''reguläre Sprachen sind genau die Sprachen, die von deterministischen endlichen Automaten erkannt werden. Zu jedem deterministischen endlichen Automaten kann man eine reguläre Grammatik finden.''

Schriftliches Rechnen

2017-05-06T10:45:50Z

Mgrifka: /* ausführliches Erklärvideo */

Schriftliches Rechnen

2017-05-06T10:18:43Z

Mgrifka: /* ausführliches Erklärvideo */

[[Kategorie:Mathematik]]
[[Kategorie:Mathematik Unterstufe]]
[[Kategorie:Rechnen]]

In diesem Kapitel wird das '''schriftliche Rechnen''' erklärt. Das kennt ihr alle schon aus der Grundschule, aber manchmal vergisst man ja, wie das nochmal ging.

= Schriftliche Addition ("plus rechnen untereinander") =
Möchte man zwei (oder mehr) Zahlen schriftlich addieren, ist das wichtigste, dass man die Ziffern mit dem gleichen Stellenwert untereinander schreibt.
Also Einer unter Einer, Zehner unter Zehner, Hunderter unter Hunderter usw. Die [[Stellenwerttafel]] hat eine eigene Erklärseite.

Man fängt hinten an und addiert zuerst alle Einer. Wenn man dabei als Ergebnis auf 10 oder mehr kommt, muss man den Übertrag (Übertrag 1, wenn man bei Zahlen von 10 bis 19 gelandet ist / Übertrag 2, wenn man eine Zahl von 20 bis 29 heraus hatte usw.) in die nächste Stelle schreiben.

=== Beispiel ===

<math>
\begin{alignat}{5}
&~ \; ~ 6079 \\
+ & ~ \; ~ \; \,492 \\
+ &~ \; ~ 5267 \\
& ~ \,_1 ~ \,_2\,_1\\
& \hline\\
& 11838
\end{alignat}
</math>

=== ausführliches Erklärvideo ===

<iframe width="854" height="480" src="https://www.youtube.com/embed/ZJXtvCF7XrQ" frameborder="0" allowfullscreen></iframe>

Schriftliches Rechnen

2017-05-06T10:01:01Z

Mgrifka:

[[Kategorie:Mathematik]]
[[Kategorie:Mathematik Unterstufe]]
[[Kategorie:Rechnen]]

In diesem Kapitel wird das '''schriftliche Rechnen''' erklärt. Das kennt ihr alle schon aus der Grundschule, aber manchmal vergisst man ja, wie das nochmal ging.

= Schriftliche Addition ("plus rechnen untereinander") =
Möchte man zwei (oder mehr) Zahlen schriftlich addieren, ist das wichtigste, dass man die Ziffern mit dem gleichen Stellenwert untereinander schreibt.
Also Einer unter Einer, Zehner unter Zehner, Hunderter unter Hunderter usw. Die [[Stellenwerttafel]] hat eine eigene Erklärseite.

Man fängt hinten an und addiert zuerst alle Einer. Wenn man dabei als Ergebnis auf 10 oder mehr kommt, muss man den Übertrag (Übertrag 1, wenn man bei Zahlen von 10 bis 19 gelandet ist / Übertrag 2, wenn man eine Zahl von 20 bis 29 heraus hatte usw.) in die nächste Stelle schreiben.

=== Beispiel ===

<math>
\begin{alignat}{5}
&~ \; ~ 6079 \\
+ & ~ \; ~ \; \,492 \\
+ &~ \; ~ 5267 \\
& ~ \,_1 ~ \,_2\,_1\\
& \hline\\
& 11838
\end{alignat}
</math>

=== ausführliches Erklärvideo ===

<iframe width="854" height="480" src="https://www.youtube.com/embed/ZJXtvCF7XrQ" frameborder="0" allowfullscreen></iframe>

Schriftliches Rechnen

2017-05-06T08:46:01Z

Mgrifka: /* Beispiel */

Schriftliches Rechnen

2017-05-06T07:05:20Z

Mgrifka: Die Seite wurde neu angelegt: „Kategorie:Mathematik Kategorie:Mathematik Unterstufe Kategorie:Rechnen In diesem Kapitel wird das '''schriftliche Rechnen''' erklärt. Das kennt i…“

[[Kategorie:Mathematik]]
[[Kategorie:Mathematik Unterstufe]]
[[Kategorie:Rechnen]]

In diesem Kapitel wird das '''schriftliche Rechnen''' erklärt. Das kennt ihr alle schon aus der Grundschule, aber manchmal vergisst man ja, wie das nochmal ging.

= Schriftliche Addition ("plus rechnen untereinander") =
Möchte man zwei (oder mehr) Zahlen schriftlich addieren, ist das wichtigste, dass man die Ziffern mit dem gleichen Stellenwert untereinander schreibt.
Also Einer unter Einer, Zehner unter Zehner, Hunderter unter Hunderter usw. Die [[Stellenwerttafel]] hat eine eigene Erklärseite.

Man fängt hinten an und addiert zuerst alle Einer. Wenn man dabei als Ergebnis auf 10 oder mehr kommt, muss man den Übertrag (Übertrag 1, wenn man bei Zahlen von 10 bis 19 gelandet ist / Übertrag 2, wenn man eine Zahl von 20 bis 29 heraus hatte usw.) in die nächste Stelle schreiben.

=== Beispiel ===

<math>
\begin{alignat}{5}
&~ 1479 \\
+ & ~ \; \,892 \\
+ &~ 5267 \\
& \,_1\,_2 \,_1\\
& \hline\\
& 7638
\end{alignat}
</math>

Mathematik Unterstufe

2017-05-05T17:36:43Z

Mgrifka: Die Seite wurde neu angelegt: „Kategorie:Mathematik Kategorie:Mathematik-Unterstufe '''Willkommen bei der Seite der Unterstufe für Mathematik!''' == Themen == # Rechnen ## Schri…“

[[Kategorie:Mathematik]]
[[Kategorie:Mathematik-Unterstufe]]

'''Willkommen bei der Seite der Unterstufe für Mathematik!'''

== Themen ==
# Rechnen
## [[Schriftliches Rechnen]]
## [[Rechenausdrücke, Vorfahrtsregeln]]
## [[Rechnen mit negativen Zahlen]]
## [[Rechnen mit Brüchen]]
## [[Rechnen mit Dezimalzahlen]]
# Einheiten und Größen
## [[Zeiteinheiten und Gewichte]]
## [[Längeneinheiten (1D)]]
## [[Flächeneinheiten (2D)]]
## [[Volumeneinheiten (3D)]]
# Geometrie
## [[Senkrecht, parallel]]
## [[Flächen (2D)]]
### [[Dreiecke]]
### [[Vierecke]]
### [[Vielecke]]
### [[Kreise]]
### [[Winkel]]
## [[Körper (3D)]]
### [[Würfel]]
### [[Quader]]
## [[Symmetrie]]
# Statistische Daten
## [[Diagramme]]
## [[Anteile, Prozente, Häufigkeiten]]
## [[Mittelwerte]]

Hauptseite

2017-05-05T17:07:31Z

Mgrifka: /* Kurse / Klassen */

= SIBI-Wiki.de =
'''Willkommen beim Wiki des Siebengebirgsgymnasiums!'''

[http://sibi-honnef.de Homepage des Siebengebirgsgymnasiums]

== Wer kann hier mitarbeiten - und wie? ==
* Am SIBI-Wiki kann '''jede Schülerin / jeder Schüler / jede Lehrerin / jeder Lehrer des SIBI''' mitarbeiten.
* Wer mitarbeiten möchte, meldet sich bitte bei Herrn Kaibel ([[Datei:MailadresseAKaibel.jpg]]) und bekommt einen Account.
* Sobald man angemeldet ist, sieht man '''über der Seite''' den '''Reiter "Bearbeiten"''' und '''neben jedem Absatz''' den '''Link "Bearbeiten"'''. Einfach draufklicken und die entsprechende Seite bearbeiten!

== Für Newbies (=Neulinge) ==
* Im Bearbeiten-Modus sehen Wiki-Seiten erst einmal komisch aus.
* Aber: '''Wiki-Syntax ist wirklich einfach!''' Am besten das Cheat-Sheet runterladen, ausdrucken und beim Bearbeiten neben den PC legen!
** '''[http://sibi-leo.de/wiki/images/SIBI-wiki-cheat-sheet.pdf SIBI-wiki-cheat-sheet]'''
* '''Ausprobieren''' kann man das auf der '''[[Spielwiese]]'''. Da kann jeder editieren, wie er will. (Die Spielwiese gibt es übrigens auch in der Wikipedia!)

== Cheat-Sheet für Wiki-Syntax ==
* Auf dem folgenden Cheat-Sheet wird '''die wichtigste Wiki-Syntax auf einer DIN-A4-Seite''' zusammengefasst.
* Einfach runterladen, ausdrucken und neben den Rechner legen!
* '''[http://sibi-leo.de/wiki/images/SIBI-wiki-cheat-sheet.pdf SIBI-wiki-cheat-sheet]'''

==Fächer==
* Informatik
** [[:Kategorie:Informatik|Informatik]]
** [[:Kategorie:Informatik-Abitur|Informatik Abitur]]
* Mathematik
** [[:Kategorie:Mathematik|Mathematik]]
** [[:Kategorie:Mathematik-Fachschaft|Fachschaft Mathematik]]

== Kurse / Klassen ==
* Informatik
** [[Informatik Q2|Informatik Q2]]
** [[Informatik Q2 ab Abi 2017|Informatik Q2 ab Abi 2017]]
** [[Informatik Q1 LK|Informatik Q1 LK]]
** [[Informatik Q1 LK Abi ab 2017|Informatik Q1 LK ab Abi 2017]]
** [[Informatik Q1 GK|Informatik Q1 GK]]
** [[Informatik EF|Informatik EF]]
** [[:Kategorie:Informatik-09|Informatik 09]]
** [[:Kategorie:Informatik 8|Informatik 08]]

* Mathematik
** [[Mathematik Unterstufe|Mathematik Unterstufe (Klassen 5,6)]]
** [[Mathematik Mittelstufe|Mathematik Mittelstufe (Klassen 7,8,9)]]
** [[Mathematik Oberstufe| Mathematik Oberstufe]]
*** [[Mathematik EF|Mathematik EF]]
*** [[Mathematik Q1-Q2 GK|Mathematik Q1-Q2 GK]]
*** [[Mathematik Q1-Q2 LK|Mathematik Q1-Q2 LK]]

== Fragen? Anregungen? ==
Per Mail an Herrn Kaibel: [[File:MailadresseAKaibel.jpg]]

== Danke... ==
* an Fadel Tchalabi für das Aufsetzen und Maintenance dieses Wikis.
* ebenfalls an Fadel Tchalabi für sehr sehr viele Inhalte!

Dijkstra-Algorithmus

2016-08-11T07:02:46Z

Mgrifka: /* Implementierung */

[[Kategorie:Informatik]]
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Datenstrukturen(IF)]]

[[File:Deutschland-graph.png|thumb|Originalgraph |400px]]
[[File:Deutschland-graph-dijkstra-kassel.png|thumb|Ergebnis des Dijkstra-Algorithmus für Kassel |400px]]

Mit Hilfe des Dijkstra-Algorithmus kann man für einen Startknoten die kürzesten Wege zu allen anderen Knoten des Graphen bestimmen.

Der Dijkstra-Algorithmus ist wesentlich effizienter als die Suche nach einem kürzesten Weg mithilfe von [[Backtracking ab Abi 2017|Backtracking]]

Der Dijkstra-Algorithmus bezieht sich auf die Datenstruktur [[Graph]].

= Idee des Dijkstra-Algorithmus=
==Notwendige Datenstrukturen==
* Für jeden Knoten wird der Vorgänger und ein Wert <code>distanz</code> gespeichert; <code>distanz</code> gibt die bisher beste gefundene Distanz zum Startknoten an.
* '''gelbe Liste''': In dieser Liste werden Knoten gespeichert, für die schon ein Distanzwert vorliegt, deren Distanz zum Startknoten aber noch nicht abschließend festgelegt werden konnte. Die Knoten erscheinen in der gelben Liste gemäß ihrem Distanzwert, und zwar in aufsteigender Reihenfolge.
* '''rote Liste''': Man braucht eine Liste, in der alle Knoten gespeichert werden, deren Distanz zum Startknoten abschließend festgestellt wurde.

==Algorithmus==
# Die Distanz des Startknoten wird auf 0 gesetzt; der von allen anderen Knoten auf unendlich.
# Der Startknoten wird in die rote Liste eingefügt.
# Alle Nachbarknoten des Startknotens werden in die gelbe Liste eingefügt, und zwar gemäß ihrer Distanz zum Startknoten.
# Die folgenden Schritte laufen jetzt so lange, bis die gelbe Liste leer ist:
## den ersten Knoten aus der gelben Liste (im folgenden <code>ersterGelber</code>) entnehmen und in die rote Liste einfügen. Denn die Distanz dieses Knotens ist endgültig geklärt.
## für alle Nachbarknoten von <code>ersterGelber</code> überprüft man:
### wenn sie noch nicht in der gelben Liste sind: Distanz berechnen (=Distanz von <code>ersterGelber</code> plus Kantenlänge von <code>ersterGelber</code>) und dann in die gelbe Liste hinzufügen (=gemäß der Distanz einfügen)
### wenn sie schon in der gelben Liste sind: Überprüfen, ob die Distanz von <code>ersterGelber</code> plus Kantenlänge '''kleiner''' ist als die bisher gespeicherte Distanz: Dann hat man eine bessere Route gefunden! Die Distanz des Nachbarknoten wird dann entsprechend verbessert, wodurch sich seine Position in der gelben Liste verbessert.

==Kürzester Weg für einen beliebigen Knoten==
Die Distanz kann man direkt aus dem Knoten auslesen.

Den kürzesten Weg von einem beliebigen Knoten zum Startknoten kann man jetzt angeben, indem man sich von dem Knoten aus immer zum nächsten Vorgänger hangelt, bis mn schließlich beim Startknoten angekommen ist.

== Beispiel ==
Für den Startknoten Kassel sind die ersten Schritte des Dijkstra-Algorithmus die folgenden.

* Die '''rote Liste''' ist '''fett'' geschrieben und ist von oben nach unten zu lesen.
* Die '''gelbe Liste''' ist jeweils von links nach rechts zu lesen.
** Veränderungen in der gelben Liste sind unterstrichen.
In der gelben Liste wird in Klammern die aktuelle Distanz zum Startknoten und der Vorgängerknoten (als Nummernschild) angegeben.
* '''Kassel (0, --)''': Dortmund (160, KS), Hannover (167, KS), Frankfurt (193, KS), Wuerzburg (209, KS), Leipzig (250, KS)
* '''Dortmund (160, KS)''': Hannover (167, KS), Frankfurt (193, KS), Wuerzburg (209, KS), Leipzig (250, KS), Koeln (253, DO), Bremen (394, DO)
* '''Hannover (167, KS)''': Frankfurt (193, KS), Wuerzburg (209, KS), Leipzig (250, KS), Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Berlin (457, H)
* '''Frankfurt (193, KS)''': Wuerzburg (209, KS), Leipzig (250, KS), Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Karlsruhe (340, F), Berlin (457, H)
* '''Wuerzburg (209, KS)''': Leipzig (250, KS), Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Nuernberg (319, WÜ), Karlsruhe (340, F), Berlin (457, H)
* '''Leipzig (250, KS)''': Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Nuernberg (319, WÜ), Berlin (438, L)
* '''Koeln (253, DO)''': Bremen (289, H), Hamburg (317, H), Nuernberg (319, WÜ), Karlsruhe (340, F), Berlin (438, L)
* '''Bremen (289, H)''': Hamburg (317, H), Nuernberg (319, WÜ), Karlsruhe (340, F), Berlin (438, L)
* '''Hamburg (317, H)''': Nuernberg (319, WÜ), Karlsruhe (340, F), Berlin (438, L)
* '''Nuernberg (319, WÜ)''': Karlsruhe (340, F), Berlin (438, L), Muenchen (485, N), Stuttgart (527, N)
* '''Karlsruhe (340, F)''': Stuttgart (422, KA), Berlin (438, L), Muenchen (485, N)
* '''Stuttgart (422, KA)''': Berlin (438, L), Muenchen (485, N)
* '''Berlin (438, L)''': Muenchen (485, N)
* '''Muenchen (485, N)'''

Den kürzesten Weg von Kassel nach Stuttgart findet man jetzt, indem man in der roten Liste Stuttgart sucht und dann in der roten Liste "rückwärts" geht:

Stuttgart (422, KA) -> Karlsruhe (340, F) -> Frankfurt (193, KS) -> Kassel (0, --)

= Implementierung =
Diese Implementierung umfasst zwei Klassen:
* <code>DijkstraAlgorithmus</code>
* <code>DijkstraNode</code>
Die Klasse <code>DijkstraAlgorithmus</code> enthält eine (lange...) Methode <code>initGraph</code>, damit man das Ganze auch testen kann.

Klasse <code>DijkstraAlgorithmus</code>:

<code>
import graph.Graph;
import graph.GraphWithViewer;
import gui.GUI;
import linear.List;
import linear.ListWithViewer;

'''public class DijkstraAlgorithmus {'''
public GraphWithViewer graph;
List<DijkstraNode> gelbeListe;
List<DijkstraNode> roteListe;

'''public DijkstraAlgorithmus(){'''
initGraph();
}

'''public void dijkstra(String pStadt) {'''
gelbeListe = new ListWithViewer<>();
roteListe = new ListWithViewer<>();
DijkstraNode startNode = (DijkstraNode)graph.getNode(pStadt);
startNode.setDistanz(0);
gelbeListe.append(startNode);
while(!gelbeListe.isEmpty()){
gelbeListe.toFirst();
DijkstraNode ersterGelber = gelbeListe.getContent();
//System.out.println("ersterGelber: "+ersterGelber);
gelbeListe.remove();
ersterGelber.mark();
roteListe.append(ersterGelber);
List<GraphNode> nachbarn = graph.getNeighbours(ersterGelber);
nachbarn.toFirst();
while(nachbarn.hasAccess()){
DijkstraNode derNachbar = (DijkstraNode) nachbarn.getContent();
if (!derNachbar.isMarked()) {
//System.out.println("currentNeighbour: "+currentNeighbour);
double streckeErsterZumNachbar = graph.getEdgeWeight(ersterGelber, derNachbar);
if (ersterGelber.getDistanz() + streckeErsterZumNachbar < derNachbar.getDistanz()) {
// ueber derNachbar fuehrt eine kuerzere Strecke zu currentNeighbour!
derNachbar.setVorgaenger(ersterGelber);
derNachbar.setDistanz(ersterGelber.getDistanz() + streckeErsterZumNachbar);
inGelbeListeUpdaten(derNachbar);
}
}
nachbarn.next();
}
}
}

/**
* sorgt dafuer, dass node gemaess seiner Distanz
* die richtige Position in gelbeListe bekommt.
* wenn pNode noch gar nicht in gelbeListe enthalten ist,
* dann wird node an der richtigen Stelle eingefuegt.
*/
'''private void inGelbeListeUpdaten(DijkstraNode pNode) {'''
boolean inserted = false;
gelbeListe.toFirst();
while(gelbeListe.hasAccess()){
DijkstraNode aktuell = gelbeListe.getContent();
if(aktuell.getDistanz() >= pNode.getDistanz()){
gelbeListe.insert(pNode);
inserted = true;
break;
}
gelbeListe.next();
}
if(inserted){
// ggf. taucht pNode nochmal in der Liste auf!
// dann muss er entfernt werden!
while(gelbeListe.hasAccess()){
DijkstraNode aktuell = gelbeListe.getContent();
if(aktuell.getName().equals(pNode.getName())){
gelbeListe.remove();
break;
}
gelbeListe.next();
}
}
else{
// der Knoten wurde noch nicht eingefuegt!
gelbeListe.append(pNode);
}
}

/**
* erzeugt einen Graph, in dem nur die Dijkstra-Verbindungen eingetragen sind
* @param pGraph
* @param roteListe
* @return
*/
'''public GraphWithViewer zeigeDijkstraGraph(){'''
Graph pGraph = graph;
GraphWithViewer ergebnis = new GraphWithViewer();
List<GraphNode> nodes = pGraph.getNodes();
for(nodes.toFirst(); nodes.hasAccess(); nodes.next()){
ergebnis.addNode((DijkstraNode) nodes.getContent());
}
for(roteListe.toFirst(); roteListe.hasAccess(); roteListe.next()){
DijkstraNode aktuell = roteListe.getContent();
DijkstraNode vorgaenger = aktuell.getVorgaenger();
if(vorgaenger != null){
double distanz = pGraph.getEdgeWeight(pGraph.getNode(aktuell.getName()), pGraph.getNode(vorgaenger.getName()));
ergebnis.addEdge(ergebnis.getNode(aktuell.getName()),
ergebnis.getNode(vorgaenger.getName()),
distanz);
}
}
ergebnis.switchToISOMLayout();
return ergebnis;
}

'''private void initGraph(){'''
graph = new GraphWithViewer();

DijkstraNode dortmund = new DijkstraNode("Dortmund");
graph.addNode(dortmund);
DijkstraNode koeln = new DijkstraNode("Koeln");
graph.addNode(koeln);
DijkstraNode frankfurt = new DijkstraNode("Frankfurt");
graph.addNode(frankfurt);
DijkstraNode kassel = new DijkstraNode("Kassel");
graph.addNode(kassel);
DijkstraNode wuerzburg = new DijkstraNode("Wuerzburg");
graph.addNode(wuerzburg);
DijkstraNode bielefeld = new DijkstraNode("Bielefeld");
DijkstraNode hamburg = new DijkstraNode("Hamburg");
graph.addNode(hamburg);
DijkstraNode berlin = new DijkstraNode("Berlin");
graph.addNode(berlin);
DijkstraNode bremen = new DijkstraNode("Bremen");
graph.addNode(bremen);
DijkstraNode hannover = new DijkstraNode("Hannover");
graph.addNode(hannover);
DijkstraNode leipzig = new DijkstraNode("Leipzig");
graph.addNode(leipzig);
DijkstraNode nuernberg = new DijkstraNode("Nuernberg");
graph.addNode(nuernberg);
DijkstraNode stuttgart = new DijkstraNode("Stuttgart");
graph.addNode(stuttgart);
DijkstraNode muenchen = new DijkstraNode("Muenchen");
graph.addNode(muenchen);
DijkstraNode karlsruhe = new DijkstraNode("Karlsruhe");
graph.addNode(karlsruhe);

graph.addEdge(kassel, dortmund, 160);
graph.addEdge(dortmund, koeln, 93);
graph.addEdge(frankfurt, kassel, 193);
graph.addEdge(kassel, wuerzburg, 209);
graph.addEdge(wuerzburg, frankfurt, 119);
graph.addEdge(frankfurt, koeln, 189);
graph.addEdge(berlin, hamburg, 289);
graph.addEdge(hamburg, bremen, 119);
graph.addEdge(bremen, hannover, 122);
graph.addEdge(hannover, hamburg, 150);
graph.addEdge(berlin, hannover, 290);
graph.addEdge(berlin, leipzig, 188);
graph.addEdge(hannover, kassel, 167);
graph.addEdge(leipzig, kassel, 250);
graph.addEdge(dortmund, bremen, 234);
graph.addEdge(dortmund, hannover, 210);
graph.addEdge(leipzig, nuernberg, 278);
graph.addEdge(wuerzburg, nuernberg, 110);
graph.addEdge(nuernberg, muenchen, 166);
graph.addEdge(muenchen, stuttgart, 223);
graph.addEdge(nuernberg, stuttgart, 208);
graph.addEdge(stuttgart, karlsruhe, 82);
graph.addEdge(karlsruhe, frankfurt, 147);

// auf ein geeignetes Layout umstellen
graph.switchToISOMLayout();
}

'''public static void main(String[] args) {'''
DijkstraAlgorithmus da = new DijkstraAlgorithmus();
new GUI(da);
}
}
</code>

Klasse <code>DijkstraNode</code>:

<code>
import graph.GraphNode;

public class DijkstraNode extends GraphNode{

private DijkstraNode vorgaenger;
private double distanz;

public DijkstraNode(String pName) {
super(pName);
vorgaenger = null;
distanz = 100000000;
}

public void setDistanz(double pDistanz){
this.distanz = pDistanz;
}

public double getDistanz(){
return distanz;
}

public void setVorgaenger(DijkstraNode pNode){
this.vorgaenger = pNode;
}

public DijkstraNode getVorgaenger() {
return vorgaenger;
}

public String toString(){
String ergebnis = this.getName()+": "+this.distanz;
if(this.vorgaenger != null){
ergebnis += (" ("+vorgaenger.getName()+")");
}
return ergebnis;
}
}
</code>

Dijkstra-Algorithmus

2016-08-11T07:01:47Z

Mgrifka: Die Seite wurde neu angelegt: „Kategorie:Informatik Kategorie:Informatik-Abitur Kategorie:Datenstrukturen(IF) 400px [[File:De…“

[[Kategorie:Informatik]]
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Datenstrukturen(IF)]]

[[File:Deutschland-graph.png|thumb|Originalgraph |400px]]
[[File:Deutschland-graph-dijkstra-kassel.png|thumb|Ergebnis des Dijkstra-Algorithmus für Kassel |400px]]

Mit Hilfe des Dijkstra-Algorithmus kann man für einen Startknoten die kürzesten Wege zu allen anderen Knoten des Graphen bestimmen.

Der Dijkstra-Algorithmus ist wesentlich effizienter als die Suche nach einem kürzesten Weg mithilfe von [[Backtracking ab Abi 2017|Backtracking]]

Der Dijkstra-Algorithmus bezieht sich auf die Datenstruktur [[Graph]].

= Idee des Dijkstra-Algorithmus=
==Notwendige Datenstrukturen==
* Für jeden Knoten wird der Vorgänger und ein Wert <code>distanz</code> gespeichert; <code>distanz</code> gibt die bisher beste gefundene Distanz zum Startknoten an.
* '''gelbe Liste''': In dieser Liste werden Knoten gespeichert, für die schon ein Distanzwert vorliegt, deren Distanz zum Startknoten aber noch nicht abschließend festgelegt werden konnte. Die Knoten erscheinen in der gelben Liste gemäß ihrem Distanzwert, und zwar in aufsteigender Reihenfolge.
* '''rote Liste''': Man braucht eine Liste, in der alle Knoten gespeichert werden, deren Distanz zum Startknoten abschließend festgestellt wurde.

==Algorithmus==
# Die Distanz des Startknoten wird auf 0 gesetzt; der von allen anderen Knoten auf unendlich.
# Der Startknoten wird in die rote Liste eingefügt.
# Alle Nachbarknoten des Startknotens werden in die gelbe Liste eingefügt, und zwar gemäß ihrer Distanz zum Startknoten.
# Die folgenden Schritte laufen jetzt so lange, bis die gelbe Liste leer ist:
## den ersten Knoten aus der gelben Liste (im folgenden <code>ersterGelber</code>) entnehmen und in die rote Liste einfügen. Denn die Distanz dieses Knotens ist endgültig geklärt.
## für alle Nachbarknoten von <code>ersterGelber</code> überprüft man:
### wenn sie noch nicht in der gelben Liste sind: Distanz berechnen (=Distanz von <code>ersterGelber</code> plus Kantenlänge von <code>ersterGelber</code>) und dann in die gelbe Liste hinzufügen (=gemäß der Distanz einfügen)
### wenn sie schon in der gelben Liste sind: Überprüfen, ob die Distanz von <code>ersterGelber</code> plus Kantenlänge '''kleiner''' ist als die bisher gespeicherte Distanz: Dann hat man eine bessere Route gefunden! Die Distanz des Nachbarknoten wird dann entsprechend verbessert, wodurch sich seine Position in der gelben Liste verbessert.

==Kürzester Weg für einen beliebigen Knoten==
Die Distanz kann man direkt aus dem Knoten auslesen.

Den kürzesten Weg von einem beliebigen Knoten zum Startknoten kann man jetzt angeben, indem man sich von dem Knoten aus immer zum nächsten Vorgänger hangelt, bis mn schließlich beim Startknoten angekommen ist.

== Beispiel ==
Für den Startknoten Kassel sind die ersten Schritte des Dijkstra-Algorithmus die folgenden.

* Die '''rote Liste''' ist '''fett'' geschrieben und ist von oben nach unten zu lesen.
* Die '''gelbe Liste''' ist jeweils von links nach rechts zu lesen.
** Veränderungen in der gelben Liste sind unterstrichen.
In der gelben Liste wird in Klammern die aktuelle Distanz zum Startknoten und der Vorgängerknoten (als Nummernschild) angegeben.
* '''Kassel (0, --)''': Dortmund (160, KS), Hannover (167, KS), Frankfurt (193, KS), Wuerzburg (209, KS), Leipzig (250, KS)
* '''Dortmund (160, KS)''': Hannover (167, KS), Frankfurt (193, KS), Wuerzburg (209, KS), Leipzig (250, KS), Koeln (253, DO), Bremen (394, DO)
* '''Hannover (167, KS)''': Frankfurt (193, KS), Wuerzburg (209, KS), Leipzig (250, KS), Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Berlin (457, H)
* '''Frankfurt (193, KS)''': Wuerzburg (209, KS), Leipzig (250, KS), Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Karlsruhe (340, F), Berlin (457, H)
* '''Wuerzburg (209, KS)''': Leipzig (250, KS), Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Nuernberg (319, WÜ), Karlsruhe (340, F), Berlin (457, H)
* '''Leipzig (250, KS)''': Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Nuernberg (319, WÜ), Berlin (438, L)
* '''Koeln (253, DO)''': Bremen (289, H), Hamburg (317, H), Nuernberg (319, WÜ), Karlsruhe (340, F), Berlin (438, L)
* '''Bremen (289, H)''': Hamburg (317, H), Nuernberg (319, WÜ), Karlsruhe (340, F), Berlin (438, L)
* '''Hamburg (317, H)''': Nuernberg (319, WÜ), Karlsruhe (340, F), Berlin (438, L)
* '''Nuernberg (319, WÜ)''': Karlsruhe (340, F), Berlin (438, L), Muenchen (485, N), Stuttgart (527, N)
* '''Karlsruhe (340, F)''': Stuttgart (422, KA), Berlin (438, L), Muenchen (485, N)
* '''Stuttgart (422, KA)''': Berlin (438, L), Muenchen (485, N)
* '''Berlin (438, L)''': Muenchen (485, N)
* '''Muenchen (485, N)'''

Den kürzesten Weg von Kassel nach Stuttgart findet man jetzt, indem man in der roten Liste Stuttgart sucht und dann in der roten Liste "rückwärts" geht:

Stuttgart (422, KA) -> Karlsruhe (340, F) -> Frankfurt (193, KS) -> Kassel (0, --)

= Implementierung =
Diese Implementierung umfasst zwei Klassen:
* <code>DijkstraAlgorithmus</code>
* <code>DijkstraNode</code>
Die Klasse <code>DijkstraAlgorithmus</code> enthält eine (lange...) Methode <code>initGraph</code>, damit man das Ganze auch testen kann.

Klasse <code>DijkstraAlgorithmus</code>:

<code>
import graph.Graph;
import graph.GraphWithViewer;
import gui.GUI;
import linear.List;
import linear.ListWithViewer;

'''public class DijkstraAlgorithmus {'''
public GraphWithViewer graph;
List<DijkstraNode> gelbeListe;
List<DijkstraNode> roteListe;

'''public DijkstraAlgorithmus(){'''
initGraph();
}

'''public void dijkstra(String pStadt) {'''
gelbeListe = new ListWithViewer<>();
roteListe = new ListWithViewer<>();
DijkstraNode startNode = (DijkstraNode)graph.getNode(pStadt);
startNode.setDistanz(0);
gelbeListe.append(startNode);
while(!gelbeListe.isEmpty()){
gelbeListe.toFirst();
DijkstraNode ersterGelber = gelbeListe.getContent();
//System.out.println("ersterGelber: "+ersterGelber);
gelbeListe.remove();
ersterGelber.mark();
roteListe.append(ersterGelber);
List<GraphNode> nachbarn = graph.getNeighbours(ersterGelber);
nachbarn.toFirst();
while(nachbarn.hasAccess()){
DijkstraNode derNachbar = (DijkstraNode) nachbarn.getContent();
if (!derNachbar.isMarked()) {
//System.out.println("currentNeighbour: "+currentNeighbour);
double streckeErsterZumNachbar = graph.getEdgeWeight(ersterGelber, derNachbar);
if (ersterGelber.getDistanz() + streckeErsterZumNachbar < derNachbar.getDistanz()) {
// ueber derNachbar fuehrt eine kuerzere Strecke zu currentNeighbour!
derNachbar.setVorgaenger(ersterGelber);
derNachbar.setDistanz(ersterGelber.getDistanz() + streckeErsterZumNachbar);
inGelbeListeUpdaten(derNachbar);
}
}
nachbarn.next();
}
}
}

/**
* sorgt dafuer, dass node gemaess seiner Distanz
* die richtige Position in gelbeListe bekommt.
* wenn pNode noch gar nicht in gelbeListe enthalten ist,
* dann wird node an der richtigen Stelle eingefuegt.
*/
'''private void inGelbeListeUpdaten(DijkstraNode pNode) {'''
boolean inserted = false;
gelbeListe.toFirst();
while(gelbeListe.hasAccess()){
DijkstraNode aktuell = gelbeListe.getContent();
if(aktuell.getDistanz() >= pNode.getDistanz()){
gelbeListe.insert(pNode);
inserted = true;
break;
}
gelbeListe.next();
}
if(inserted){
// ggf. taucht pNode nochmal in der Liste auf!
// dann muss er entfernt werden!
while(gelbeListe.hasAccess()){
DijkstraNode aktuell = gelbeListe.getContent();
if(aktuell.getName().equals(pNode.getName())){
gelbeListe.remove();
break;
}
gelbeListe.next();
}
}
else{
// der Knoten wurde noch nicht eingefuegt!
gelbeListe.append(pNode);
}
}

/**
* erzeugt einen Graph, in dem nur die Dijkstra-Verbindungen eingetragen sind
* @param pGraph
* @param roteListe
* @return
*/
'''public GraphWithViewer zeigeDijkstraGraph(){'''
Graph pGraph = graph;
GraphWithViewer ergebnis = new GraphWithViewer();
List<GraphNode> nodes = pGraph.getNodes();
for(nodes.toFirst(); nodes.hasAccess(); nodes.next()){
ergebnis.addNode((DijkstraNode) nodes.getContent());
}
for(roteListe.toFirst(); roteListe.hasAccess(); roteListe.next()){
DijkstraNode aktuell = roteListe.getContent();
DijkstraNode vorgaenger = aktuell.getVorgaenger();
if(vorgaenger != null){
double distanz = pGraph.getEdgeWeight(pGraph.getNode(aktuell.getName()), pGraph.getNode(vorgaenger.getName()));
ergebnis.addEdge(ergebnis.getNode(aktuell.getName()),
ergebnis.getNode(vorgaenger.getName()),
distanz);
}
}
ergebnis.switchToISOMLayout();
return ergebnis;
}

'''private void initGraph(){'''
graph = new GraphWithViewer();

DijkstraNode dortmund = new DijkstraNode("Dortmund");
graph.addNode(dortmund);
DijkstraNode koeln = new DijkstraNode("Koeln");
graph.addNode(koeln);
DijkstraNode frankfurt = new DijkstraNode("Frankfurt");
graph.addNode(frankfurt);
DijkstraNode kassel = new DijkstraNode("Kassel");
graph.addNode(kassel);
DijkstraNode wuerzburg = new DijkstraNode("Wuerzburg");
graph.addNode(wuerzburg);
DijkstraNode bielefeld = new DijkstraNode("Bielefeld");
DijkstraNode hamburg = new DijkstraNode("Hamburg");
graph.addNode(hamburg);
DijkstraNode berlin = new DijkstraNode("Berlin");
graph.addNode(berlin);
DijkstraNode bremen = new DijkstraNode("Bremen");
graph.addNode(bremen);
DijkstraNode hannover = new DijkstraNode("Hannover");
graph.addNode(hannover);
DijkstraNode leipzig = new DijkstraNode("Leipzig");
graph.addNode(leipzig);
DijkstraNode nuernberg = new DijkstraNode("Nuernberg");
graph.addNode(nuernberg);
DijkstraNode stuttgart = new DijkstraNode("Stuttgart");
graph.addNode(stuttgart);
DijkstraNode muenchen = new DijkstraNode("Muenchen");
graph.addNode(muenchen);
DijkstraNode karlsruhe = new DijkstraNode("Karlsruhe");
graph.addNode(karlsruhe);

graph.addEdge(kassel, dortmund, 160);
graph.addEdge(dortmund, koeln, 93);
graph.addEdge(frankfurt, kassel, 193);
graph.addEdge(kassel, wuerzburg, 209);
graph.addEdge(wuerzburg, frankfurt, 119);
graph.addEdge(frankfurt, koeln, 189);
graph.addEdge(berlin, hamburg, 289);
graph.addEdge(hamburg, bremen, 119);
graph.addEdge(bremen, hannover, 122);
graph.addEdge(hannover, hamburg, 150);
graph.addEdge(berlin, hannover, 290);
graph.addEdge(berlin, leipzig, 188);
graph.addEdge(hannover, kassel, 167);
graph.addEdge(leipzig, kassel, 250);
graph.addEdge(dortmund, bremen, 234);
graph.addEdge(dortmund, hannover, 210);
graph.addEdge(leipzig, nuernberg, 278);
graph.addEdge(wuerzburg, nuernberg, 110);
graph.addEdge(nuernberg, muenchen, 166);
graph.addEdge(muenchen, stuttgart, 223);
graph.addEdge(nuernberg, stuttgart, 208);
graph.addEdge(stuttgart, karlsruhe, 82);
graph.addEdge(karlsruhe, frankfurt, 147);

// auf ein geeignetes Layout umstellen
graph.switchToISOMLayout();
}

'''public static void main(String[] args) {'''
DijkstraAlgorithmus da = new DijkstraAlgorithmus();
new GUI(da);
}
}
</code>

Klasse <code>DijktstraNode</code>:

<code>
import graph.GraphNode;

public class DijkstraNode extends GraphNode{

private DijkstraNode vorgaenger;
private double distanz;

public DijkstraNode(String pName) {
super(pName);
vorgaenger = null;
distanz = 100000000;
}

public void setDistanz(double pDistanz){
this.distanz = pDistanz;
}

public double getDistanz(){
return distanz;
}

public void setVorgaenger(DijkstraNode pNode){
this.vorgaenger = pNode;
}

public DijkstraNode getVorgaenger() {
return vorgaenger;
}

public String toString(){
String ergebnis = this.getName()+": "+this.distanz;
if(this.vorgaenger != null){
ergebnis += (" ("+vorgaenger.getName()+")");
}
return ergebnis;
}
}
</code>

Backtracking

2016-08-11T06:56:17Z

Mgrifka: /* Backtracking für kürzeste Wege auf Graphen */

[[Kategorie:Informatik]]
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Algorithmen]]

= Idee =
''Der folgende Text ist gekürzt aus der Wikipedia [http://de.wikipedia.org/wiki/Backtracking] übernommen. ''

Backtracking geht nach dem Versuch-und-Irrtum-Prinzip (''trial and error'') vor, das heißt, es wird versucht, eine erreichte Teillösung zu einer Gesamtlösung auszubauen. Wenn absehbar ist, dass eine Teillösung nicht zu einer endgültigen Lösung führen kann, wird der letzte Schritt beziehungsweise werden die letzten Schritte zurückgenommen, und es werden stattdessen alternative Wege probiert. Auf diese Weise ist sichergestellt, dass alle in Frage kommenden Lösungswege ausprobiert werden können

Backtracking wird am einfachsten rekursiv implementiert.

= Beschreibung des Algorithmus =
''Die folgende Beschreibung ist gekürzt und leicht verändert aus der Wikipedia [http://de.wikipedia.org/wiki/Backtracking] übernommen. ''

<code>
Teillösung ist zu Anfang leer.
Stufe ist 0.

'''Funktion FindeLoesung (Stufe, Teillösung)'''
1. Abbruchbedingung: Wenn die Stufe zu groß ist
oder es keinen Teil-Lösungsschritt mehr gibt.
2. Abbruchbedingung: Wenn eine Lösung erreicht wurde.
Bearbeite ggf. die Lösung!
3. wiederhole, solange es noch neue Teil-Lösungsschritte gibt:
a) Wähle einen neuen Teil-Lösungsschritt.
b) Erweitere Teillösung um Wahl.
c) rekursiver Aufruf: FindeLoesung(Stufe+1, Teillösung)
d) Mache die Erweiterung der Teillösung rückgängig
</code>

= Backtracking für kürzeste Wege auf Graphen =
Um kürzeste Wege auf Graphen zu bestimmen, kann man den Backtracking-Algorithmus verwenden. Allerdings ist dieser sehr langsam; effizienter wird das Problem mit dem [[Dijkstra-Algorithmus ab Abi 2017|Dijkstra-Algorithmus]] gelöst.

==Beispiel==
[[File:Graph-fuenf-staedte.png|thumb|Graph mit fünf Städten |310px]]
Gesucht ist die kürzeste Verbindung von '''Frankfurt''' nach '''Dortmund'''

Damit man keine Möglichkeit auslässt, geht man nach einer '''Ordnung''' vor - hier bietet es sich an, die möglichen Nachbarstädte nach dem Alphabet zu betrachten.

Dann ergibt sich für das Backtracking folgende Reihenfolge:
* Frankfurt -> Kassel -> Dortmund: ''merken!''
* Frankfurt -> Kassel -> Würzburg: ''Sackgasse''
* Frankfurt -> Köln -> Dortmund: ''kürzer, also merken!''
* Frankfurt -> Würzburg -> Kassel -> Dortmund: ''länger, also ignorieren''

== Backtracking-Algorithmus für den kürzesten Weg ==

Man braucht die folgenden Attribute:
* <code>besterWeg</code>: Hier wird der jeweils beste gefundene Weg gespeichert.
* <code>besteLaenge</code>: Die Länge von <code>besterWeg</code>
* <code>aktuellerWeg</code>: Der Weg, der gerade untersucht wird.
* <code>aktuelleLaenge</code>: Die Länge von <code>aktuellerWeg</code>

Mithilfe dieser lässt sich der Algorithmus so beschreiben:

<code>
'''findeKuerzestenWegBacktracking (pNode)'''
'''Abbruchbedingung:'''
Wenn pNode das Ziel ist ''(d.h. der Lösungsvektor ist vollständig!)''
dann vergleiche aktuellerWeg mit besterWeg
und aktualisiere diesen, wenn es nötig ist.
'''Betrachte der Reihe nach alle Nachbarn von pNode.'''
Für jeden Nachbarn wird folgendes getan:
- den Nachbar zu aktuellerWeg hinzufügen (''d.h. der Lösungsvektor wird erweitert!'')
- aktuelleLaenge entsprechend erhöhen
- den Nachbarn markieren
- '''findeKuerzstestenWegBacktracking (nachbar) aufrufen'''
- die Änderungen wieder rückgängig machen (''d.h. die Wahl wird rückgängig gemacht!'')
- den Nachbarn aus aktuellerWeg entfernen
- aktuelleDistanz wieder zurücksetzen
- die Markierung des Nachbarn entfernen
</code>

==Implementierung==
Die Implementierung setzt auf die Klasse [[Graph]] auf.

Damit während des Backtracking auf die wesentlichen Daten zugegriffen werden kann, werden diese in Attributen gespeichert.

Die wesentlichen Methoden sind die folgenden:
* die '''Rahmenmethode''' <code>kuerzestenWegFinden(String pStart, String pZiel)</code>: In der Rahmenmethode wird alles für das rekursive Backtracking vorbereitet.
* die '''rekursive Backtracking-Methode''' <code>kuerzestenWegFindenBacktracking(GraphNode pNode)</code>

<code>
'''// Attribute'''
public GraphWithViewer graph;

'''// Attribute fuer das Backtracking'''
public ListWithViewer<GraphNode> besterWeg;
public ListWithViewer<GraphNode> aktuellerWeg;
public int besteLaenge;
public int aktuelleLaenge;
public GraphNode start;
public GraphNode ziel;

'''//Methoden'''

'''public ListWithViewer<GraphNode> kuerzestenWegFinden(String pStart, String pZiel){'''
graph.resetMarks();

start = graph.getNode(pStart);
ziel = graph.getNode(pZiel);

besterWeg = new ListWithViewer<>();
aktuellerWeg = new ListWithViewer<>();

besteLaenge = 10000000;
aktuelleLaenge = 0;

start.mark();
aktuellerWeg.append(start);

kuerzestenWegFindenBacktracking(start);

return besterWeg;
}

'''private void kuerzestenWegFindenBacktracking(GraphNode pNode) {'''
if(pNode.equals(ziel)){
if(aktuelleLaenge < besteLaenge){
// besterWeg leeren
for(besterWeg.toFirst();!besterWeg.isEmpty();){
besterWeg.remove();
}
// aktuellerWeg in besterWeg kopieren
for(aktuellerWeg.toFirst();aktuellerWeg.hasAccess();aktuellerWeg.next()){
besterWeg.append(aktuellerWeg.getObject());
}
besteLaenge = aktuelleLaenge;
}
return;
}
List<GraphNode> nachbarn = graph.getNeighbours(pNode);
for(nachbarn.toFirst(); nachbarn.hasAccess(); nachbarn.next()){
GraphNode derNachbar = nachbarn.getContent();
if(!derNachbar.isMarked()){
derNachbar.mark();
aktuellerWeg.append(derNachbar);
double distanz = graph.getEdgeWeight(derNachbar, pNode);
aktuelleLaenge += distanz;

'''kuerzestenWegFindenBacktracking(derNachbar);'''

aktuelleLaenge -= distanz;
aktuellerWeg.toLast();
aktuellerWeg.remove();
derNachbar.unmark();
}
}
return;
}
</code>

=Backtracking für Arrays: Magisches Quadrat=
In ein '''magisches Quadrat''' werden die Zahlen von 1 bis 9 (bzw. 1 bis 16, 1 bis 25, ...) eingetragen.
Die Summe muss in jeder Zeile, Spalte und Diagonale gleich sein.

Lösungen dieses Problems lassen sich gut mit Backtracking finden.

==Implementierung==
Die folgende Implementierung löst ein 3x3 Quadrat.
* Als Datenstruktur muss nur das Quadrat bereitgestellt werden, das ein 3x3-Array ist.
* Die Stufen des Backtracking-Verfahrens sind hier die Felder; dabei gehen die Stufen von 0 bis 8.
* Aus der Stufe kann man die Koordinaten des Feldes berechnen.
* Das eigentliche Backtracking findet in der Methode <code>public void findeLoesung(int pStufe)</code> statt; diese Methode wird von der Rahmenmethode <code>public void findeLoesung()</code> aufgerufen.

<code>
public class MagischesQuadratFertig {

private int[][] quadrat;

MagischesQuadratFertig(){
quadrat = new int[3][3];
initialisiere();
}

public void initialisiere(){
for ( int y=0 ; y < 3 ; y++ ) {
for ( int x=0 ; x < 3 ; x++ ) {
quadrat[x][y] = 0;
}
}
}

public void findeLoesung(){
findeLoesung(0);
System.out.println("*** Loesung: ***");
this.ausgeben();
}

'''//Die eigentliche Backtracking-Methode!'''
'''public boolean findeLoesung(int pStufe){'''

ausgeben();

// Abbruch, wenn pStufe ueber das Quadrat hinausgeht.
if(pStufe == 3*3){
return false;
}

// aus pStufe die x-Koordinate und die y-Koordinate berechnen
int x = pStufe % 3;
int y = pStufe / 3;

// jetzt fuer pStude alle Moeglichkeiten durchlaufen,
// d.h. die Zahlen von 1 bis 9
for(int i=1; i<= 3*3; i++){
// die Zahl i an die richtige Stelle in das Quadrat eintragen
quadrat[x][y] = i;

// Wenn es die Zahl schon einmal gibt, dann zur naechsten Zahl weiter.
if(esGibtDoppelte()){
continue;
}

// wenn man ein magisches Quadrat gefunden hat, dann true zurueckgeben.
if(magisch()){
return true;
}

// es gibt keine Doppelten, aber das Quadrat ist (noch) nicht magisch
// d.h. man baut die Teilloesung weiter aus.
// Dafuer ein rekursiver Aufruf fuer die naechsthoehere Stufe.
// Der Aufruf gibt zurueck, ob das Ausbauen der Teilloesung zum Erfolg fuehrte.
boolean fertig = findeLoesung(pStufe + 1);
if(fertig){
return true;
}
} // end for

// Auf dieser Stufe wurden alle Zahlen von 1 bis 9 durchprobiert, ohne Erfolg.
// Man loescht die Information auf dieser Stufe...
quadrat[x][y] = 0;
// und gibt false zurueck
return false;
}

public boolean esGibtDoppelte(){
boolean[] dabei = new boolean[3*3+1];
for ( int y=0 ; y < 3 ; y++ ) {
for ( int x=0 ; x < 3 ; x++ ) {
int index = quadrat[x][y];
if(index != 0 && dabei[index]){
return true;
}
dabei[index] = true;
}
}
return false;
}

public boolean magisch(){
if(esGibtDoppelte()){
return false;
}
// Summen testen
int s=0, t=0;
// 1. Diagonale
for ( int x=0 ; x < 3 ; x++ ) s+=quadrat[x][x];
//2. Diagonale
for ( int x=0 ; x < 3 ; x++ ) t+=quadrat[3-x-1][x];
if (t != s) return false;
// Zeilen
for ( int y=0 ; y < 3 ; y++ ) {
int k=0;
for ( int x=0 ; x < 3 ; x++ ) {
k += quadrat[x][y];
}
if (k != s) return false;
}

for ( int x=0 ; x < 3 ; x++ ) {
int k=0;
for ( int y=0 ; y < 3 ; y++ ) {
k += quadrat[x][y];
}
if (k != s) return false;
}
System.out.println("*** It's magic!!! ***");
return true;
}

public void ausgeben(){
for ( int y=0 ; y < 3 ; y++ ) {
for ( int x=0 ; x < 3 ; x++ ) {
System.out.print(quadrat[x][y]);
}
System.out.print(" ");
}
System.out.println();
}

public static void main(String[] args) {
MagischesQuadratFertig mq = new MagischesQuadratFertig();
mq.findeLoesung();
}
}
</code>

=Aufgabe: Backtracking für Arrays: Rucksackproblem selber programmieren=
Das '''Rucksackproblem''' lässt anhand des folgenden Beispiels beschreiben:
* In einen Rucksack kann man 200kg laden (=ganz schön schwer...).
* Es gibt die folgenden Gewichte: 28, 57, 33, 18, 99, 42, 17, 52
* '''Welche Gewichte muss man in den Rucksack laden, damit die 200kg möglichst gut ausgenutzt, aber nicht überschritten werden?'''

==Implementierung zum Selbermachen==
Die folgende Implementierung hält neben <code>gewichte</code> und <code>maxGewicht</code> noch folgende Datenstrukturen bereit:
* <code>boolean[] dabei</code>: In diesem Array wird festgehalten, welche der Gewichte bei der aktuell untersuchten Lösung dabei sind.
* <code>int erreichtesGewicht</code>: Hier wird festgehalten, welches Gewicht die aktuell untersuchte Lösung hat.
* <code>boolean[] besteLoesung</code>: In diesem Array wird die bisher beste Loesung festgehalten.
* <code>int bestesGewicht</code>: Hier wird festgehalten, welches Gewicht die bisher beste Lösung hat.
Diese Variablen müssen natürlich im Laufe des Backtracking immer aktualisiert werden.

'''Die Implementierung ist noch nicht vollständig; der Backtracking-Teil muss hier noch programmiert werden; dafür muss die Methode <code>sucheBesteLoesung(int pStufe)</code> ergänzt werden.'''

'''Viel Spaß beim Programmieren!'''

<code>
public class Rucksackproblem {
public int[] gewichte = {28, 57, 33, 18, 99, 42, 17, 52};
public int maxGewicht = 200;

public boolean[] dabei = new boolean[gewichte.length];
public int erreichtesGewicht = 0;

public boolean[] besteLoesung = new boolean[gewichte.length];
public int bestesGewicht = 0;

public void sucheBesteLoesung(){
//Vorbereitung
for(int i=0; i<dabei.length; i++){
dabei[i] = false;
}
kopiereInBesteLoesung();
// los gehts!
sucheBesteLoesung(0);
System.out.println("*** Beste Loesung: ***");
ausgeben(besteLoesung);
}

public void sucheBesteLoesung(int pStufe) {
dabeiArrayAusgeben();
//TODO
}

public void ausgeben(boolean[] b){
System.out.print(berechneGewicht(b)+": ");
for(int i=0; i<dabei.length; i++){
if(b[i]){
System.out.print(gewichte[i]+",");
}
}
System.out.println();
}

public void dabeiArrayAusgeben(){
for(int i=0; i<dabei.length; i++){
if(dabei[i]){
System.out.print("+");
}
else{
System.out.print("-");
}
}
System.out.println();
}

public void kopiereInBesteLoesung(){
for(int i=0; i<dabei.length; i++){
besteLoesung[i] = dabei[i];
}
}

public int berechneGewicht(boolean[] p){
int ergebnis = 0;
for(int i=0; i<p.length; i++){
if(p[i]){
ergebnis += gewichte[i];
}
}
return ergebnis;
}

public static void main(String[] args) {
Rucksackproblem rp = new Rucksackproblem();
rp.sucheBesteLoesung();
}
}
</code>

Backtracking

2016-08-11T06:55:52Z

Mgrifka: Die Seite wurde neu angelegt: „Kategorie:Informatik Kategorie:Informatik-Abitur Kategorie:Algorithmen = Idee = ''Der folgende Text ist gekürzt aus der Wikipedia [http://de.wiki…“

[[Kategorie:Informatik]]
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Algorithmen]]

= Idee =
''Der folgende Text ist gekürzt aus der Wikipedia [http://de.wikipedia.org/wiki/Backtracking] übernommen. ''

Backtracking geht nach dem Versuch-und-Irrtum-Prinzip (''trial and error'') vor, das heißt, es wird versucht, eine erreichte Teillösung zu einer Gesamtlösung auszubauen. Wenn absehbar ist, dass eine Teillösung nicht zu einer endgültigen Lösung führen kann, wird der letzte Schritt beziehungsweise werden die letzten Schritte zurückgenommen, und es werden stattdessen alternative Wege probiert. Auf diese Weise ist sichergestellt, dass alle in Frage kommenden Lösungswege ausprobiert werden können

Backtracking wird am einfachsten rekursiv implementiert.

= Beschreibung des Algorithmus =
''Die folgende Beschreibung ist gekürzt und leicht verändert aus der Wikipedia [http://de.wikipedia.org/wiki/Backtracking] übernommen. ''

<code>
Teillösung ist zu Anfang leer.
Stufe ist 0.

'''Funktion FindeLoesung (Stufe, Teillösung)'''
1. Abbruchbedingung: Wenn die Stufe zu groß ist
oder es keinen Teil-Lösungsschritt mehr gibt.
2. Abbruchbedingung: Wenn eine Lösung erreicht wurde.
Bearbeite ggf. die Lösung!
3. wiederhole, solange es noch neue Teil-Lösungsschritte gibt:
a) Wähle einen neuen Teil-Lösungsschritt.
b) Erweitere Teillösung um Wahl.
c) rekursiver Aufruf: FindeLoesung(Stufe+1, Teillösung)
d) Mache die Erweiterung der Teillösung rückgängig
</code>

= Backtracking für kürzeste Wege auf Graphen =
Um kürzeste Wege auf Graphen zu bestimmen, kann man den Backtracking-Algorithmus verwenden. Allerdings ist dieser sehr langsam; effizienter wird das Problem mit dem [[Dijkstra-Algorithmus]] gelöst.

==Beispiel==
[[File:Graph-fuenf-staedte.png|thumb|Graph mit fünf Städten |310px]]
Gesucht ist die kürzeste Verbindung von '''Frankfurt''' nach '''Dortmund'''

Damit man keine Möglichkeit auslässt, geht man nach einer '''Ordnung''' vor - hier bietet es sich an, die möglichen Nachbarstädte nach dem Alphabet zu betrachten.

Dann ergibt sich für das Backtracking folgende Reihenfolge:
* Frankfurt -> Kassel -> Dortmund: ''merken!''
* Frankfurt -> Kassel -> Würzburg: ''Sackgasse''
* Frankfurt -> Köln -> Dortmund: ''kürzer, also merken!''
* Frankfurt -> Würzburg -> Kassel -> Dortmund: ''länger, also ignorieren''

== Backtracking-Algorithmus für den kürzesten Weg ==

Man braucht die folgenden Attribute:
* <code>besterWeg</code>: Hier wird der jeweils beste gefundene Weg gespeichert.
* <code>besteLaenge</code>: Die Länge von <code>besterWeg</code>
* <code>aktuellerWeg</code>: Der Weg, der gerade untersucht wird.
* <code>aktuelleLaenge</code>: Die Länge von <code>aktuellerWeg</code>

Mithilfe dieser lässt sich der Algorithmus so beschreiben:

<code>
'''findeKuerzestenWegBacktracking (pNode)'''
'''Abbruchbedingung:'''
Wenn pNode das Ziel ist ''(d.h. der Lösungsvektor ist vollständig!)''
dann vergleiche aktuellerWeg mit besterWeg
und aktualisiere diesen, wenn es nötig ist.
'''Betrachte der Reihe nach alle Nachbarn von pNode.'''
Für jeden Nachbarn wird folgendes getan:
- den Nachbar zu aktuellerWeg hinzufügen (''d.h. der Lösungsvektor wird erweitert!'')
- aktuelleLaenge entsprechend erhöhen
- den Nachbarn markieren
- '''findeKuerzstestenWegBacktracking (nachbar) aufrufen'''
- die Änderungen wieder rückgängig machen (''d.h. die Wahl wird rückgängig gemacht!'')
- den Nachbarn aus aktuellerWeg entfernen
- aktuelleDistanz wieder zurücksetzen
- die Markierung des Nachbarn entfernen
</code>

==Implementierung==
Die Implementierung setzt auf die Klasse [[Graph]] auf.

Damit während des Backtracking auf die wesentlichen Daten zugegriffen werden kann, werden diese in Attributen gespeichert.

Die wesentlichen Methoden sind die folgenden:
* die '''Rahmenmethode''' <code>kuerzestenWegFinden(String pStart, String pZiel)</code>: In der Rahmenmethode wird alles für das rekursive Backtracking vorbereitet.
* die '''rekursive Backtracking-Methode''' <code>kuerzestenWegFindenBacktracking(GraphNode pNode)</code>

<code>
'''// Attribute'''
public GraphWithViewer graph;

'''// Attribute fuer das Backtracking'''
public ListWithViewer<GraphNode> besterWeg;
public ListWithViewer<GraphNode> aktuellerWeg;
public int besteLaenge;
public int aktuelleLaenge;
public GraphNode start;
public GraphNode ziel;

'''//Methoden'''

'''public ListWithViewer<GraphNode> kuerzestenWegFinden(String pStart, String pZiel){'''
graph.resetMarks();

start = graph.getNode(pStart);
ziel = graph.getNode(pZiel);

besterWeg = new ListWithViewer<>();
aktuellerWeg = new ListWithViewer<>();

besteLaenge = 10000000;
aktuelleLaenge = 0;

start.mark();
aktuellerWeg.append(start);

kuerzestenWegFindenBacktracking(start);

return besterWeg;
}

'''private void kuerzestenWegFindenBacktracking(GraphNode pNode) {'''
if(pNode.equals(ziel)){
if(aktuelleLaenge < besteLaenge){
// besterWeg leeren
for(besterWeg.toFirst();!besterWeg.isEmpty();){
besterWeg.remove();
}
// aktuellerWeg in besterWeg kopieren
for(aktuellerWeg.toFirst();aktuellerWeg.hasAccess();aktuellerWeg.next()){
besterWeg.append(aktuellerWeg.getObject());
}
besteLaenge = aktuelleLaenge;
}
return;
}
List<GraphNode> nachbarn = graph.getNeighbours(pNode);
for(nachbarn.toFirst(); nachbarn.hasAccess(); nachbarn.next()){
GraphNode derNachbar = nachbarn.getContent();
if(!derNachbar.isMarked()){
derNachbar.mark();
aktuellerWeg.append(derNachbar);
double distanz = graph.getEdgeWeight(derNachbar, pNode);
aktuelleLaenge += distanz;

'''kuerzestenWegFindenBacktracking(derNachbar);'''

aktuelleLaenge -= distanz;
aktuellerWeg.toLast();
aktuellerWeg.remove();
derNachbar.unmark();
}
}
return;
}
</code>

=Backtracking für Arrays: Magisches Quadrat=
In ein '''magisches Quadrat''' werden die Zahlen von 1 bis 9 (bzw. 1 bis 16, 1 bis 25, ...) eingetragen.
Die Summe muss in jeder Zeile, Spalte und Diagonale gleich sein.

Lösungen dieses Problems lassen sich gut mit Backtracking finden.

==Implementierung==
Die folgende Implementierung löst ein 3x3 Quadrat.
* Als Datenstruktur muss nur das Quadrat bereitgestellt werden, das ein 3x3-Array ist.
* Die Stufen des Backtracking-Verfahrens sind hier die Felder; dabei gehen die Stufen von 0 bis 8.
* Aus der Stufe kann man die Koordinaten des Feldes berechnen.
* Das eigentliche Backtracking findet in der Methode <code>public void findeLoesung(int pStufe)</code> statt; diese Methode wird von der Rahmenmethode <code>public void findeLoesung()</code> aufgerufen.

<code>
public class MagischesQuadratFertig {

private int[][] quadrat;

MagischesQuadratFertig(){
quadrat = new int[3][3];
initialisiere();
}

public void initialisiere(){
for ( int y=0 ; y < 3 ; y++ ) {
for ( int x=0 ; x < 3 ; x++ ) {
quadrat[x][y] = 0;
}
}
}

public void findeLoesung(){
findeLoesung(0);
System.out.println("*** Loesung: ***");
this.ausgeben();
}

'''//Die eigentliche Backtracking-Methode!'''
'''public boolean findeLoesung(int pStufe){'''

ausgeben();

// Abbruch, wenn pStufe ueber das Quadrat hinausgeht.
if(pStufe == 3*3){
return false;
}

// aus pStufe die x-Koordinate und die y-Koordinate berechnen
int x = pStufe % 3;
int y = pStufe / 3;

// jetzt fuer pStude alle Moeglichkeiten durchlaufen,
// d.h. die Zahlen von 1 bis 9
for(int i=1; i<= 3*3; i++){
// die Zahl i an die richtige Stelle in das Quadrat eintragen
quadrat[x][y] = i;

// Wenn es die Zahl schon einmal gibt, dann zur naechsten Zahl weiter.
if(esGibtDoppelte()){
continue;
}

// wenn man ein magisches Quadrat gefunden hat, dann true zurueckgeben.
if(magisch()){
return true;
}

// es gibt keine Doppelten, aber das Quadrat ist (noch) nicht magisch
// d.h. man baut die Teilloesung weiter aus.
// Dafuer ein rekursiver Aufruf fuer die naechsthoehere Stufe.
// Der Aufruf gibt zurueck, ob das Ausbauen der Teilloesung zum Erfolg fuehrte.
boolean fertig = findeLoesung(pStufe + 1);
if(fertig){
return true;
}
} // end for

// Auf dieser Stufe wurden alle Zahlen von 1 bis 9 durchprobiert, ohne Erfolg.
// Man loescht die Information auf dieser Stufe...
quadrat[x][y] = 0;
// und gibt false zurueck
return false;
}

public boolean esGibtDoppelte(){
boolean[] dabei = new boolean[3*3+1];
for ( int y=0 ; y < 3 ; y++ ) {
for ( int x=0 ; x < 3 ; x++ ) {
int index = quadrat[x][y];
if(index != 0 && dabei[index]){
return true;
}
dabei[index] = true;
}
}
return false;
}

public boolean magisch(){
if(esGibtDoppelte()){
return false;
}
// Summen testen
int s=0, t=0;
// 1. Diagonale
for ( int x=0 ; x < 3 ; x++ ) s+=quadrat[x][x];
//2. Diagonale
for ( int x=0 ; x < 3 ; x++ ) t+=quadrat[3-x-1][x];
if (t != s) return false;
// Zeilen
for ( int y=0 ; y < 3 ; y++ ) {
int k=0;
for ( int x=0 ; x < 3 ; x++ ) {
k += quadrat[x][y];
}
if (k != s) return false;
}

for ( int x=0 ; x < 3 ; x++ ) {
int k=0;
for ( int y=0 ; y < 3 ; y++ ) {
k += quadrat[x][y];
}
if (k != s) return false;
}
System.out.println("*** It's magic!!! ***");
return true;
}

public void ausgeben(){
for ( int y=0 ; y < 3 ; y++ ) {
for ( int x=0 ; x < 3 ; x++ ) {
System.out.print(quadrat[x][y]);
}
System.out.print(" ");
}
System.out.println();
}

public static void main(String[] args) {
MagischesQuadratFertig mq = new MagischesQuadratFertig();
mq.findeLoesung();
}
}
</code>

=Aufgabe: Backtracking für Arrays: Rucksackproblem selber programmieren=
Das '''Rucksackproblem''' lässt anhand des folgenden Beispiels beschreiben:
* In einen Rucksack kann man 200kg laden (=ganz schön schwer...).
* Es gibt die folgenden Gewichte: 28, 57, 33, 18, 99, 42, 17, 52
* '''Welche Gewichte muss man in den Rucksack laden, damit die 200kg möglichst gut ausgenutzt, aber nicht überschritten werden?'''

==Implementierung zum Selbermachen==
Die folgende Implementierung hält neben <code>gewichte</code> und <code>maxGewicht</code> noch folgende Datenstrukturen bereit:
* <code>boolean[] dabei</code>: In diesem Array wird festgehalten, welche der Gewichte bei der aktuell untersuchten Lösung dabei sind.
* <code>int erreichtesGewicht</code>: Hier wird festgehalten, welches Gewicht die aktuell untersuchte Lösung hat.
* <code>boolean[] besteLoesung</code>: In diesem Array wird die bisher beste Loesung festgehalten.
* <code>int bestesGewicht</code>: Hier wird festgehalten, welches Gewicht die bisher beste Lösung hat.
Diese Variablen müssen natürlich im Laufe des Backtracking immer aktualisiert werden.

'''Die Implementierung ist noch nicht vollständig; der Backtracking-Teil muss hier noch programmiert werden; dafür muss die Methode <code>sucheBesteLoesung(int pStufe)</code> ergänzt werden.'''

'''Viel Spaß beim Programmieren!'''

<code>
public class Rucksackproblem {
public int[] gewichte = {28, 57, 33, 18, 99, 42, 17, 52};
public int maxGewicht = 200;

public boolean[] dabei = new boolean[gewichte.length];
public int erreichtesGewicht = 0;

public boolean[] besteLoesung = new boolean[gewichte.length];
public int bestesGewicht = 0;

public void sucheBesteLoesung(){
//Vorbereitung
for(int i=0; i<dabei.length; i++){
dabei[i] = false;
}
kopiereInBesteLoesung();
// los gehts!
sucheBesteLoesung(0);
System.out.println("*** Beste Loesung: ***");
ausgeben(besteLoesung);
}

public void sucheBesteLoesung(int pStufe) {
dabeiArrayAusgeben();
//TODO
}

public void ausgeben(boolean[] b){
System.out.print(berechneGewicht(b)+": ");
for(int i=0; i<dabei.length; i++){
if(b[i]){
System.out.print(gewichte[i]+",");
}
}
System.out.println();
}

public void dabeiArrayAusgeben(){
for(int i=0; i<dabei.length; i++){
if(dabei[i]){
System.out.print("+");
}
else{
System.out.print("-");
}
}
System.out.println();
}

public void kopiereInBesteLoesung(){
for(int i=0; i<dabei.length; i++){
besteLoesung[i] = dabei[i];
}
}

public int berechneGewicht(boolean[] p){
int ergebnis = 0;
for(int i=0; i<p.length; i++){
if(p[i]){
ergebnis += gewichte[i];
}
}
return ergebnis;
}

public static void main(String[] args) {
Rucksackproblem rp = new Rucksackproblem();
rp.sucheBesteLoesung();
}
}
</code>

Binärer Suchbaum

2016-08-10T08:09:09Z

Mgrifka: /* Eigenschaften eines Suchbaumes */

[[Kategorie:Informatik]]
[[Kategorie:Informatik-Q1]]
[[Kategorie:Datenstrukturen(IF)]]
[[Kategorie:Informatik-Abitur]]

[[File:Binbaum.jpg|thumb|Binärer Suchbaum mit 15 Elementen |600px]]

=Definition=
Ein binärer Suchbaum ist ein [[allgemeiner Binärbaum ab Abi 2017|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.

=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 (search)|Suchen von Elementen in einem Binären Suchbaum]]
* 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=
[[Medium:Dokumentation2017_BinarySearchTree_ComparableContent.pdf|Schnittstelle BinarySearchTree (PDF)]]
==Erläuterungen zur Schnittstelle ==
Die Schnittstelle des Zentralabiturs besteht aus zwei Klassen:
* <code>BinarySearchTree</code> ist der eigentliche binäre Suchbaum.
* <code>ComparableCOntent</code>: In einen <code>BinarySearchTree</code> können nur Objekte eingefügt werden, die die Schnittstelle <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.

=Beispiel: Verwendung von <code>BinarySearchTree</code> und <code>ComparableContent</code>=
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>ComparableContent</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.

<code>
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) {
Buch pBuch = pContent;
boolean ergebnis = false;
if(titel.equals(pBuch.getTitel())){
ergebnis = true;
}
return ergebnis;
}

public boolean isLess(Buch pContent) {
Buch pBuch = pContent;
boolean ergebnis = false;
if(titel.compareTo(pBuch.getTitel())<0){
ergebnis = true;
}
return ergebnis;
}

public boolean isGreater(Buch pContent) {
Buch pBuch = pContent;
boolean ergebnis = false;
if(titel.compareTo(pBuch.getTitel())>0){
ergebnis = true;
}
return ergebnis;
}
}
</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:

<code>
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;
}
}
</code>

'''Erläuterungen zur Methode <code>public Buch suche(String pTitel)</code>''':

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<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.
* Da <code>Buch</code> die Schnittstelle <code>ComparableContent</code> implementiert, kann man mithilfe von <code>dummyBuch</code> die Methode <code>search</code> aufrufen.
* <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!

=Die Klassen <code>BinarySearchTree</code> und <code>BSTNode</code>=

* Der BinarySearchTree ''hat'' einen <code>BSTNode</code> als einziges Attribut, er ''besteht'' also eigentlich nur aus einem <code>BSTNode</code>.
* Die Klasse <code>BSTNode</code> hat die Attribute <code>content</code> (Wurzelinhalt), <code>left</code> und <code>right</code> (linker und rechter Teilbaum).
* Analog zu den Klassen [[Queue ab Abi 2017|Queue]] und [[Stack ab Abi 2017|Stack]] wird die Verbindung der Elemente der Datenstruktur also über die Nodes (auch hier: innere (Hilfs-)Klasse) umgesetzt.

Der Beginn der Klasse <code>BinarySearchTree</code>:
<code>
public class BinarySearchTree<ContentType extends ComparableContent<ContentType>> {

private BSTNode<ContentType> node;

// usw...
</code>

Die innere (Hilfs-)Klasse <code>BSTNode</code>:
<code>
private class BSTNode<CT extends ComparableContent<CT>> {

private CT content;
private BinarySearchTree<CT> left, right;

public BSTNode(CT pContent) {
// Der Knoten hat einen linken und rechten Teilbaum, die
// beide von null verschieden sind. Also hat ein Blatt immer zwei
// leere Teilbaeume unter sich.
this.content = pContent;
left = new BinarySearchTree<CT>();
right = new BinarySearchTree<CT>();
}
}

</code>

==ComparableContent: Java-Quellcode==
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.)
<code>
public interface ComparableContent<ContentType> {
public boolean isEqual(ContentType pContent);
public boolean isLess(ContentType pContent);
public boolean isGreater(ContentType pContent);
}
</code>

* Die Methoden werden in <code>ContentType</code> nur deklariert, aber nicht implementiert!
* 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)=
Die Klasse <code>BinarySearchTree</code> bietet die Methode <code>search</code>, um Elemente im Baum zu suchen.

Ist das Element enthalten, wird es zurückgegeben. Dies mag auf den ersten Blick sinnlos erscheinen, bietet aber die Möglichkeit, sich ein Objekt mit einem bestimmten Attributwert zu holen, indem man zunächst ein Dummy-Objekt erstellt, das mit dem gesuchten Objekt nur in diesem Attributwert übereinstimmt und sich damit das zugehörige ''wirkliche Objekt'' aus dem <code>BinaryTree</code> sucht. (''Die überschriebene Methode <code>isEqual()</code> darf natürlich nur Gleichheit genau auf diesem Attribut testen!'') -> s. auch Beispiel oben: '''public Buch suche(String pTitel)'''!

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. (''In der Abiturklasse ist allerdings kein klassischer [[Binärbaum (Methoden) ab Abi 2017#Durchlaufen eines Pfades|Pfaddurchlauf]] (mit while-Schleife etc.) umgesetzt, sondern eine rekursive Variante gewählt worden, die aber auch nur den einen notwendigen Pfad durchläuft.'')

==Implementierung (LK)==

<code>
public ContentType search(ContentType pContent) {
if (this.isEmpty() || pContent == null) {
// Abbrechen, da es kein Element zu suchen gibt.
return null;
} else {
ContentType content = this.getContent();
if (pContent.isLess(content)) {
// Element wird im linken Teilbaum gesucht.
return this.getLeftTree().search(pContent);
} else if (pContent.isGreater(content)) {
// Element wird im rechten Teilbaum gesucht.
return this.getRightTree().search(pContent);
} else if (pContent.isEqual(content)) {
// Element wurde gefunden.
return content;
} else {
// Dieser Fall sollte nicht auftreten.
return null;
}
}
}
</code>

=Einfügen (insert)=
Um Elemente in einen binären Suchbaum einzufügen, muss man ausgehend von der Wurzel einen Pfad bis zu einem leeren Knoten abgehen und dort den eizufügenden Inhalt hineinschreiben. 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. In der Abiturklasse wird diese Strategie rekursiv umgesetzt.

== Implementierung (LK) ==
<code>
public void insert(ContentType pContent) {
if (pContent != null) {
if (isEmpty()) {
this.node = new BSTNode<ContentType>(pContent);
} else if (pContent.isLess(this.node.content)) {
this.node.left.insert(pContent);
} else if(pContent.isGreater(this.node.content)) {
this.node.right.insert(pContent);
}
}
}
</code>

=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!

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==
[[Datei:loeschen_von_elementen_aus_baeumen.png|400px|thumb|right|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'''
# Den richtigen Knoten suchen: '''K0'''. Außerdem braucht man den '''Vorgänger von K0'''
# Suche im linken Teilbaum von K0 den Knoten, der am weitesten rechts ist: '''K1'''. Außerdem braucht man den '''Vorgänger von K1'''
# Hänge den (linken!) Nachfolger von K1 an den Vorgänger von K1.
# K1 ersetzt jetzt K0, d.h. der Inhalt von K1 wird jetzt in den Knoten K0 geschrieben.

'''Ausnahmefälle'''

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

'''benötigte Methoden'''

# <code>public boolean istBlatt(BinaryTree pTree)</code>
# <code>public BinaryTree findeK0Vorgaenger(BinaryTree pTree, Object pObject)</code>
# <code>public BinaryTree findeK1Vorgaenger(BinaryTree pTree)</code>

===Implementierung===
<code>
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;
}
</code>

Binärer Suchbaum

2016-08-10T08:06:26Z

Mgrifka: /* Suchen (search) */

[[Kategorie:Informatik]]
[[Kategorie:Informatik-Q1]]
[[Kategorie:Datenstrukturen(IF)]]
[[Kategorie:Informatik-Abitur]]

[[File:Binbaum.jpg|thumb|Binärer Suchbaum mit 15 Elementen |600px]]

=Definition=
Ein binärer Suchbaum ist ein [[allgemeiner Binärbaum ab Abi 2017|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.

=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]]
* 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=
[[Medium:Dokumentation2017_BinarySearchTree_ComparableContent.pdf|Schnittstelle BinarySearchTree (PDF)]]
==Erläuterungen zur Schnittstelle ==
Die Schnittstelle des Zentralabiturs besteht aus zwei Klassen:
* <code>BinarySearchTree</code> ist der eigentliche binäre Suchbaum.
* <code>ComparableCOntent</code>: In einen <code>BinarySearchTree</code> können nur Objekte eingefügt werden, die die Schnittstelle <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.

=Beispiel: Verwendung von <code>BinarySearchTree</code> und <code>ComparableContent</code>=
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>ComparableContent</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.

<code>
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) {
Buch pBuch = pContent;
boolean ergebnis = false;
if(titel.equals(pBuch.getTitel())){
ergebnis = true;
}
return ergebnis;
}

public boolean isLess(Buch pContent) {
Buch pBuch = pContent;
boolean ergebnis = false;
if(titel.compareTo(pBuch.getTitel())<0){
ergebnis = true;
}
return ergebnis;
}

public boolean isGreater(Buch pContent) {
Buch pBuch = pContent;
boolean ergebnis = false;
if(titel.compareTo(pBuch.getTitel())>0){
ergebnis = true;
}
return ergebnis;
}
}
</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:

<code>
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;
}
}
</code>

'''Erläuterungen zur Methode <code>public Buch suche(String pTitel)</code>''':

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<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.
* Da <code>Buch</code> die Schnittstelle <code>ComparableContent</code> implementiert, kann man mithilfe von <code>dummyBuch</code> die Methode <code>search</code> aufrufen.
* <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!

=Die Klassen <code>BinarySearchTree</code> und <code>BSTNode</code>=

* Der BinarySearchTree ''hat'' einen <code>BSTNode</code> als einziges Attribut, er ''besteht'' also eigentlich nur aus einem <code>BSTNode</code>.
* Die Klasse <code>BSTNode</code> hat die Attribute <code>content</code> (Wurzelinhalt), <code>left</code> und <code>right</code> (linker und rechter Teilbaum).
* Analog zu den Klassen [[Queue ab Abi 2017|Queue]] und [[Stack ab Abi 2017|Stack]] wird die Verbindung der Elemente der Datenstruktur also über die Nodes (auch hier: innere (Hilfs-)Klasse) umgesetzt.

Der Beginn der Klasse <code>BinarySearchTree</code>:
<code>
public class BinarySearchTree<ContentType extends ComparableContent<ContentType>> {

private BSTNode<ContentType> node;

// usw...
</code>

Die innere (Hilfs-)Klasse <code>BSTNode</code>:
<code>
private class BSTNode<CT extends ComparableContent<CT>> {

private CT content;
private BinarySearchTree<CT> left, right;

public BSTNode(CT pContent) {
// Der Knoten hat einen linken und rechten Teilbaum, die
// beide von null verschieden sind. Also hat ein Blatt immer zwei
// leere Teilbaeume unter sich.
this.content = pContent;
left = new BinarySearchTree<CT>();
right = new BinarySearchTree<CT>();
}
}

</code>

==ComparableContent: Java-Quellcode==
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.)
<code>
public interface ComparableContent<ContentType> {
public boolean isEqual(ContentType pContent);
public boolean isLess(ContentType pContent);
public boolean isGreater(ContentType pContent);
}
</code>

* Die Methoden werden in <code>ContentType</code> nur deklariert, aber nicht implementiert!
* 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)=
Die Klasse <code>BinarySearchTree</code> bietet die Methode <code>search</code>, um Elemente im Baum zu suchen.

Ist das Element enthalten, wird es zurückgegeben. Dies mag auf den ersten Blick sinnlos erscheinen, bietet aber die Möglichkeit, sich ein Objekt mit einem bestimmten Attributwert zu holen, indem man zunächst ein Dummy-Objekt erstellt, das mit dem gesuchten Objekt nur in diesem Attributwert übereinstimmt und sich damit das zugehörige ''wirkliche Objekt'' aus dem <code>BinaryTree</code> sucht. (''Die überschriebene Methode <code>isEqual()</code> darf natürlich nur Gleichheit genau auf diesem Attribut testen!'') -> s. auch Beispiel oben: '''public Buch suche(String pTitel)'''!

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. (''In der Abiturklasse ist allerdings kein klassischer [[Binärbaum (Methoden) ab Abi 2017#Durchlaufen eines Pfades|Pfaddurchlauf]] (mit while-Schleife etc.) umgesetzt, sondern eine rekursive Variante gewählt worden, die aber auch nur den einen notwendigen Pfad durchläuft.'')

==Implementierung (LK)==

<code>
public ContentType search(ContentType pContent) {
if (this.isEmpty() || pContent == null) {
// Abbrechen, da es kein Element zu suchen gibt.
return null;
} else {
ContentType content = this.getContent();
if (pContent.isLess(content)) {
// Element wird im linken Teilbaum gesucht.
return this.getLeftTree().search(pContent);
} else if (pContent.isGreater(content)) {
// Element wird im rechten Teilbaum gesucht.
return this.getRightTree().search(pContent);
} else if (pContent.isEqual(content)) {
// Element wurde gefunden.
return content;
} else {
// Dieser Fall sollte nicht auftreten.
return null;
}
}
}
</code>

=Einfügen (insert)=
Um Elemente in einen binären Suchbaum einzufügen, muss man ausgehend von der Wurzel einen Pfad bis zu einem leeren Knoten abgehen und dort den eizufügenden Inhalt hineinschreiben. 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. In der Abiturklasse wird diese Strategie rekursiv umgesetzt.

== Implementierung (LK) ==
<code>
public void insert(ContentType pContent) {
if (pContent != null) {
if (isEmpty()) {
this.node = new BSTNode<ContentType>(pContent);
} else if (pContent.isLess(this.node.content)) {
this.node.left.insert(pContent);
} else if(pContent.isGreater(this.node.content)) {
this.node.right.insert(pContent);
}
}
}
</code>

=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!

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==
[[Datei:loeschen_von_elementen_aus_baeumen.png|400px|thumb|right|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'''
# Den richtigen Knoten suchen: '''K0'''. Außerdem braucht man den '''Vorgänger von K0'''
# Suche im linken Teilbaum von K0 den Knoten, der am weitesten rechts ist: '''K1'''. Außerdem braucht man den '''Vorgänger von K1'''
# Hänge den (linken!) Nachfolger von K1 an den Vorgänger von K1.
# K1 ersetzt jetzt K0, d.h. der Inhalt von K1 wird jetzt in den Knoten K0 geschrieben.

'''Ausnahmefälle'''

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

'''benötigte Methoden'''

# <code>public boolean istBlatt(BinaryTree pTree)</code>
# <code>public BinaryTree findeK0Vorgaenger(BinaryTree pTree, Object pObject)</code>
# <code>public BinaryTree findeK1Vorgaenger(BinaryTree pTree)</code>

===Implementierung===
<code>
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;
}
</code>

Binärer Suchbaum

2016-08-10T07:55:17Z

Mgrifka: /* Löschen (remove) */

[[Kategorie:Informatik]]
[[Kategorie:Informatik-Q1]]
[[Kategorie:Datenstrukturen(IF)]]
[[Kategorie:Informatik-Abitur]]

[[File:Binbaum.jpg|thumb|Binärer Suchbaum mit 15 Elementen |600px]]

=Definition=
Ein binärer Suchbaum ist ein [[allgemeiner Binärbaum ab Abi 2017|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.

=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]]
* 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=
[[Medium:Dokumentation2017_BinarySearchTree_ComparableContent.pdf|Schnittstelle BinarySearchTree (PDF)]]
==Erläuterungen zur Schnittstelle ==
Die Schnittstelle des Zentralabiturs besteht aus zwei Klassen:
* <code>BinarySearchTree</code> ist der eigentliche binäre Suchbaum.
* <code>ComparableCOntent</code>: In einen <code>BinarySearchTree</code> können nur Objekte eingefügt werden, die die Schnittstelle <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.

=Beispiel: Verwendung von <code>BinarySearchTree</code> und <code>ComparableContent</code>=
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>ComparableContent</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.

<code>
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) {
Buch pBuch = pContent;
boolean ergebnis = false;
if(titel.equals(pBuch.getTitel())){
ergebnis = true;
}
return ergebnis;
}

public boolean isLess(Buch pContent) {
Buch pBuch = pContent;
boolean ergebnis = false;
if(titel.compareTo(pBuch.getTitel())<0){
ergebnis = true;
}
return ergebnis;
}

public boolean isGreater(Buch pContent) {
Buch pBuch = pContent;
boolean ergebnis = false;
if(titel.compareTo(pBuch.getTitel())>0){
ergebnis = true;
}
return ergebnis;
}
}
</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:

<code>
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;
}
}
</code>

'''Erläuterungen zur Methode <code>public Buch suche(String pTitel)</code>''':

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<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.
* Da <code>Buch</code> die Schnittstelle <code>ComparableContent</code> implementiert, kann man mithilfe von <code>dummyBuch</code> die Methode <code>search</code> aufrufen.
* <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!

=Die Klassen <code>BinarySearchTree</code> und <code>BSTNode</code>=

* Der BinarySearchTree ''hat'' einen <code>BSTNode</code> als einziges Attribut, er ''besteht'' also eigentlich nur aus einem <code>BSTNode</code>.
* Die Klasse <code>BSTNode</code> hat die Attribute <code>content</code> (Wurzelinhalt), <code>left</code> und <code>right</code> (linker und rechter Teilbaum).
* Analog zu den Klassen [[Queue ab Abi 2017|Queue]] und [[Stack ab Abi 2017|Stack]] wird die Verbindung der Elemente der Datenstruktur also über die Nodes (auch hier: innere (Hilfs-)Klasse) umgesetzt.

Der Beginn der Klasse <code>BinarySearchTree</code>:
<code>
public class BinarySearchTree<ContentType extends ComparableContent<ContentType>> {

private BSTNode<ContentType> node;

// usw...
</code>

Die innere (Hilfs-)Klasse <code>BSTNode</code>:
<code>
private class BSTNode<CT extends ComparableContent<CT>> {

private CT content;
private BinarySearchTree<CT> left, right;

public BSTNode(CT pContent) {
// Der Knoten hat einen linken und rechten Teilbaum, die
// beide von null verschieden sind. Also hat ein Blatt immer zwei
// leere Teilbaeume unter sich.
this.content = pContent;
left = new BinarySearchTree<CT>();
right = new BinarySearchTree<CT>();
}
}

</code>

==ComparableContent: Java-Quellcode==
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.)
<code>
public interface ComparableContent<ContentType> {
public boolean isEqual(ContentType pContent);
public boolean isLess(ContentType pContent);
public boolean isGreater(ContentType pContent);
}
</code>

* Die Methoden werden in <code>ContentType</code> nur deklariert, aber nicht implementiert!
* 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)=
Die Klasse <code>BinarySearchTree</code> bietet die Methode <code>search</code>, um Elemente im Baum zu suchen.

Ist das Element enthalten, wird es zurückgegeben. Dies mag auf den ersten Blick sinnlos erscheinen, bietet aber die Möglichkeit, sich ein Objekt mit einem bestimmten Attributwert zu holen, indem man zunächst ein Dummy-Objekt erstellt, das mit dem gesuchten Objekt nur in diesem Attibutwert übereinstimmt und sich damit das zugehörige ''wirkliche Objekt'' aus dem <code>BinaryTree</code> sucht. (''Die überschriebene Methode <code>isEqual()</code> darf natürlich nur Gleichheit genau auf diesem Attribut testen!'') -> s. auch Beispiel oben: '''public Buch suche(String pTitel)'''!

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. (''In der Abiturklasse ist allerdings kein klassischer [[Binärbaum (Methoden) ab Abi 2017#Durchlaufen eines Pfades|Pfaddurchlauf]] (mit while-Schleife etc.) umgesetzt, sondern eine rekursive Variante gewählt worden, die aber auch nur den einen notwendigen Pfad durchläuft.'')

==Implementierung (LK)==

<code>
public ContentType search(ContentType pContent) {
if (this.isEmpty() || pContent == null) {
// Abbrechen, da es kein Element zu suchen gibt.
return null;
} else {
ContentType content = this.getContent();
if (pContent.isLess(content)) {
// Element wird im linken Teilbaum gesucht.
return this.getLeftTree().search(pContent);
} else if (pContent.isGreater(content)) {
// Element wird im rechten Teilbaum gesucht.
return this.getRightTree().search(pContent);
} else if (pContent.isEqual(content)) {
// Element wurde gefunden.
return content;
} else {
// Dieser Fall sollte nicht auftreten.
return null;
}
}
}
</code>

=Einfügen (insert)=
Um Elemente in einen binären Suchbaum einzufügen, muss man ausgehend von der Wurzel einen Pfad bis zu einem leeren Knoten abgehen und dort den eizufügenden Inhalt hineinschreiben. 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. In der Abiturklasse wird diese Strategie rekursiv umgesetzt.

== Implementierung (LK) ==
<code>
public void insert(ContentType pContent) {
if (pContent != null) {
if (isEmpty()) {
this.node = new BSTNode<ContentType>(pContent);
} else if (pContent.isLess(this.node.content)) {
this.node.left.insert(pContent);
} else if(pContent.isGreater(this.node.content)) {
this.node.right.insert(pContent);
}
}
}
</code>

=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!

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==
[[Datei:loeschen_von_elementen_aus_baeumen.png|400px|thumb|right|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'''
# Den richtigen Knoten suchen: '''K0'''. Außerdem braucht man den '''Vorgänger von K0'''
# Suche im linken Teilbaum von K0 den Knoten, der am weitesten rechts ist: '''K1'''. Außerdem braucht man den '''Vorgänger von K1'''
# Hänge den (linken!) Nachfolger von K1 an den Vorgänger von K1.
# K1 ersetzt jetzt K0, d.h. der Inhalt von K1 wird jetzt in den Knoten K0 geschrieben.

'''Ausnahmefälle'''

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

'''benötigte Methoden'''

# <code>public boolean istBlatt(BinaryTree pTree)</code>
# <code>public BinaryTree findeK0Vorgaenger(BinaryTree pTree, Object pObject)</code>
# <code>public BinaryTree findeK1Vorgaenger(BinaryTree pTree)</code>

===Implementierung===
<code>
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;
}
</code>