14.4Ausgeglichene Bäume

Wie kann nun verhindert werden, dass ein Suchbaum bei einer »ungünstigen« Einfügereihenfolge entartet? Grundsätzlich kann man versuchen, den Baum nach jeder Einfüge- und Löschoperation auszugleichen. Dies kann jedoch zur Folge haben, dass unter Umständen jeder Knoten bewegt werden muss, wie dies in Abbildung 14–12 für das Einfügen des Elementes »1« dargestellt ist.

Wir werden im Folgenden drei Lösungsideen vorstellen, die dieses Problem vermeiden:

image

Abb. 14–12 Vollständiges Ausgleichen eines Baumes

Rot-Schwarz-Bäume

  • Rot-Schwarz-Bäume umgehen aufwendige Strukturänderungen zur Wiederherstellung der Ausgeglichenheit, indem ...

Get Algorithmen und Datenstrukturen, 6th Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial