Drzewo czerwono-czarne to rodzaj samobilansującego się drzewa binarnego, które spełnia określone reguły, aby utrzymać swoją strukturę równoważoną. Oto podstawowe warunki, jakie spełniają drzewa czerwono-czarne:
- Każdy węzeł w drzewie jest albo czerwony, albo czarny.
- Korzeń drzewa jest zawsze czarny.
- Każdy liść (zwykle reprezentowany jako węzeł z wartością NULL) jest czarny.
- Jeśli węzeł jest czerwony, to jego dzieci (lewe i prawe) muszą być czarne.
- Dla każdej ścieżki od dowolnego węzła do każdego jego potomka liścia, liczba czarnych węzłów jest taka sama.
Te reguły zapewniają, że droga od korzenia do dowolnego liścia nie będzie znacznie dłuższa od innych dróg, co pozwala na zachowanie efektywności operacji na drzewie, takich jak wyszukiwanie, wstawianie i usuwanie.
Drzewa czerwono-czarne są szeroko stosowane w informatyce, zwłaszcza w implementacjach struktur danych, takich jak mapy i zestawy w językach programowania, ponieważ zapewniają zbalansowane drzewo o gwarantowanej złożoności operacji, nawet w najgorszym przypadku.