Definition - Binärbaum

• Generalisierungen:
  • Wurzelbaum
  • Gerichteter Baum
• Involvierte Definitionen:
  • siehe auch B-Baum
• Veranstaltung: IR
• Referenz: @wagenpfeil2024 (p. 24)

⠀

Definition: Binärbaum

Als Binärbaum bezeichnen wir gerichtete Wurzelbäume, bei denen jeder Knoten höchstens zwei Teilbäume besitzt - einen linken und einen rechten.

Jeder dieser Teilbäume ist selbst wieder ein Binärbaum, und ein leerer Baum gilt ebenfalls als Binärbaum.

Im Beispiel wird ein Binärbaum als Struktur zur Repräsentation eines invertierten Indexes genutzt. Ein Problem bei der Nutzung ist, dass Binärbäume dazu neigen, unausgeglichen zu sein. Das führt dazu, dass Queries unnötig kostenintensiv werden.