Qara-qırmızı ağac — özünü ikili . Bu hər bir qovşağı özündə əlavə rəng göstərən bit saxlayır. Rəng bitləri yeni qovşaq əlavə etdikdə və ya ondan mövcud qovşağı sildikdə, təqribən qalmasını təmin etmək üçün istifadə edilirlər.
Bu tipli onların qovşaqlarını rəngləməklə (adətən, şərti olaraq qırmızı və qara) təmin edilir. Rəngləmə qaydası elə seçilir ki, bütövlükdə rənglər verilən pozulmasını məhdudlaşdırır. Hər dəfə redaktə edildikdə, rəngləmə prosessi yenidən yerinə yetirilir ki, əvvəlki təmin edən xassələr qorunsun. Bu xassələri xüsusi qaydada hazırlamaqla redaktə edilmiş rəngləmə prosessinin sürətli olmasını təmin etmək mümkündür.
Qara-qırmızı ideal olmasa da, o zamanda axtarışa təminat verir. Burada n qovşaqlarının sayıdır. Bundan başqa yeni qovşağın yaradılması, silinməsi və yenidən rənglənməsi mürəkkəbliyi də ilə məhduddur.
Qara-qırmızı rənglənməsində yalnız iki rəng istifadə edildiyi üçün, qovşaqlarda 1 bit əlavə informasiya saxlamaq kifayətdir. Buna görə də bu tipli yaddaş tələbatı (rənglənməmiş) ikili ağacların yaddaş tələbatı ilə eynidir.
İstinadlar
- ; ; ; . Red–Black Trees // (second). MIT Press. 2001. –301. ISBN 0-262-03293-7.
- John Morris. . 2017-04-09 tarixində arxivləşdirilib. İstifadə tarixi: 2017-07-09.