Bäume

← Informatik · Q1 · Thema 1.1

Wie findet ein Rechner in Millisekunden einen Eintrag unter Millionen? Von Binärbäumen und dem Suchbaum über das Durchlaufen und Löschen bis zu AVL-Bäumen, die sich mit Rotationen selbst im Gleichgewicht halten. Hier gibt es das Skript zum Nachlesen und eine Simulation zum Ausprobieren.

BinärbaumSuchbaumDurchlaufen LöschenAVL-BaumRotationen
▶ Simulation starten Skript öffnen (PDF)
402060 10305070

Inhalt des Skripts

  1. 1Bäume und BinärbäumeS. 2
  2. 2Der SuchbaumS. 3
  3. 3Durchlaufen eines BaumsS. 4
  4. 4Löschen im SuchbaumS. 6
  5. 5Wenn der Baum entartetS. 7
  6. 6AVL-Bäume und RotationenS. 8
  7. 6.4Einfügen und Löschen im AVL-BaumS. 10
  8. 7Der AVL-Baum in Python: SpezifikationS. 13
  9. 9ÜberblickS. 14
  10. 10Ausblick: andere BäumeS. 16
  11. 11–12Übungen mit LösungenS. 18

Simulation: AVL-Bäume

Zahlen einfügen und löschen, die Balance jedes Knotens ansehen und die Rotationen Schritt für Schritt verfolgen. Der AVL-Ausgleich lässt sich abschalten, um den entarteten Suchbaum zu vergleichen.

⤢ Im Vollbild öffnen

Werkzeuge