Drzewo czerwono-czarne jest rozszerzeniem podstawowej struktury o algorytm równoważenia wykonywany po każdej operacji INSERT oraz DELETE. W przypadku tej struktury elementy-liście nie przechowują żadnych informacji, dlatego często w ich miejsce wprowadza się dla zaoszczędzenia pamięci i uproszczenia kodu pojedynczego wartownika.
Właściwości thumb|500px|Przykład drzewa czerwono-czarnego|right
W drzewie czerwono-czarnym z każdym węzłem powiązany jest dodatkowy atrybut „kolor”, który może być czerwony lub czarny. Oprócz podstawowych własności drzew poszukiwań binarnych, wprowadzone zostały kolejne wymagania, które trzeba spełniać: Każdy węzeł jest czerwony albo czarny. Korzeń jest czarny. Każdy liść jest czarny (Można traktować nil jako liść). Jeśli węzeł jest czerwony, to jego synowie muszą być czarni. Każda ścieżka z ustalonego węzła do każdego z jego potomków będących liśćmi liczy tyle samo czarnych węzłów.