MathePrisma Logo

Binäre Suchbäume

Binäre Suchbäume

Suchspiel

Bei den neuen Regeln gewinnst du fast immer, wenn du eine Strategie verwendest, bei der du den in Frage kommenden Bereich jedes Mal halbierst.
Ein Beispiel:

der Bereich ist blau unterlegt

Algorithmisch kann man dies so formulieren:

binäre Suche

  1. Klicke auf das mittlere Kästchen des Bereichs.
  2. Falls du damit die gesuchte Zahl gefunden hast, stoppe.
  3. Andernfalls halbiere den Bereich:
    • ist die geklickte Zahl kleiner als die gesuchte
      so setze die linke Grenze des Bereichs auf das geklickte Kästchen
    • andernfalls setze die rechte Grenze des Bereichs auf das geklickte Kästchen
  4. ... und beginne von vorne (mit 1.)

Mitte?

Wenn der Bereich eine gerade Zahl von Kästchen enthält, gibt es kein 'mittleres'. Man wählt dann eines der beiden, die der Mitte am nächsten sind.

so schnell!

Mit Hilfe der Halbierungsstrategie kommt man in 93,75% der Fälle mit vier oder weniger Klicks zum Ziel. Für die anderen 6,25% braucht man fünf Klicks.
Wie kommt man darauf?
Weil man in jedem Schritt weiß, ob man links oder rechts weitersuchen muss, spricht man von binärer Suche.

Du hast diese Strategie vorher nicht verwendet?
Dann probiere sie hier aus.

Anwendung

Viele Aufgaben in der Datenverarbeitung kann man als Suche nach einem Datensatz mit einem bestimmten Schlüssel charakterisieren. In unserem Beispiel sind die Kästchen die Datensätze und die Zahlen die Schlüssel.
Die Abspeicherung von Datensätzen als Feld mit aufsteigenden Schlüsseln ist für das Suchen also besonders günstig.

Einfügen ist umständlich!

Aber: Will man einen neuen Datensatz einfügen, so wird es sehr aufwendig, die Anordnung zu erhalten. Im Schnitt muss man dann nämlich die Hälfte aller Datensätze um eine Position nach rechts verschieben.

Um eine Zahl einzufügen müssen erst alle Felder mit größeren Zahlen verschoben werden:

Ein ähnliches Problem taucht auf, wenn man einen Datensatz löscht.

Statt eines Feldes verwendet man deshalb besser die Datenstruktur binärer Suchbaum, die wir in diesem Modul behandeln.

binsuch1
binsuch2
binsuch3
binsuch4
binsuch5