Reklama

drzewo czerwono-czarne

(red-black tree)

drzewo poszukiwan binarnych, w którym kazdy wezel zawiera dodatkowy bit informacji, zwany k o l o r e m, który na mocy umowy moze byc albo czerwony (red), albo czarny (black). Nakladajac odpowiednie warunki na mozliwe ciagi kolorów wezlów lezacych na dowolnej sciezce wiodacej od korzenia do liscia d.c.c., gwarantuje sie, ze kazda sciezka jest co najwyzej dwa razy dluzsza niz dowolna inna, czyli osiaga sie przyblizenie B-drzewa. Zob. tez drzewo przedzialów, drzewo statystyk pozycyjnych.

Reklama

Podobne hasła:

Encyklopedia Internautica
Reklama
Reklama
Reklama