Binärer Suchbaum - Versionsgeschichte

Akaibel am 11. März 2024 um 17:57 Uhr

2024-03-11T17:57:05Z

← Nächstältere Version		Version vom 11. März 2024, 17:57 Uhr
Zeile 10:		Zeile 10:
	* Diese Eigenschaft gilt auch für alle Teilbäume eines binären Suchbaumes.		* Diese Eigenschaft gilt auch für alle Teilbäume eines binären Suchbaumes.
	Wie ''kleiner'' bzw. ''größer'' definiert werden, hängt dabei vom Anwendungszusammenhang ab; bei Personen kann z.B. das Alter oder die alphabetische Ordnung des Nachnamens das wesentliche Ordnungskriterium sein.		Wie ''kleiner'' bzw. ''größer'' definiert werden, hängt dabei vom Anwendungszusammenhang ab; bei Personen kann z.B. das Alter oder die alphabetische Ordnung des Nachnamens das wesentliche Ordnungskriterium sein.

			=Erklärvideos=
			* [https://youtu.be/Hv2gABx0KAo Video 1: CelebritiesVerwaltung - Implementationsdiagramm]
			* [https://youtu.be/Cz1Nv8B1RH4 Video 2: CelebritiesVerwaltung - Implementierung]

	=Fachbegriffe=		=Fachbegriffe=

Akaibel am 15. Februar 2023 um 17:55 Uhr

2023-02-15T17:55:09Z

← Nächstältere Version		Version vom 15. Februar 2023, 17:55 Uhr
Zeile 5:		Zeile 5:

	[[File:Binbaum.jpg\|thumb\|Binärer Suchbaum mit 15 Elementen \|600px]]		[[File:Binbaum.jpg\|thumb\|Binärer Suchbaum mit 15 Elementen \|600px]]
	~~<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>~~
	=Definition=		=Definition=
	Ein binärer Suchbaum ist ein [[allgemeiner Binärbaum ab Abi 2017\|Binärbaum]] mit einer zusätzlichen Eigenschaft:		Ein binärer Suchbaum ist ein [[allgemeiner Binärbaum ab Abi 2017\|Binärbaum]] mit einer zusätzlichen Eigenschaft:

Akaibel am 23. Januar 2022 um 16:57 Uhr

2022-01-23T16:57:21Z

← Nächstältere Version		Version vom 23. Januar 2022, 16:57 Uhr
Zeile 58:		Zeile 58:
	==Implementierung==		==Implementierung==

	<code>		<code>
	public class Buch <u><b>implements ComparableContent<Buch></b></u>{		public class Buch <u><b>implements ComparableContent<Buch></b></u>{
	private String titel;		private String titel;
Zeile 92:		Zeile 92:
	}		}
	}		}
	</code>		</code>

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

	<code>		<code>
	public class Bibliothek{		public class Bibliothek{

Zeile 121:		Zeile 121:
	}		}
	}		}
	</code>		</code>

	'''Erläuterungen zur Methode <code>public Buch suche(String pTitel)</code>''':		'''Erläuterungen zur Methode <code>public Buch suche(String pTitel)</code>''':
Zeile 135:		Zeile 135:
	=ComparableContent: Java-Quellcode=		=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.)		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>		<code>
	public interface ComparableContent<ContentType> {		public interface ComparableContent<ContentType> {
	public boolean isEqual(ContentType pContent);		public boolean isEqual(ContentType pContent);
Zeile 141:		Zeile 141:
	public boolean isGreater(ContentType pContent);		public boolean isGreater(ContentType pContent);
	}		}
	</code>		</code>

	* Die Methoden werden in <code>ContentType</code> sind '''abstrakte Methoden''', d.h. sie werden nur deklariert, aber nicht implementiert!		* Die Methoden werden in <code>ContentType</code> sind '''abstrakte Methoden''', d.h. sie werden nur deklariert, aber nicht implementiert!
Zeile 155:		Zeile 155:
	Die Methode <code>search</code> lässt sich - genauso wie die Methode <code>insert</code> - mit einem Pfaddurchlauf realisieren:		Die Methode <code>search</code> lässt sich - genauso wie die Methode <code>insert</code> - mit einem Pfaddurchlauf realisieren:

	<code>		<code>
	'''public ContentType search(ContentType pContent) {'''		'''public ContentType search(ContentType pContent) {'''
	BinaryTree<ContentType b = myTree;		BinaryTree<ContentType b = myTree;
