Zur MathePrisma-Startseite
Zur Modul-Startseite  


Binäre Suchbäume (Suchbaum 2)
 
 
 

 
 Binäre Suchbäume sind spezielle Binärbäume, deren Knoten  Datensätze mit Schlüsseln enthalten.
 
binärer Suchbaum
 
 Ein binärer Suchbaum ist ein Binärbaum, bei dem für jeden Knoten des Baumes gilt:
  • Alle Schüssel im linken Teilbaum sind kleiner, alle im rechten Teilbaum sind größer oder gleich dem Schlüssel in diesem Knoten.
 

 
 In der folgenden Aufgabe wurde ein binärer Suchbaum an einer Stelle 'gestört'. Finde diese Stelle und ändere den Schlüssel so, dass wieder ein binärer Suchbaum entsteht.
 
repariere den Suchbaum
Nach Anklicken eines Knotens kannst du dessen Schlüssel unten neu eingeben.



 

 
 Mit einem binären Suchbaum wollen wir die folgenden Operationen durchführen:
 
Operationen
 
  • suchen( s ) sucht einen Datensatz mit Schlüssel s im Suchbaum und liefert diesen Datensatz zurück.
  • einfügen( s ) fügt einen neuen Datensatz mit Schlüssel s in den binären Suchbaum ein.
  • löschen( s ) löscht den (ersten gefundenen) Datensatz mit Schlüssel s.
 
Sprachregelung
 
 Zur Vereinfachung unterscheiden wir jetzt nicht mehr zwischen Datensatz und Schlüssel und sprechen nur noch von den Schlüsseln.
 

 
 Für jede Operation muss man sich überlegen, wie sie algorithmisch auszuführen ist.
Wir starten mit dem Suchen.
 


Wo ist der Schlüssel?
Suche den vorgegebenen Schlüssel.
Klicke dazu der Reihe nach die zu besuchenden Knoten an. Einstieg ist immer die Wurzel.
Beachte:
  • Über den Knopf 'sichtbar/unsichtbar' kannst du eine Gesamtansicht des Binärbaumes ein- und ausblenden.
  • Wenn du die Gesamtansicht ausblendest, entspricht die Situation einer praktischen Implementierung.
  • Es kann sein, dass der zu suchende Schlüssel gar nicht vorhanden ist.
 

 
 Die Operation suchen( s ) läuft nach folgendem Algorithmus ab:
 
suchen

 
 Algorithmus zum Suchen von Schlüssel s



Beginne in der Wurzel.

  1. Ist s gleich dem aktuellen Knoten, so bist du fertig.
  2. Ist s kleiner, so nehme den linken Sohn des Knotens als aktuellen Knoten,
    andernfalls den rechten
  3. falls du in einem 'leeren' Knoten gelandet bist, stoppe (der gesuchte Schlüssel kommt nicht vor)
    andernfalls beginne von vorne (mit 1.)
 

 
 Das Einfügen geht fast genau so wie das Suchen.
 


Wo muss der Schlüssel hin?
Füge den vorgegebenen Schlüssel ein.
Klicke dazu der Reihe nach die zu besuchenden Knoten an. Start ist wieder die Wurzel.
 

 
 Hat es geklappt? Wie wurden bereits vorhandene Schlüssel eingefügt?
 
einfügen

 
 Algorithmus zum Einfügen von Schlüssel s



Beginne in der Wurzel.

  1. Ist der aktuellen Knoten leer, so lege s dort ab und stoppe
  2. Ansonsten: Ist s kleiner als der aktuelle Knoten, so nehme den linken Sohn als neuen aktuellen Knoten,
    andernfalls den rechten
  3. und beginne von vorn (mit 1.)
 

 
 Ist der Schlüssel s bereits im Suchbaum vorhanden, so wird er nochmals, aber weiter rechts unten, abgespeichert
 
Seite 4/11