I-red-black izihlahla: Uhlolojikelele, izici

Rudolph Bayer uye uhlelo "izihlahla obomvu-black" ngasekuqaleni kwawo-1970. Igama lalesi wanikwa Gimpas L. futhi R. Sedgewick.

Yeka izihlahla obomvu-black

Kufanele kuqashelwe ukuthi awuhlobo zezihlahla self-kulinganisa kanambambili, ukuhlinzeka usayizi ukubalwa ukuphakama inani amayunithi futhi ukukhiqiza izinqubo okuyinhloko kanye eziyisisekelo kwesihlahla yosesho phakathi nesikhathi esifushane. imisebenzi enjalo ihlanganisa nokuzuza, ngaphandle futhi indawo Ukuthola. Ibhalansi inikezwa ngesisekelo umbala isicelo add-Imfanelo notation engeyokuqala. Le mpahla ithatha omunye imiqondo kungenzeka futhi wabonisa enye yalezi imibala.

Isibalo amayunithi amagatsha abamnyama kusukela ekuqaleni (impande) kokugcina (ishidi) ibizwa ngokuthi black isihlahla ukuphakama.

Ukuvela kwegama elithi

Echaza yokusesha isihlahla self-kulinganisa emsebenzini wabo, abalobi cishe akazange acabange ukuthi iyoba abasunguli kwethemu entsha. Nokho, isiphetho abakholelwa ukuthi ukuthi inki okunyathelisa ayenjani etholakalayo imibala emibili kuphela. Bona enzelwe futhi ngamunye kancane kokujoyina i-okwalandela engeyokuqala.

isicelo

Ngo computer science, i-izihlahla obomvu-black asetshenziselwa kumiswa idatha efanayo, okungase kuhlanganise ezihlukahlukene ukukhuthazela yale mibhalo noma izibalo.

Kungenzeka ukwakha isihlahla obomvu-amnyama ActionScript, Python, C ++, futhi cishe kunoma iyiphi enye ulimi lokwakha izinhlelo. Kulula kabi. A obomvu-black emthini Java okungukuthi futhi ngempela kwandile.

Izici

izihlahla ngombala omnyama red kukhona kanambambili search izihlahla endaweni Ukudidiyela uhlelo. Kulezi izinhlelo ngasiphi node has a lombala ethize. Kungathatha omunye abizwa ngenhla. Ngaphezu zonke izimo esetshenziswa esihlahleni kanambambili, futhi zilwane phambi kwethu, ngisho wasebenzisa le mithetho elandelayo:

• Umbala we-node uwukuphela Omunye walabo ababili ngenhla. Ayikho enye kukhetha, kuyabonakala igama elithi.
• Impande yalo muthi kumelwe njalo ngesineke abamnyama. Okuhlukile kungenzeka, kodwa ukuhamba enjalo ekubuseni unezela ingozi ukuthi bayaduka isihlahla self-kulinganisa.
• Zonke amahlamvu abe ukubaluleka oholayo (Nil) futhi ziphawulwe abamnyama.
• Kufanele kuqashelwe ukuthi ezimbili inzalo zonke engeyokuqala red kukhona umzali abamnyama.
• Noma yimuphi indlela ukukhanya okuvela engeyokuqala ikakhulukazi kunoma ishidi ingane node inikeza ncamashi nenani elilinganako amayunithi black kwesakhiwo.

Ngezinye izikhathi imithi obomvu-elimnyama esichazwa njengesono esiphambene banal kanambambili search izihlahla. ukungaboni ngaso linye kwabo kunqunywa kuphela ukuthi esikhundleni izingxenye ezithile umbala, wetinshokutsi eshiwo ngenhla amaKhaladi izimbambo.

Kungani ukhethe izihlahla obomvu-black

izihlahla ngombala omnyama red kukhona okuhlukile okukodwa evamile ngokulingene ngokwakho kanambambili search umuthi, okuyinto avame ujike ngendlela yokuhlakanipha.

