Rot-Schwarz-Bäume
Ein Rot-Schwarz-Baum ist eine Datentruktur, die in Form eines Baumes aufgebaut ist. Es gibt wichtige Unterschiede zwischen einem herkömmlichen binären Suchbaum und einem Rot-Schwarz-Baum. Die Grundoperationen wie DELETE und INSERT eines binären Suchbaumes werden in $O(n)$ realisiert. Dadurch ist gegeben, dass die Operationen schnell sind, wenn die Höhe des Baumes klein ist. Ist die Höhe des Baumes allerdings groß, kann es sein, dass die Operationen länger brauchen, weil Bäume in das Unendliche wachsen können. Dieses Problem werden von Rot-Schwarz-Bäumen behoben.
Es gibt fünf Eigenschaften die einen Rot-Schwarz-Baum ausmachen (Cormen 2010, S. 311):
- Jeder Knoten ist entweder rot oder schwarz.
- Die Wurzel ist schwarz.
- Jedes Blatt (Nil) ist schwarz.
- Wenn ein Knoten rot ist, dann sind seine beiden Kinder schwarz.
- Für jede Knoten enthalten alle einfachen Pfade, die an diesem Knoten starten und in einem Blatt des Teilbaumes dieses Knoten enden, die gleiche Anzahl schwarzer Knoten.
Einen Rot-Schwarz-Baum ist ein binärer Suchbaum, der jeweils pro Knoten ein zusätzliches Attribut gespeichert hat. Dieses Attribut dient zur Speicherung seiner Farbe. Die Farbe des Attributes kann entweder schwarz oder rot sein, daher auch der Name dieser besonderen Baum Datenstruktur. Durch diese Farbreihenfolge wird sichergestellt, dass kein Pfad doppelt so lang werden kann, dadurch ist der Baum balanciert. Die Anzahl der roten und schwarzen Knoten lässt sich jeweils mittels $log2(n+1)$ bestimmen. Dies ermöglicht eine maximale Tiefe von $log2(n+1)+log2(n+1)$. Das wiederum garantiert uns, dass wichtige Operationen wie DELETE und INSERT eine Laufzeit von $O(log2(n))$ haben. Ein Rot-Schwarz-Baum, der nur aus schwarzen Knoten besteht, erfüllt die Regeln nur dann, wenn dieser ausgeglichen ist, ansonsten läge ein binärer Suchbaum vor und kein Rot-Schwarz-Baum.
In der Praxis können hierfür die Attribute color, key, left, righ und parent festgelegt werden, um einen Knoten repräsentieren zu können. In der Programmiersprache Java werden Rot-Schwarz-Bäume von der Klasse RedBlackBST<Key extends Comparable<Key>, Value dargestellt.