Crveno-crno stablo: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
Nema sažetka uređivanja |
{{dijakritici}}, interwiki |
||
Redak 1:
{{dijakritici}}
'''Crveno
Ako cvor nema djece, zovemo ga listovni cvor ili list (engl. leaf node), buduci da se nalazi na samom rubu stabla. Podstablo (engl. subtree) je dio stabla kojem se može pristupiti preko odredenoga cvora te se može smatrati samostalnim stablom. <br>▼
Binarna pretraživacka stabla, ukljucujuci crveno-crna stabla, zadovoljava ogranicenje da svaki cvor sadržava vrijednost manju ili jednaku vrijednosti od vrijednosti desnog podcvora, a vecu ili jednaku od vrijednosti lijevog podcvora. Ovo omogucava brzo pretraživanje stabla za zadanu vrijednost i dopušta ucinkovito obilaženje (traversiranje) elemenata. ▼
▲Ako cvor nema djece, zovemo ga listovni cvor ili list (engl. ''leaf node''), buduci da se nalazi na samom rubu stabla. Podstablo (engl. subtree) je dio stabla kojem se može pristupiti preko odredenoga cvora te se može smatrati samostalnim stablom.
[[slika:Crveno crno stablo primjer.png |thumb|300px|Primjer crveno crnoga stabla|right]]▼
▲Binarna pretraživacka stabla, ukljucujuci crveno-crna stabla, zadovoljava ogranicenje da svaki cvor sadržava vrijednost manju ili jednaku vrijednosti od vrijednosti desnog podcvora, a vecu ili jednaku od vrijednosti lijevog podcvora. Ovo omogucava brzo pretraživanje stabla za zadanu vrijednost i dopušta ucinkovito obilaženje (traversiranje) elemenata.
==
▲[[
Crveno-crna stabla su binarna sortirana stabla s jednim dodatnim bitom prostora po cvoru: bojom koja može biti ili CRVENA ili CRNA. Nijedan put od korijena lista nije više od dva puta dulji od bilo koje drugog puta tako da je drvo otprilike balansirano.
Svaki cvor drva sadrži polja boju, kljuc, lijevo, desno i p. Ako ne postoje dijete ili roditelj cvora, odgovarajuce polja cvora koje sadrži pokazivac sadrži vrijednost NIL. Mi cemo smatrat ove NIL-ove kao pokazivace prema vanjskim cvorovima (listovima) binarnog stabla a normalne cvorove koje sadrže kljuceve kao unutarnje cvorove stabla.
▲Crveno-crna stabla su binarna sortirana stabla s jednim dodatnim bitom prostora po cvoru: bojom koja može biti ili CRVENA ili CRNA. Nijedan put od korijena lista nije više od dva puta dulji od bilo koje drugog puta tako da je drvo otprilike balansirano. <br>
▲Svaki cvor drva sadrži polja boju, kljuc, lijevo, desno i p. Ako ne postoje dijete ili roditelj cvora, odgovarajuce polja cvora koje sadrži pokazivac sadrži vrijednost NIL. Mi cemo smatrat ove NIL-ove kao pokazivace prema vanjskim cvorovima (listovima) binarnog stabla a normalne cvorove koje sadrže kljuceve kao unutarnje cvorove stabla. <br>
Binarno stablo je crveno-crno stablo ako zadovoljava sljedeca crveno-crna svojstva: <br>▼
1. Svaki cvor je ili crven ili crn. <br>▼
2. Korijen je crn. <br>▼
3. Svaki list (NIL) je crn. <br>▼
4. Ako je cvor crven, onda su oba njegova djeteta crna. <br>▼
5. Za svaki cvor, svaki put od njegova cvora do listova koji su mu potomci sadržava isti broj crnih čvorova. <br> ▼
▲
Kao pogodnost pri radu s ogranicenim uvjetima prilikom rada sa crveno-crnim stablima, koristimo jedinstvenu stražarsku oznaku da reprezentiramo NIL. Za crveno-crno stablo T stražarska oznaka nil[T] je objekt sa istim poljima kao obicni cvor u stablu. Njegovo polje boja je CRNA, dok njegova druga polja - p, lijevo, desno i kljuc mogu biti postavljane na proizvoljne vrijednosti. Kao što slika 1(b) pokazuje, svi pokazivaci na NIL su zamijenjeni pokazivacima na oznaku nil[T].
▲''Slika 1: Crveno-crno stabla sa crnim cvorovima i crvenim cvorovima. Svaki cvor u crveno-crnom stablu je ili crven ili crn, a djeca od crvenoga cvora su oba crna te svaki a jednostavni put od cvora do lista potomka sadrži isti broj crnih cvorova. (a) Svaki list, prikazan kao NIL, je crn. Svaki ne-NIL cvor je oznacen svojom crnom-visinom. NIL ima crnu-visinu jednaku 0. (b) Isto crveno-crno stablo, ali sa svakim NIL zamijenjenim istom stražarskom oznakom nil[T] koja je uvijek crna. Takoder su u stablu izostavljene crne-visine cvorova. Korijenov roditelj je takoder stražarska oznaka. (c) Isto crveno crno stablo ali sa izostavljenim listovima i roditeljevim korijenom. Ovaj cemo stil koristiti u ostatku ovog rada.'' <br><br>
▲Kao pogodnost pri radu s ogranicenim uvjetima prilikom rada sa crveno-crnim stablima, koristimo jedinstvenu stražarsku oznaku da reprezentiramo NIL. Za crveno-crno stablo T stražarska oznaka nil[T] je objekt sa istim poljima kao obicni cvor u stablu. Njegovo polje boja je CRNA, dok njegova druga polja - p, lijevo, desno i kljuc mogu biti postavljane na proizvoljne vrijednosti. Kao što slika 1(b) pokazuje, svi pokazivaci na NIL su zamijenjeni pokazivacima na oznaku nil[T]. <br>
Koristimo stražarsku oznaku tako da možemo tretirati NIL dijete cvora x kao standardni cvor ciji je roditelj x. Iako smo umjesto toga mogli dodati razlicitu stražarsku oznaku za svaki NIL u stablu, tako da je roditelj svakoga NIL-a dobro definiran taj pristup bi trošio nepotreban prostor. Umjesto toga koristimo jednu stražarsku oznaku nil[T] da bismo predstavili sve NIL-ove listove i korijenov roditelj. Vrijednosti polja p, lijevo, desno i kljuc stražarske oznake su nevažni, iako ih možemo staviti ako nam cefne.
Opcenito se ogranicavamo na unutrašnje cvorove crveno-crnoga stabla, buduci da oni sadržavaju vrijednosti kljuceva. U ostatku ovog rada izostavljamo listove prilikom crtanja crveno-crnih stabla, kao što je prikazano na slici 1(c).
Broj crnih cvorova na svakom putu od x-a, ali ne ukljucujuci x, do pojedinog lista zovemo crna - visina cvora i oznacavamo sa bh(x). Po svojstvu petom svojstvu crveno-crnih stabala, ideja crne-visine je dobro definirana jer svi silazi putovi od cvora imaju isti broj crnih cvorova. Definiramo crnu-visinu crveno-crnoga stabla kao crnu-visinu njegovog korijena. <br>▼
Teorem koji slijedi pokazuje zašto je crveno-crno stablo dobro stablo za pretragu. <br>▼
▲Broj crnih cvorova na svakom putu od x-a, ali ne ukljucujuci x, do pojedinog lista zovemo crna - visina cvora i oznacavamo sa bh(x). Po svojstvu petom svojstvu crveno-crnih stabala, ideja crne-visine je dobro definirana jer svi silazi putovi od cvora imaju isti broj crnih cvorova. Definiramo crnu-visinu crveno-crnoga stabla kao crnu-visinu njegovog korijena.
'''Teorem 1'''▼
Crveno-crno stablo sa n unutrašnjih cvorova ima visinu od najviše 2log(n+1).<br>▼
<br clear=all>
Dokaz Pocinjemo pokazujuci da podstablo s korijenom u bilo kojem cvoru x sadrži barem 2bh(x) – 1 unutrašnjih cvorova. Dokazujemo ovu tvrdnju matematickom indukcijom za visinu x-a. Ako je vrijednost x-a 0, onda x mora biti list nil[T]) i podstablo s korijenom u x zaista sadrži barem 2bh(x) - 1 = 20 - 1 = 0. unutrašnjih cvorova. Za korak indukcije, smatrajmo da cvor x ima pozitivnu vrijednost te da je unutrašnji cvor sa dva djeteta. Svako dijete ima crnu-visinu od bh(x) ili bh(x) - 1, ovisno o tome je li boja crna ili crvena. Buduci da je visina djeteta od x manja od same vrijednosti x, možemo primjeniti induktivnu hipotezu da zakljucimo da svako dijete ima barem 2bh(x) - 1 unutarnjih cvorova. Stoga podstablo s korijenom u x sadrži barem (2bh(x) - 1 ) + (2bh(x)-1 - 1) + 1 = 2bh(x) – 1 unutrašnjih cvorova što dokazuje tvrdnju. <br>▼
Da se završi dokaz teorema, neka h bude visina stabla. Prema svojstvu 4, barem polovica cvorova bilo kojeg jednostavnoga puta od korijena do kraja, ne ukljucujuci korijen, mora biti crna. Prema tome, crna vrijednost korijena mora biti barem h/2, te stoga vrijedi<br>▼
n = 2h/2 - 1.<br>▼
Pomaknemo li 1 na lijevu stranu i logaritmiramo li izraz dobivamo lg(n + 1) = h/2, ili h = 2 lg(n + 1) ▼
Direktna posljedica ovoga teorema je ta da dinamicki operacije PRETRAŽI, MINIMUM, MAXIMUM, SLJEDBENIK i PRETHODNIK na crveno-crnim stablima mogu biti implementirane u O(log n) vremenu, pošto se ionako mogu obaviti u O(h) vremenu na pretraživackome stablu visine h, a svako crveno-crno stablo s n cvorova je pretraživacko stablo s visinom O(lg n).<br>▼
*Dokaz
▲
▲Da se završi dokaz teorema, neka h bude visina stabla. Prema svojstvu 4, barem polovica cvorova bilo kojeg jednostavnoga puta od korijena do kraja, ne ukljucujuci korijen, mora biti crna. Prema tome, crna vrijednost korijena mora biti barem h/2, te stoga vrijedi
▲Pomaknemo li 1 na lijevu stranu i logaritmiramo li izraz dobivamo lg(n + 1) = h/2, ili h = 2 lg(n + 1)
▲Direktna posljedica ovoga teorema je ta da dinamicki operacije PRETRAŽI, MINIMUM, MAXIMUM, SLJEDBENIK i PRETHODNIK na crveno-crnim stablima mogu biti implementirane u O(log n) vremenu, pošto se ionako mogu obaviti u O(h) vremenu na pretraživackome stablu visine h, a svako crveno-crno stablo s n cvorova je pretraživacko stablo s visinom O(lg n).
(Crveno - crna stabla ne podržavaju direktno dinamicke operacije INSERT i DELETE kako su one definirane na uobicajenim binarnim pretraživackim stablima, buduci da one ne garantiraju da ce modificirano binarno stablo biti crveno crno stablo. Kasnije cemo pokazati da se ove dvije operacije mogu modificirati na nacin da i one mogu biti obavljene u O(log n) vremenu.)
{{Link FA|zh}}
[[de:Rot-Schwarz-Baum]]
Line 43 ⟶ 54:
[[es:Árbol rojo-negro]]
[[fr:Arbre bicolore]]
[[he:
[[it:Albero rosso-nero]]
[[lt:Raudonai-Juodas medis]]
[[ja:
[[ko:
[[pl:Drzewo czerwono-czarne]]
[[ru:Красно-чёрное дерево]]
[[sr:
[[fi:Punamusta puu]]
[[sv:Röd-svart träd]]
[[vi:Cây
[[uk:Червоно-чорне дерево]]
[[zh:
▲[[Kategorija:Teoretsko racunarstvo]]
| |||