Qara-qırmızı ağac
Qara-qırmızı ağac — özünü balanslaşdıran ikili ağac. Bu ağacın hər bir qovşağı özündə əlavə rəng göstərən bit saxlayır. Rəng bitləri ağaca yeni qovşaq əlavə etdikdə və ya ondan mövcud qovşağı sildikdə, ağacın təqribən balanslı qalmasını təmin etmək üçün istifadə edilirlər.[1]
Bu tipli ağaclarda balans 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 ağacın balansının pozulmasını məhdudlaşdırır. Hər dəfə ağacı redaktə edildikdə, rəngləmə prosessi yenidən yerinə yetirilir ki, ağacın əvvəlki balansını təmin edən xassələr qorunsun. Bu xassələri xüsusi qaydada hazırlamaqla redaktə edilmiş ağacda rəngləmə prosessinin sürətli olmasını təmin etmək mümkündür.
Qara-qırmızı ağaclarda balans ideal olmasa da, o zamanda axtarışa təminat verir. Burada n ağacın qovşaqlarının sayıdır. Bundan başqa yeni qovşağın yaradılması, silinməsi və ağacın yenidən rənglənməsi mürəkkəbliyi də ilə məhduddur.[2]
Qara-qırmızı ağacların 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 ağacların yaddaş tələbatı (rənglənməmiş) ikili ağacların yaddaş tələbatı ilə eynidir.
İstinadlar[redaktə | mənbəni redaktə et]
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Red–Black Trees // Introduction to Algorithms (second). MIT Press. 2001. 273–301. ISBN 0-262-03293-7.
- ↑ John Morris. "Red–Black Trees". 2017-04-09 tarixində orijinalından arxivləşdirilib. İstifadə tarixi: 2017-07-09.