Binärer Suchbaum

Term

Hierarchische Datenstruktur mit effizienten Suchoperationen

Ein binärer Suchbaum ist eine hierarchische Datenstruktur, in der jeder Knoten bis zu zwei Nachfolger hat und die Eigenschaft erfüllt, dass alle Elemente im linken Teilbaum kleiner und alle im rechten Teilbaum größer als das Wurzelelement sind. Diese Struktur ermöglicht effiziente Such-, Einfüge- und Löschoperationen mit durchschnittlicher Zeitkomplexität O(log n). Im schlimmsten Fall, bei dem der Baum zu einer Liste entartet, sinkt die Komplexität jedoch auf O(n). Binäre Suchbäume sind die Grundlage für viele fortgeschrittene Datenstrukturen wie AVL-Bäume und Rot-Schwarz-Bäume.

Andere Schreibweisen

Binary Search Tree, BST

In diesen Lernmodulen erwähnt

Quelle: AI Generated · Auto-extracted from FUTO modules: FI-AE 08 Algorithmen und Komplexität