Notizen

Rot-Schwarz-Bäume

tagsdatenstrukturen

Ein binärer Suchbaum heißt Rot-Schwarz-Baum, wenn gilt:

  1. Jeder Knoten ist entweder rot oder schwarz
  2. Die Wurzel ist Schwarz
  3. Jeder Leerverweis (RS-Blatt) ist schwarz
  4. Jeder rote Knoten hat ausschließlich schwarze Nachfolger
  5. Für jeden Knoten gilt: Jeder Pfad von zu einem RS-Blatt enthält die gleiche Anzahl an schwarzen Knoten
graph TB
classDef red stroke:#f00
17-->15 & 20
15-->16 & NULL
16:::red-->NULL & NULL
20-->19 & 25
19:::red-->NULL & NULL
25:::red-->NULL & NULL

Schwarz-Höhe

Die Schwarz-Höhe eines Knotens gibt die Anzahl schwarzer Knoten bis zu einem Blatt an.

Höhe von Rot-Schwarz-Bäumen

Sei ein RS-Baum mit Knoten, dann gilt:

Folgerungen

  • AVL-Bäume sind asymptotisch besser: Sie haben nur einen Faktor von statt
  • Trotzdem ist die Höhe beider Baumvarianten beschränkt auf
  • Dafür müssen RS-Bäume pro Knoten weniger Informationen speichern, nur 1 statt 2 Bit

Einfügen, Suchen und Entfernen

  • Diese Operationen haben analog zu AVL-Bäumen logarithmische Komplexität

Backlinks