Zeile 176:		Zeile 176:
	return null;		return null;
	}		}
	</code>		</code>

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

	<code>		<code>
	public void insert(ContentType pContent) {		public void insert(ContentType pContent) {
	BinaryTree<ContentType> b = myTree;		BinaryTree<ContentType> b = myTree;
Zeile 197:		Zeile 197:
	b.setContent(pContent);		b.setContent(pContent);
	}		}
	</code>		</code>

	=Löschen (remove)=		=Löschen (remove)=
Zeile 241:		Zeile 241:

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

Akaibel: /* ComparableContent: Java-Quellcode */

2019-06-23T13:23:38Z

ComparableContent: Java-Quellcode

← Nächstältere Version		Version vom 23. Juni 2019, 13:23 Uhr
Zeile 143:		Zeile 143:
	</code>		</code>

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

Akaibel am 23. Juni 2019 um 13:22 Uhr

2019-06-23T13:22:55Z

← Nächstältere Version		Version vom 23. Juni 2019, 13:22 Uhr
Zeile 11:		Zeile 11:
	* Diese Eigenschaft gilt auch für alle Teilbäume eines binären Suchbaumes.		* Diese Eigenschaft gilt auch für alle Teilbäume eines binären Suchbaumes.
	Wie ''kleiner'' bzw. ''größer'' definiert werden, hängt dabei vom Anwendungszusammenhang ab; bei Personen kann z.B. das Alter oder die alphabetische Ordnung des Nachnamens das wesentliche Ordnungskriterium sein.		Wie ''kleiner'' bzw. ''größer'' definiert werden, hängt dabei vom Anwendungszusammenhang ab; bei Personen kann z.B. das Alter oder die alphabetische Ordnung des Nachnamens das wesentliche Ordnungskriterium sein.
			=Fachbegriffe=

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

	=Eigenschaften eines Suchbaumes=		=Eigenschaften eines Suchbaumes=

	'''Suchen:'''		'''Suchen:'''

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

Akaibel: /* Implementierung von insert(LK) */

2019-04-03T10:06:17Z

Implementierung von insert(LK)

@@ Zeile 176: / Zeile 176: @@
 </code>
-= Implementierung von insert(LK) =
+== Implementierung von insert(LK) ==
-Um Elemente in einen binären Suchbaum einzufügen, muss man ausgehend von der Wurzel einen Pfad bis zu einem leeren Knoten abgehen und dort den einzufü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.
+Die Methode <code>insert</code> lässt sich - genauso wie die Methode <code>search</code> - mit einem Pfaddurchlauf realisieren:
 <code>
@@ Zeile 226: / Zeile 196: @@
+     }
 </code>
 =Löschen (remove)=

Akaibel: /* Implementierung von search (LK) */

2019-04-03T10:02:38Z

Implementierung von search (LK)

