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 O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.