Wymagania te gwarantują, że najdłuższa ścieżka od korzenia do liścia będzie co najwyżej dwukrotnie dłuższa niż najkrótsza. Wynika to wprost z własności: Zgodnie z własnością 4, żadna ścieżka nie zawiera dwóch czerwonych węzłów z rzędu, jednak może zawierać czarne. Stąd najkrótsza ścieżka od węzła zawiera wyłącznie czarnych węzłów. Zgodnie z własnością 5, druga ścieżka wychodząca z węzła musi zawierać także czarnych węzłów. Jedynym sposobem, aby miała ona inną łączną długość, jest umieszczenie pomiędzy każdą parą węzłów czarnych węzła czerwonego. Zgodnie z własnością 3, liść kończący obie ścieżki musi być czarny. Jeżeli węzeł jest czarny, wtedy w ścieżce możemy rozmieścić co najwyżej -1 węzłów czerwonych, w przeciwnym zaś razie będziemy mieli w niej czerwonych węzłów (wliczając w to sam ). Zatem łączna długość drugiej ścieżki może wynieść co najwyżej 2, gdzie jest długością pierwszej ścieżki zbudowanej wyłącznie z węzłów czarnych.
Można udowodnić, że dla węzłów głębokość drzewa czerwono-czarnego wyniesie najwyżej 2 log (+1), przez co elementarne operacje będą wykonywać się w czasie O(log ).
Operacje thumb|400px|Efekt działania rotacji w lewo i w prawo|right