Rudolf Bayer je razvil sistem "rdeče-črnih dreves" v zgodnjih sedemdesetih letih. Ime je dobil L. Gimpas in R. Sedgwick.

Kaj pa rdeče-črna drevesa

Omeniti je treba, da so to ena od vrst samonalansirnih binarnih dreves, ki zagotavljajo prešteto višino števila vozlišč in proizvajajo primarne in osnovne procese drevesa iskanja v kratkem času. Te operacije vključujejo združevanje, izključevanje in sledenje strani. Ravnotežje je zagotovljeno na podlagi dopolnila atributa uporabe barvne kode mesta. Ta lastnost prevzame enega od verjetnih konceptov in je označena z eno od omenjenih barv.


Število črnih enot na vejah od začetka (korena) do finala (črka) se imenuje črna višina drevesa.

Pojav izraza

Avtorji članka, ki opisujejo samo-uravnotežujoče drevo iskanja v svojem delu, verjetno niso niti domnevali, da bodo postali ustanovitelji novega izraza. Vendar je bila usoda naročena tako, da je bila tiskarna v prisotnosti barve le dveh barv. Označili so tudi vsak bit, ki se pridruži naslednjem vozlišču.

Uporaba

V informatiki se rdeče-črna drevesa uporabljajo za oblikovanje primerljivih podatkov, ki lahko vključujejo različne izpostavljenosti in dele napisov ali številk. Ustvarite lahko rdeče-belo drevo na Actionscript, Python, C ++ in praktično vsakem drugem programskem jeziku. To je zelo preprosto. Rdeče-črno drevo Java je prav tako leporazširjena

Značilnosti

Črno-rdeča drevesa so iskalna drevesa v binarnem koordinatnem sistemu. V teh sistemih ima vsako mesto določeno barvno vrednost. Lahko prevzame enega od zgoraj navedenih simbolov. Poleg vseh pogojev, ki veljajo za binarna veličastna drevesa, za vrste, ki jih obravnavamo, se uporabljajo tudi naslednja pravila:

Barva območja je izključno ena od obeh zgoraj navedenih. Ni drugih možnosti, to se odraža tudi v imenu izraza.

Koren drevesa mora biti vedno črne barve. Izjeme so možne, vendar to odstopanje od pravila dodaja tveganje, da se bo samoizravnavanje dreves uničilo.

Vsi listi imajo ničelno vrednost (NIL) in so označeni s črno barvo.

Treba je zagotoviti, da sta dva potomca vsakega rdečega nadrejenega vozlišča črna.

Vsak svetlobni tok od določenega vozlišča do katerega koli podrejenega vozlišča listov zagotavlja natančno enako število črnih strukturnih enot.

Včasih se rdeča in črna drevesa razlagajo kot trivialna binarna iskalna drevesa. Njihove razlike so odvisne samo od dejstva, da so v zameno za nekatera barvna vozlišča zgoraj navedene vrednosti filcana rebra.

Zakaj izbrati rdeče črna drevesa

Črno-rdeča drevesa predstavljajo eno izmed najpogosteje uporabljenih variant samoregulativnih binarnih dreves iskanja, ki se najpogosteje nanašajo na praktično uporabo. Zakaj je ta priljubljenost jasna? Praksa je lena in je vredna priznanja. Vse je preveč okornoin težko uporabljati, hkrati pa daje primerljivo podobne rezultate pri uporabi enostavnejših metod, umre ali odide v oddaljeni načrt. Ta prevalenca rdeče-črnih dreves pri ljudeh je posledica dejstva, da najpogosteje zagotavljajo optimalno ravnovesje med kakovostjo in ravnjo ravnovesja in zakovristosti njegove podpore.
Na primer, če jih primerjamo z popolnoma uravnoteženimi drevesi, potem lahko pride do situacije, ko opazimo, da »idealni« predstavniki nalagajo preveč nezdružljive zahteve. In v smislu izvajanja akcije izključevanja iz drevesa ali obračanja preveč časa in truda se porabi za stabilizacijo ravnotežja v danih razmerah.

Procesi

Postopek preverjanja črno-rdečih binarnih dreves je skoraj enak za vse druge binarne preiskave razvejanosti. Tako je, ker je vsako črno-belo drevo ena od zasebnih možnosti klasičnega binarnega drevesa iskanja. Vendar pa je treba pri sodelovanju z njimi upoštevati večjo verjetnost, da lahko neposredna produkcija vključitve ali izključitve podatkov poškoduje strukturo črnih in rdečih dreves. Velika prednost je, da je za rekonstrukcijo lastnosti, kot so spreminjanje barv in manj kot trije obrati drevesa, potrebno relativno majhno število dejanj. Pravzaprav, vse te operacije ne trajajo veliko časa. Začetek vstavljanja ali vstavljanje elementa je vredno dodati naslednjemu vozlišču. Ta funkcija je enaka za vsa binarna drevesa iskanja.Naslednji korak je barvanje vozlišča v rdeči barvi. Edina razlika je, da če vstavljanje binarnega drevesa iskanja najprej doda črko, potem v črni in rdeči zadnji ni nobene informacije. Zato se namesto njih doda notranje vozlišče, ki prejme rdečo barvo in dva njena črna potomca. Naša nadaljnja dejanja so neposredno pogojena z barvo sosednjih vozlišč. Za njih se uporablja izraz "stric". Neposredna analogija s rodoslovnim drevesom. Posledično:

Značilnost dejstva, da so vsi listi črne barve, mora biti vedno izvedena.

Zaporedje dejstva, da dva derivata vsakega rdečega vozlišča ostajata črna, se lahko prekine. Toda to se zgodi le pri dodajanju rdečega mesta, pri spreminjanju barve črne na rdeče ali pri širjenju celotnega drevesa.

Ugotavljamo tudi, da lahko to vpliva na zaporedje od vozlišča do črke, ki vključuje enako število črnih vozlišč. To se zgodi le pri obračanju črnega vozlišča, pri čemer se rdeči element spremeni v črno, v nasprotnem primeru pa se črno in rdeče prebarva. Enako velja za obračanje dreves.

Po preučevanju vsega zgoraj navedenega je enostavno ugotoviti, kako iskati v rdečem in črnem drevesu. Zanimiva interpretacija tako enostavnega pojma, kot je drevo, z opisom njegove barve - rdeče-črne ali črno-rjave. Zdaj se tega zavedate.