Welche Nachteile gibt es bei Baumstrukturen (Informatik)?

Die Datenstruktur ist mit relativ hohen Speicherkosten verbunden, weil im binären Fall zumindest zusätzlich zu jeder Node noch ein Pointer auf den linken- und rechten Teilbaum gespeichert werden muss. Bei nicht-binären Bäumen müssen noch mehr Pointer gespeichert werden.

Außerdem ist die Suche bei Bäumen relativ aufwendig, weil man im worst case den gesamten Baum durchlaufen muss. Wenn die Bäume bereits sortiert sind, ist die Suche zwar schneller als beispielsweise bei einer Liste zu realisieren, aber es entsteht der Sortierungsaufwand im Vorfeld.

Das Hauptproblem ist das degenerieren des Baumes bei wiederholten Einfüge- und Löschoperationen, bzw. der für die Reorganisation benötigte Aufwand, wenn man dies begrenzen möchte.

Weil in einer Antwort von der Speicherkomplexität gesprochen wird, man kann Bäume linearisieren.

Aufwendiges entfernen von Knoten z.B. Ja e nachdem welche Art Baum.