• Artikel
• Bearbeiten
• Historie
• Druckansicht

Suchbaum

Suchbaum für die nachfolgenden Beispiele

• Schlüssel und Daten sind identisch
• Schlüssel sind Zeichen
• Binärbaum

Suchbaumeigenschaft

• Alle Schlüssel linker Nachfolger sind kleiner
• Alle Schlüssel rechter Nachfolger sind größer

Problem

• Suchbäume können entarten
  • Bei sortierten Eingaben (was in Praxis häufiger vorkommen kann)
  • Schlechtester Fall entspricht linearer Liste
• Lösung
  • Entartung vermeiden durch Reorganisation
  • Überprüfen der Höhen und bei Tendenz zum Entarten Reorganisation
  • Problem: Vollständige Reorganisation (zu ausgeglichenem Baum) sehr aufwendig

Ausgeglichene Bäume

• Rot-Schwarz-Baum
• AVL-Baum
• Splay-Tree?
• ...