red-black tree: drzewo czerwono-czarne

Abstrakcyjna reprezentacja drzew 2-3-4 (2-3-4-tree) w postaci binarnych drzew poszukiwań, których każdy węzeł zawiera dodatkowy bit informacji opisujący jego kolor (typ). W drzewie takim każdy węzeł może być jednego z dwóch typów — czerwony albo czarny. Korzeń jest zawsze czarny. Następniki czerwonego węzła są zawsze czarne oraz ścieżka od każdego liścia do korzenia zawiera tyle samo węzłów czarnych.