Qara-qırmızı ağac

Vikipediya, açıq ensiklopediya
Jump to navigation Jump to search

Qara-qırmızı ağac — özünü balanslaşdıran ikili ağac. Bu ağacın hər bir düyünü özündə əlavə rəng göstərən bit saxlayır. Rəng bitləri ağaca yeni düyün əlavə etdikdə və ya ondan mövcud düyünü 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 düyünlərini rəngləməklə (adətən qırmızı və qara) təmin edilir. Rəngləmə prosessi xüsusi xassələrə malikdir və elə yerinə yetirilir 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 (log n) zamanda axtarışa təminat verir. Burada n ağacın düyünlərinin sayıdır. Bundan başqa yeni düyünün yaradılması, silinməsi və ağacın yenidən rənglənməsi mürəkkəbliyi də O (log n) ilə məhduddur.[2]

Qara-qırmızı ağacların rənglənməsində yalnız iki rəng istifadə edildiyi üçün, düyünlərdə 1 bit əlavə informasiya saxlamaq kafidir. 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ə | əsas redaktə]