Kuchazwa kanjani-ke lokhu udumo lwawo? Prakthiza ukuvilapha, ukuthi siwukuqaphela. Yenza noma yini nzima kakhulu futhi kunzima ukusebenzisa futhi ngesikhathi esifanayo inika yi efanayo ifaniswe nokusetshenziswa izindlela ezingaphezu elula, eshona noma ingena imiphumela yesikhathi eside ezayo uhlelo. Lokhu ukwanda kwalesi abantu izihlahla obomvu-black ngoba ngokuvamile kakhulu ukunikeza ibhalansi elikhulu phakathi izinga kanye nezinga ibhalansi eyinkimbinkimbi futhi silondoloze ke.

Ngokwesibonelo, uma eziqhathanisa ibhalansi aphelele degree of izihlahla zabo, kungase kuphakame isimo uma waphawula ukuthi abameleli "enhle" abeke izimfuno ezingahlangani kakhulu. Futhi ngokuya ukugcwaliseka isenzo nokuqedwa kwesihlahla noma ukusakaza isikhathi nomzamo omkhulu kakhulu ichithwa ekuthuthukiseni isimo esilinganisweni esifanele.

izinqubo

Inqubo yekuhlungwa omnyama abomvu esihlahleni kanambambili cishe yawo wonke amanye amagatsha search kanambambili okufanayo. Kuyiqiniso, njenganoma yikuphi omnyama mahogany umele omunye samuntu ethile zakudala kanambambili search esihlahleni.

Nokho, lapho usebenzelana nabo kufanele kubhekwe kakhulu amathuba okuba ukuthi imisebenzi zokukhiqiza ngokuqondile noma ukubeka datha umonakalo omnyama abomvu isihlahla isakhiwo. Inzuzo enkulu wukuthi kubalulekile ukuba kabusha izakhiwo eziningana elincani nezenzo, ezifana nemibala ezishintsha njalo, futhi badedelane ngokuvamile esingaphansi ezintathu esihlahleni. Cishe zonke lezi imisebenzi ungathathi isikhathi eside.

Ungaqhubeki isenzo Ukufakwa noma ukushintsha liyisici esidingekayo ukwandisa engeyokuqala okwalandela. Lesi sici efanayo yonke kanambambili search esihlahleni. Isinyathelo esilandelayo ukuze iyunithi umbala-esephepheni elibomvu. Umehluko nje kungase kubhekwe ukuthi uma ukusebenza Ukufakwa ngendlela kanambambili search isihlahla into yokuqala esiyikweleta engeza ishidi, esidlule omnyama abomvu ukuthwala ulwazi. Ngakho-ke, esikhundleni ingeze node yangaphakathi ethola ezimnyama ingane ezimbili.

Phambili izenzo zethu ngqo zilawulwe umbala ISIZINDA eduze. igama elithi "Umalume" lisetshenziswa ngabo. Isifaniso ngqo uhlu lozalo. Ngakho-ke:

• Izimpawu ukuthi onke amaqabunga ahlale black, kufanele lisetshenziswe ngaso sonke isikhathi.
• Kulandzelana ukuthi ezimbili nemikhiqizo Node ngalinye elibomvu ukugcina black, angase uphazamiseka. Kodwa lokhu kwenzeka kuphela uma ungeza engeyokuqala obomvu, ngokushintsha umbala omnyama ibe bomvu noma ukushintsha wonke esihlahleni.
• Futhi wazi ukuthi ukulandelana bebandla ukuya ishidi ehlanganisa inani elifanayo ISIZINDA black ephulwa. Lokhu kwenzeka kuphela uma i-black node, ukushintsha izakhi obomvu on black, futhi isimo okuphambene repainting black ibe bomvu. Kungokufanayo kungenziwa nalapho turning esihlahleni.

Ngemva kokubukeza konke okungenhla, kulula ukuqonda ukuthi usesho esihlahleni obomvu-black.

Kuvele incazelo ezithakazelisayo into elula kangaka njengoba nje nesihlahla, kwachazwa nombala - red-black noma emnyama ansundu. Manje wena uyazi kule.