← Nächstältere Version		Version vom 3. April 2019, 10:02 Uhr
Zeile 151:		Zeile 151:

	==Implementierung von search (LK)==		==Implementierung von search (LK)==
	Die ~~'''Rahmenmethode''' delegiert~~ die ~~Aufgabe an eine rekursive~~ Methode~~, an die als Parameter~~ <code>~~myTree~~</code> ~~übergeben wird.~~		Die Methode <code>search</code> lässt sich - genauso wie die Methode <code>insert</code> - mit einem Pfaddurchlauf realisieren:

	~~Die rekursive Methode geht einen Pfad ab, bis sie auf das gesuchte Element oder auf einen leeren Knoten trifft.~~

	<code>		<code>
	'''public ContentType search(ContentType pContent) {'''		'''public ContentType search(ContentType pContent) {'''
	~~return search(myTree, pContent);~~		BinaryTree<ContentType b = myTree;
	}		while( ! b.isEmpty()){
			ContentType wurzel = b.getContent();
	~~'''public ContentType search(~~BinaryTree<ContentType~~> pTree, ContentType pContent){'''~~		if(pContent.isEqual(wurzel)){
	~~// Abbruchbedingung: leerer Baum oder pContent ist null~~		// gefunden!
	if (~~pTree~~.isEmpty() ~~\|\| pContent == null~~) {		return wurzel;
	~~return null;~~		}
	}		if(pContent.isLess(wurzel)){
			// links abbiegen
	ContentType wurzel = ~~pTree~~.getContent();		b = b.getLeftTree();
			}
	~~// Abbruchbedingung: die Wurzel enthaelt das Gesuchte!~~		else{
	if(pContent.isEqual(wurzel)){		// rechts abbiegen
	return wurzel;		b = b.getRightTree();
	}		}

	~~// rekursive Aufrufe - entweder fuer den linken oder den rechten Teilbaum~~
	if (pContent.isLess(wurzel)) {
	// ~~Element wird im linken Teilbaum gesucht.~~
	~~ContentType links~~ = ~~search(pTree~~.getLeftTree(~~), pContent~~);
	~~return links;~~
	}
	~~if (pContent.isGreater(wurzel))~~ {
	// ~~Element wird im rechten Teilbaum gesucht.~~
	~~ContentType rechts~~ = ~~search(pTree~~.getRightTree(~~), pContent~~);
	~~return rechts;~~
	}		}
	// ~~Dieser Fall sollte~~ nicht ~~auftreten.~~		// nicht gefunden!
	return null;		return null;
	}		}
	</code>		</code>

Akaibel: /* Implementierung */

2019-03-11T20:16:36Z

Implementierung

← Nächstältere Version		Version vom 11. März 2019, 20:16 Uhr
Zeile 78:		Zeile 78:
	}		}

	<b><u>public boolean isEqual(Buch pContent) {</u>		<b><u>public boolean isEqual(Buch pContent) {</u></b>
	~~<u>Buch pBuch = pContent;~~</u>		<b>return (titel.equals(pBuch.getTitel());</b>
	~~boolean ergebnis = false;~~
	if(titel.equals(pBuch.getTitel())){
	~~ergebnis = true;~~
	}
	~~return ergebnis~~;
	}		}

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

	<u>public boolean isGreater(Buch pContent) {</u>		<b><u>public boolean isGreater(Buch pContent) {</u></b>
	~~<u>Buch pBuch = pContent;~~</u>		<b>return(titel.compareTo(pBuch.getTitel())>0);</b>
	~~boolean ergebnis = false;~~		}
	if(titel.compareTo(pBuch.getTitel())>0){
	~~ergebnis = true;~~
	}
	~~return ergebnis~~;
	}</b>
	}		}
	</code>		</code>

Akaibel: /* Implementierung von insert(LK) */

2018-03-27T15:52:46Z

Implementierung von insert(LK)

← Nächstältere Version		Version vom 27. März 2018, 15:52 Uhr
Zeile 241:		Zeile 241:
	BinaryTree<ContentType> b = myTree;		BinaryTree<ContentType> b = myTree;
	'''while(!b.isEmpty()){'''		'''while(!b.isEmpty()){'''
	~~int~~ wurzel = b.getContent();		ContentType wurzel = b.getContent();
	'''// UPDATE von b'''		'''// UPDATE von b'''
	if(pContent.isLess(wurzel)){		if(pContent.isLess(wurzel)){

Akaibel: /* Implementierung von insert(LK) */

2018-03-27T15:52:14Z

Implementierung von insert(LK)

← Nächstältere Version		Version vom 27. März 2018, 15:52 Uhr
Zeile 236:		Zeile 236:

	Man kann das Einfügen auch mit einer while-Schleife realisieren. Dann braucht man keine Rahmenmethode.		Man kann das Einfügen auch mit einer while-Schleife realisieren. Dann braucht man keine Rahmenmethode.


	<code>		<code>
Zeile 255:		Zeile 254:
	}		}
	</code>		</code>

			''Was besser ist?! Genau das, was einem mehr liegt!''<br/>
			''Allgemein gilt:''
			* ''Die <u>rekursive</u> Methode hat den Vorteil, dass die bei Bäumen für fast alles (außer Levelorder) funktioniert.''<br/>
			* ''Mit der <u>while-Schleife</u> kann man <u>nur bei einem Pfaddurchlauf</u> hantieren.''

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