Crvena i crna stabla: opis, značajke

Rudolf Bayer razvio je sustav "crveno-crnih stabala" još početkom 1970-ih. Ime mu je dano L. Gimpas i R. Sedgwick.

Što crveno-crno stablo

Treba napomenuti da su one vrste samonalizirajućih binarnih stabala, pružajući brojčanu veličinu visine od broja čvorova i stvarajući primarne i osnovne procese pretraživanja u kratkom vremenu. Takve operacije uključuju vezivanje, isključivanje i traženje čvora. Ravnoteža je osigurana na osnovu popunjavanja atributa oznake aplikacije čvora, boje. Ova imovina preuzima jedan od mogućih pojmova i označava jednu od navedenih boja.

Broj crnih jedinica na grani od početka (korijena) do konačnog (list) naziva se crna visina stabla.

Pojava pojma

Opisujući samooblikovano stablo za pretraživanje u svom radu, autori članka vjerojatno nisu ni očekivali da postanu osnivači novog pojma. Ipak, sudbina je naručila da tiskara ima samo dvije boje. Također označavaju svaki bit koji se pridružuje sljedećem čvoru.

primjena

U računalnoj znanosti crvena crna stabla koriste se za generiranje usporedivih podataka, što može uključivati ​​različite izvode i dijelove natpisa ili likova.

Možete stvoriti crveno-crno stablo na Actionscript, Python, C + + i gotovo svaki drugi programski jezik. Vrlo je jednostavno. Crveno-crno stablo Java je također prilično raširena.

Značajke

Crvena i crvena stabla su stabla za pretraživanje u binarnom koordinatnom sustavu. U tim sustavima svaki čvor ima određenu vrijednost boje. Može potrajati na jednom od gore navedenih napomena. Pored svih primijenjenih uvjeta binarnih stabala i sorti koje se razmatraju, ova se pravila također koriste:

• Boja čvora isključivo je jedna od gore navedenih. Nema drugih opcija, ona se također odražava u nazivu pojma.
• Korijen stabla uvijek treba biti obojan crnom. Iznimke su moguće, ali takvo odstupanje od pravila povećava rizik da će stablo biti samostalno.
• Svi listovi imaju null vrijednost (NIL) i označeni su crnom bojom.
• Važno je osigurati da su dva potomka svakog crvenog roditeljskog čvora crna.
• Svaki jednostavan put od određenog čvora do bilo kojeg lisnatog čvora za dijete pruža točno isti broj crnih strukturnih jedinica.

Ponekad se crveno-crno drvo tumači kao banalna stabla za binarnu pretragu. Njihove razlike određuju samo činjenica da umjesto određenih čvorova u boji, rebra su obojene u gornjim vrijednostima.

Zašto odabrati točno crveno-crne stabla

Crvena i crvena stabla su jedna od najčešćih varijanti samonavjetujućih stabala za binarnu pretragu, koja se najčešće rješavaju praktično.

Što objašnjava njihovu popularnost? Praksa je lijen, a vrijedno je priznati. Sve što je previše glomazno i ​​teško za korištenje, a istodobno proizvodi usporedive rezultate slično jednostavnijim metodama, umre ili odlazi u daleku budućnost. Takva prevalencija kod ljudi crvenog crnog stabla objašnjava činjenicom da najčešće osiguravaju optimalnu ravnotežu između kvalitete i ravnoteže i lukavosti njenog održavanja.

Na primjer, ako ih usporedimo s onima koji su savršeni u stupnju njihove ravnoteže stablima, onda se može pojaviti situacija u kojoj se primjećuje da "idealni" predstavnici nameću previše beskompromisne zahtjeve. A u pogledu realizacije eliminacije djelovanja stabla ili širiti previše vremena i truda troši na stabilizaciji stanja u pravo stanje.

procesi

Proces dokazivanja crno-crvenih binarnih stabala gotovo je isti za sve ostale binarne grane pretraživanja. To je istina, budući da je bilo crno-crveno stablo jedna od posebnih varijanti klasičnog binarnog stabla pretraživanja.

Međutim, prilikom rada s njima treba uzeti u obzir da je vjerojatnije da izravna proizvodnja djelovanja uključivanja ili isključivanja podataka može prouzročiti štetu strukturi crnih i crvenih stabala. Ogromna je prednost da za rekonstrukciju svojstava, relativno mali broj radnji, kao što su promjena boje i često manje od tri rotacije stabla, su neophodni. Zapravo, sve te operacije ne trebaju mnogo vremena.

Da biste nastavili s radnjom umetanja ili uključivanja nekog elementa, potrebno je povećati sljedeći čvor. Ova funkcija je slična svim binarnim stablima pretraživanja. Sljedeći korak je obojiti čvor u crveno. Jedina je razlika ako dodate li prvi list kada umetnete u binarnu stablu pretraživanja, tada crno i crveno ne prenose nikakve informacije. Stoga, umjesto njih dodaje se unutarnji čvor koji uzima crvenu boju i dva crna potomstva.

Dalje naše postupke izravno uvjetuju boja susjednih čvorova. Za njih se koristi izraz "stric". Izravna analogija s genealoškim stablom. dakle:

• Obilježja da sva lišća zadržavaju crnu boju moraju uvijek biti realizirana.
• Slijed činjenice da dva derivata svakog crvenog čvora zadržavaju crnu boju mogu se prekinuti. No, to se događa samo kad dodate crveni čvor, kada promijenite boju crne na crvenu ili kada okrenete cijelo stablo.
• Također imajte na umu da se može kršiti slijed s čvora na list, uključujući isti broj crnih čvorova. To se događa samo kada je crni čvor uključen, crveni element mijenja u crnu, a također iu suprotnoj situaciji preinake crne do crvene. To se također može učiniti prilikom okretanja stabla.

Proučavajući sve gore navedeno, nije teško razumjeti kako se pretraživanje izvodi u crveno-crnom stablu.

Interpretacija takvog jednostavnog koncepta kao stabla je zanimljiva, s opisom njegove boje - crveno-crno ili crno-smeđe. Sada ste i vi svjesni toga.