Rot und Schwarz

TreeMap ist balancierter binärer Baum mit Rot/Schwarz-markierten Knoten.

Das ist eine Implementierung von B-Bäumen, genauer: (2,4)-Bäumen:

Übersetzung: 2-Knoten ist schwarz, 3-Knoten ist schwarz/rot oder rot/schwarz, 4-Knoten ist schwarz/rot/rot. Dann gilt:



Johannes Waldmann 2004-11-30