Simulic
Deutsch

Binäre Suchbäume – Einfügen, Suchen, Löschen und Traversierung

InformatikAlgorithmen und ProblemlösenAlter 17–18

Wird geladen …

Mit meiner Klasse nutzen ✨ Mit KI anpassen Problem melden

Fügen Sie Schlüssel in einen binären Suchbaum ein, suchen und löschen Sie sie und verfolgen Sie den Vergleichspfad durch die Knoten, die Höhe des Baums und die Zahl der Vergleiche; beim Löschen eines Knotens mit 0, 1 oder 2 Kindern wird der Inorder-Nachfolger verwendet. Werden sortierte Schlüssel eingefügt, entartet der Baum zu einer Liste – eine Ergebnistabelle vergleicht das mit zufälliger und balancierter Einfügereihenfolge. Im Modus Baumtraversierung laufen Preorder, Inorder, Postorder und Levelorder Schritt für Schritt ab, und der Modus Ausdrucksbaum liefert Präfix-, Infix- und Postfixnotation.

Lektion: Binärbäume und binäre Suchbäume; Preorder-, Inorder-, Postorder- und Levelorder-Traversierung (Breitendurchlauf); Ausdrucksbäume und polnische Notation

Was sie zeigt

In einem binären Suchbaum sind alle Schlüssel im linken Teilbaum kleiner und alle Schlüssel im rechten Teilbaum größer als der Schlüssel des Knotens. Suchen, Einfügen und Löschen folgen daher einem einzigen Pfad ab der Wurzel und brauchen höchstens h + 1 Vergleiche, wobei h die Höhe ist. Zufällige Einfügereihenfolgen ergeben recht niedrige Bäume, sortierte Eingaben dagegen eine Kette, die so langsam ist wie die lineare Suche. Traversierungen besuchen jeden Knoten genau einmal: Die Tiefendurchläufe nutzen den Aufrufstapel einer rekursiven Funktion, die Levelorder eine Warteschlange, und bei Ausdrucksbäumen entstehen Präfix-, Infix- und Postfixnotation.

So funktioniert es

Geben Sie im Modus Binärer Suchbaum einen Schlüssel ein und klicken Sie auf Einfügen, Suchen oder Löschen; die Vergleiche werden Schritt für Schritt angezeigt. Wählen Sie eine Einfügereihenfolge und eine Anzahl der Schlüssel und klicken Sie dann auf Neuen Baum erstellen, um der Vergleichstabelle eine Zeile hinzuzufügen. Wählen Sie im Modus Baumtraversierung eine Traversierung und klicken Sie auf Abspielen oder Schritt. Im Modus Ausdrucksbaum wählen Sie einen Ausdruck oder geben einen eigenen ein.

Einstellbare Parameter

  • Modus Binärer Suchbaum, Baumtraversierung, Ausdrucksbaum
  • Anfängliche Einfügereihenfolge Zufällig, Aufsteigend (sortiert), Mittlerer Schlüssel zuerst (balanciert)
  • Anfängliche Anzahl der Schlüssel 3–15 Schlüssel
  • Anfangs einzufügende Schlüssel (Zahlen 1–99, z. B. 50 30 70; leer = automatisch erzeugt)
  • Traversierung Preorder (NLR), Inorder (LNR), Postorder (LRN), Levelorder (BFS)
  • Beispielausdruck (3 + 4) * 5, 3 + 4 * 5, (8 - 2) / (1 + 2), 2 * (x + 3) - y / 4, (a + b) * (c - d) ^ 2, Eigener
  • Eigener Ausdruck (leer = Beispielausdruck verwenden)
  • Ablaufgeschwindigkeit 0,5–4 Schritte/s

Fragen zum Erkunden

  1. Wie hoch ist der Baum, wenn sieben Schlüssel aufsteigend eingefügt werden, und wie viele Vergleiche braucht die Suche nach dem größten?
  2. Warum liefert die Inorder-Traversierung eines binären Suchbaums die Schlüssel immer in aufsteigender Reihenfolge?
  3. Wie schreibt man (3 + 4) * 5 in Postfixnotation, und warum braucht man dabei keine Klammern?

Ähnliche Simulationen