ARBORI BICOLORI

l. Dr. Ing. erban RaduDepartamentul de CalculatoareFacultatea de Automatic i Calculatoare

Introducere

Arborii binari de cutare obinuii prezint un dezavantaj major

Performanele lor sunt bune dac datele sunt inserate n ordine aleatoare

Dac ns datele sunt inserate n ordine cresctoare sau descresctoare, aceste performane se degradeaz

Introducere

Atunci cnd valorile inserate sunt deja ordonate (sau aproape ordonate), arborele rezultat este neechilibrat

Arborii neechilibrai i pierd capabilitatea de cutare (sau inserare sau tergere) rapid a unui element

Arbori bicolori

Arborii bicolori sunt arbori binari de cutare cu anumite proprieti n plus

Utilizarea arborilor bicolori reprezint, n majoritatea cazurilor, cea mai eficient soluie de echilibrare, cel puin n cazul n care datele sunt pstrate n memorie

Operaii cu arbori bicolori

Cutarea ntr-un arbore bicolor funcioneaz la fel ca ntr-un arbore binar

Inserarea i tergerea se modific semnificativ

Inserarea de sus n jos

Inserarea n arborii bicolori se numete inserare de sus n jos (top-down)

Arborele va suferi modificri structurale atunci cnd algoritmul l parcurge de sus n jos, pentru a gasi locul n care va insera un nod

Inserarea de jos n sus

O alt posibilitate este inserarea de jos n sus (bottom-up)

Aceasta presupune gsirea locului n care se va insera nodul i efectuarea ulterioar a unor modificri structurale n arbore

Inserarea de jos n sus este mai puin eficient, deoarece presupune dou parcurgeri ale arborelui

Observaii

Un arbore fr ramuri degenereaz ntr-o list nlanuit

Ca i n cazul unei liste nlnuite, trebuie s parcurgem, in medie, jumtate din numrul total de elemente, pentru a gasi un anume element

Observaii

Cutarea printr-un astfel de arbore, cu 10.000 de elemente, va necesita 5.000 de comparaii, n timp ce, pentru un arbore echilibrat, numrul de comparaii este cel mult 14

Pentru date deja sortate, este indiferent dac folosim un arbore binar de cutare sau o list nlnuit

Observaii

Datele parial sortate vor genera arbori parial dezechilibrai

Dei nu au performane att de sczute ca arborii cu grad maxim de dezechilibru, arborii parial dezechilibrai nu reprezint o soluie optim n ceea ce privete cutarea

Echilibrarea arborilor

Fiecare nod din arbore trebuie s aib un numr aproximativ egal de descendeni, att n partea stng, ct i n partea dreapt

ntr-un arbore bicolor, echilibrarea este asigurat prin implementarea operaiei de inserare

Operaia de inserare

La inserarea unui element, funcia care efectueaz operaia verific dac se menin anumite caracteristici ale arborelui

n caz contrar, funcia modific structura arborelui

Prin meninerea acestor caracteristici, se pstreaz starea de echilibrare a arborelui

Caracteristicile arborilor bicolori

1. Nodurile sunt colorate, fiecare nod este fie negru, fie rou

2. Pe parcursul inserrii i tergerii, se asigur pstrarea unor aranjamente prestabilite ale acestor culori

Reguli de colorare

La inserarea (sau la tergerea) unui nod, trebuie respectate anumite reguli, numite reguli de colorare

Respectarea acestor reguli asigur echilibrarea arborelui

Reguli de colorare

1. Fiecare nod este rou sau negru

2. Rdcina are ntotdeauna culoarea neagr

3. Dac un nod este rou, fiii si trebuie s fie negri (reciproca nu este neaprat adevrat)

4. Toate cile de la rdcin spre frunze, sau spre fiii inexisteni, trebuie s conin un numr egal de noduri negre

Observaii

Fiul inexistent din ultima regul este de fapt un loc n care se poate ataa un fiu unui nod care nu este frunz

Acesta este un potenial fiu stng al unui nod cu un fiu drept, sau invers, un potenial fiu drept al unui nod cu un fiu stng

Observaii

Numrul nodurilor negre de pe calea dintre rdcin i o anumit frunz se numete nlime neagr

Ultima regul mai poate fi enunat astfel:

4. Inlimea neagr trebuie s fie constant pentru toate cile de la rdcin spre frunze

Fii inexisteni

Un fiu inexistent este un posibil fiu al unui nod care nu este frunz

Acest fiu nu exist ns n arbore

Observaii

Calea de la rdcin pn la fiul drept al lui 25 (inexistent) are numai un singur nod negru, spre deosebire de cile spre nodurile 6 sau 75, care au dou astfel de noduri

Acest arbore nu respect regula 4, dei ambele ci spre nodurile frunz au acelai numr de noduri negre

Rotaii

Pentru a echilibra un arbore, este necesar s efectum o rearanjare fizic a nodurilor

Dac toate nodurile sunt la stnga rdcinii, trebuie s deplasm unele dintre ele n partea dreapt

Aceast deplasare se efectueaz utiliznd rotaii

Rotaii

Rotaiile reprezint modaliti de rearanjare a nodurilor

Acestea se folosesc pentru a rezolva dou probleme:

1. Ridicarea unora dintre noduri i coborrea altora, pentru a echilibra arborele

2. Asigurarea respectrii ordinii caracteristice arborilor binari de cutare

Observaii

Regulile de colorare i modificrile culorilor se utilizeaz pentru a se putea decide cnd se execut o rotaie

ntr-o rotaie, nodurile nu efectueaz rotaii propriu-zise, ci doar relaiile dintre ele se modific

Observaii

Unul dintre noduri este ales ca vrf

al rotaiei

Dac efectum o rotaie spre dreapta, acest vrf

se va deplasa n jos i spre

dreapta, n poziia fiului su drept

Fiul stng al nodului din vrf se va deplasa n sus, lund locul printelui su

Observaii

Nodul din vrf nu reprezint centrul rotaiei

Orice nod poate fi vrful unei rotaii, dac dispune de fiul necesar

Dac se efectueaz o rotaie spre dreapta, nodul din vrf trebuie s aib un fiu stng

Dac se efectueaz o rotaie spre stnga, nodul din vrf trebuie s aib un fiu drept

Un nod care traverseaz

n urma rotaiei la dreapta, toate nodurile se vor deplasa

Nodul 12 urmeaz deplasarea lui 25 n sus, iar fosta rdcin 50 urmeaz deplasarea lui 75 in jos

Nodul 37 s-a desprins de 25, al carui fiu drept era, devenind fiul stng al lui 50

Observaii

Unele dintre noduri se deplaseaz n sus, altele n jos, dar 37 a traversat arborele

Rotaia a produs o nclcare a regulii 4, care va fi rezolvat mai trziu

n poziia iniial, 37 se numete un nepot interior

al nodului din vrf, 50, iar 12 este

un nepot exterior

Observaii

Nepotul interior, dac este fiul nodului care s-a deplasat n sus (fiul stng al nodului din vrf, n cazul unui rotaii la dreapta), va fi ntotdeauna deconectat de la printele su i reconectat cu fostul su bunic

Subarbori n micare

n urma unei rotaii, anumite noduri i modific poziia

Se pot deplasa ns sub arbori ntregi

Exemplu

ntr-o rotaie la dreapta, avnd ca vrf rdcina 50, se observ c mai multe noduri s-au deplasat simultan

Nodul din vrf (50) i va nlocui fiul drept

Fiul stng (25) al nodului din vrf i nlocuiete fostul printe

ntregul subarbore cu rdcina 12 se deplaseaz n sus

Exemplu

ntregul subarbore cu rdcina 37 traverseaz arborele, devenind fiul stng al lui 50

Subarborele cu rdcina 75 se deplaseaz n jos

Poziiile relative ale nodurilor din acelai subarbore nu sunt afectate de rotaie

ntregul subarbore se deplaseaz solidar

Notaii

Utilizm literele X, P i G pentru a nota o secven de noduri nrudite

X reprezint un nod care a produs o nclcare a regulilor de colorare

Uneori, X se refer la un nod nou inserat, iar alteori la un fiu, n cazul n care att printele, ct i fiul sunt de culoare roie

Notaii

X este un anumit nod

P este printele lui X

G este bunicul lui X (adic printele lui P)

Cnd se parcurge arborele n jos pentru a gsi locul de inserare, se efectueaz o inversare a culorilor, oriunde se ntlnete un printe negru cu doi fii roii (ceea ce ncalc regula 2)

Observaii

Aceast inversare provoac uneori un conflict rou-rou (se ncalc regula 2)

Dac X este fiul rou i P printele rou, conflictul se poare rezolva apelnd la o rotaie simpl sau dubl, dup cum X este nepotul exterior sau interior al lui G

Efectund inversri de culoare i rotaii, se ajunge la punctul de inserare i se insereaz nodul

Observaii

Dup inserarea noului nod X, dac P este negru, pur i simplu i atam un fiu rou

Dac P este rou, avem dou posibiliti, dup cum X este nepotul exterior sau interior al lui G

Se efectueaz dou schimbri de culoare

Observaii

Dac X este nepot exterior, se efectueaz o singur rotaie

Dac X este nepot interior, se efectueaz dou rotaii

n urma acestor operaii, arborele se va reechilibra

Inversri de culoare la parcurgerea descendent a arborelui

Metoda de inserare ntr-un arbore bicolor ncepe prin a efectua ceea ce se face i n cazul unui arbore de cutare parcurgerea drumului de la rdcin pn la locul n care trebuie inserat nodul, deplasdu-se la stnga sau la dreapta, n funcie de comparaia dintre valoarea inserat i cheia nodului curent

Inversri de culoare

ntr-un arbore bicolor, gsirea locului de inserare se complic cu efectuarea unor inversiuni de culoare i a unor rotaii

La fiecare ntnire a unui nod negru cu doi fii roii, culoarea fiilor trebuie s devin neagr, iar a printelui roie (exceptnd cazul n care printele este nodul rdcin, care rmne ntotdeauna negru)

Notaii

Se noteaz nodul din vrful triunghiului, care este negru, nainte de inversiune cu P

Fie X1 i X2 fiul stng, respectiv fiul drept al lui P

Inversiunea nu modific numrul de noduri negre de pe cile de la rdcin spre frunze (sau fii inexisteni) i care trec prin P

Observaii

Toate aceste ci trec prin P i apoi prin X1 i X2

nainte de inversarea culorilor, doar P este negru, deci triunghiul (constnd din nodurile P, X1 i X2) adaug un singur nod negru acestor ci

Observaii

Dup inversarea culorilor, P nu mai este negru, dar ambii si fii sunt, deci triunghiul contribuie tot cu un singur nod negru la fiecare din cile care l parcurg

Prin urmare, inversarea culorilor nu conduce la nclcarea regulii 4

Observaii

Inversarea culorilor este util, deoarece poate transforma frunzele roii n frunze negre

Astfel, va fi mai uor s atam noi noduri roii, fr a nclca regula 3

Observaii

Dei nu ncalc regula 4, inversarea culorilor poate duce la eludarea regulii 3

Dac printele lui P este negru, nu se ntmpl nimic atunci cnd P va deveni rou

Dac ns printele lui P este rou, dup inversarea culorilor vor aprea dou noduri roii adiacente

Noduri roii adiacente

Situaia trebuie rezolvat nainte de a continua parcurgerea arborelui, pentru a determina locul de inserare

Soluia este efectuarea unei rotaii

Dup ce s-a gsit locul potrivit din arbore, efectund (dac este cazul) inversri de culori i rotaii pe parcurs, se poate insera noul nod la fel ca ntr-un arbore de cutare

Rotaii dup inserarea nodului

Inserarea unui nod poate conduce la nclcarea regulilor de colorare

Dup inserare, trebuie s verificm apariia unor abateri de la reguli, pe care (dac exist) s le corectm

Noul nod inserat, X, este ntotdeauna rou

X poate fi poziionat n mai multe moduri, n raport cu P i G

Observaii

X este un nepot exterior, dac este situat fa de printele su P n aceeai parte n care acesta este situat n raport cu printele su G

X este nepot exterior pentru G, dac: X este fiu stng al lui P i P este fiu stng al lui G X este fiu drept al lui P i P este fiu drept al lui G

X este nepot interior al lui G, dac este situat de partea opus a lui P, fa de cum este P situat n raport cu printele su G

Observaii

Dac X este un nepot exterior, poate fi fiul stng sau drept al lui P, dup cum P este la rndul su fiu stng sau drept al lui G

Exist dou situaii similare n care X este nepot interior al lui G

3 moduri de dispunere a nodurilor

Situaiile posibile dup inserare:

1. P este negru

2. P este rou i X este un nepot exterior al lui G

3. P este rou i X este un nepot interior al lui G

Cazul 1 P este negru

Nodul nou inserat este ntotdeauna rou

Dac printele este negru, nu apare un conflict de culoare (regula 3) i nicio cretere unilateral a numrului de noduri negre (regula 4)

Regulile de colorare sunt respectate

Inserarea este efectuat cu succes

Cazul 2 P este rou i X este exterior

Sunt suficiente o rotaie i cteva modificri ale culorilor

Se poate reface corectitudinea de colorare (echilibrul arborelui) n 3 pai

3 pai

1. Se modific culoarea bunicului G (25) al lui X (6)

2. Se modific culoarea printelui P (12) al lui X (6)

3. Se efectueaz o rotaie cu nodul G (25) n vrf, n direcia care asigur ridicarea lui X (6) n arbore

n exemplu, rotaia se va efectua spre dreapta

Cazul 3 P este rou i X este interior

Avem nevoie de dou rotaii i o modificare

a culorii

unui

nod

Pai pentru echilibrarea arborelui

1. Se efectueaz o rotaie cu printele P (12) situat n vrf, n direcia care asigur ridicarea lui X (spre stnga, n acest caz)

2. Se efectueaz nc o rotaie, cu bunicul G (25) situat n vrf, in direcia care asigur ridicarea lui X (18) (spre dreapta)

3. Se modific culoarea lui P (12)

care este rou i devine negru

Observaii

Secvena de operaii aduce arborele ntr-o configuraie n care respect regulile de colorare i l reechilibreaz

Exist un caz simetric n care P este fiul drept al lui G

Observaii

Utilizarea inversrii culorilor, la parcurgerea descendent, elimin situaiile n care o rotaie poate propaga nclcri ale regulilor de colorare mai sus n arbore

Operaia asigur c una sau dou rotaii sunt suficiente pentru a restabili corectitudinea ntregului arbore

Observaii

Datorit inversrii culorilor, inserrile n arborii bicolori sunt mult mai eficiente dect n alte tipuri de arbori echilibrai, cum sunt arborii AVL

Inversrile asigur suficiena unei singure parcurgeri descendente a arborelui

Rotaii la parcurgerea descendent

Inversarea culorilor poate produce o nclcare a regulii 3 (un nod fiu i printele su nu pot fi amndoi de culoare roie)

Aceast problem se poate rezolva prin efectuarea unei rotaii

Exist dou posibiliti

nodul implicat poate fi un nepot exterior sau interior

Nepot exterior

Nod implicat fiul din perechea printe fiu, care a provocat conflictul de colorare

Metoda utilizat pentru a rezolva aceast situaie este similar cu operaia efectuat dup inserarea unui nepot exterior

Trebuie s efectum dou modificri de culori i o rotaie

Observaii

Printele lui X (12) este nodul P (25), iar bunicul lui X este G (50)

1. Se modific culoarea bunicului G

2. Se modific culoarea printelui P

3. Se rotete arborele, cu bunicul lui X n vrf, n direcia care asigur ridicarea lui X (spre dreapta)

Observaii

Nodul cu valoarea 3 poate fi inserat acum n mod obinuit

Din cauz c printele su, 6, este negru, inserarea se efectueaz imediat

Nepot interior

Dac nodul X, care produce un conflict de culoare la parcurgerea descendent a arborelui, este un nepot interior, vor fi necesare dou rotaii pentru restabilirea regulilor n arbore

Situaia este asemntoare cu operaia efectuat dup inserarea unui nepot interior

Rezolvarea conflictului de culoare

1. Se modific culoarea lui G (50)

2. Se modific culoarea lui X (37)

3. Se rotete subarborele cu P (25) n vrf, n direcia care asigur ridicarea lui X n arbore (spre stnga)

4. Se rotete arborele cu G n vrf, n direcia care asigur ridicarea lui X (spre dreapta)

Observaii

Acum se poate insera nodul 28

Culorile nodurilor 25 i 50 se vor inversa, cele dou noduri devenind negre

Eficiena arborilor bicolori

Ca i arborii binari de cutare, arborii bicolori permit efectuarea operaiilor de cutare, inserare i tergere, ntr-un timp de O(log2

N)

Pentru fiecare nod, este necesar mai mult memorie, pentru a memora i culoarea

Eficiena arborilor bicolori

Timpii necesari pentru inserare i tergere cresc cu o valoare constant, necesar efecturii inversrii culorilor i rotaiilor la parcurgere i la locul inserrii (tergerii)

n medie, inserarea presupune efectuarea unei rotaii

Inserarea se efectueaz ntr-un timp de O(log2

N), dar este puin mai lent dect pentru un arbore binar de cutare

Implementarea inserrii

Se adaug un cmp care s descrie culoarea

Pe calea descendent ctre locul de inserare, se verific dac nodul curent este negru, iar cei doi fii ai si sunt amndoi roii

Dac este astfel, se modific culorile celor trei noduri (cu excepia cazului n care printele este chiar rdcina, care trebuie meninut neagr)

Implementarea inserrii

Dup o inversare a culorilor, se verific dac nu se ncalc regula 3

n acest caz, se execut rotaiile corespunztoare: una pentru un nepot exterior, dou pentru un nepot interior

Cnd se ajunge la un nod frunz, se insereaz nodul nou, cu meniunea c acesta trebuie s fie rou

Implementarea inserrii

Se verific nc o dat prezena conflictelor de culoare, executnd rotaiile necesare

Dac se execut corect inversrile de culori i rotaiile, nlimile negre ale nodurilor se vor conserva, iar arborele va rmne echilibrat

Arbori AVL

Arborii AVL

(Adelson-Velskii i Landis) reprezint primul tip de arbori echilibrai, descoperii n 1962

ntr-un arbore AVL, fiecare nod memoreaz o alt informaie suplimentar: diferena dintre nlimea subarborelui su stng i cea a subarborelui drept

Diferena nu trebuie s depeasc 1

Arbori AVL

Dup inserare, se verific rdcina subarborelui aflat cel mai jos i n care s-a inserat noul nod

Dac diferena dintre nlimile celor doi fii este mai mare dect 1, se execut o rotaie simpl sau dubl, pentru a egaliza cele dou nlimi

Arbori AVL

Algoritmul se deplaseaz apoi cu un nivel mai sus n arbore, egaliznd din nou nlimile subarborilor, dac este cazul

Acest proces continu pn la atingerea rdcinii arborelui

Arbori AVL

Timpul de cutare este de ordinul O(log2

N), deoarece echilibrarea arborelui este garantat

Pentru inserare sau tergere, este necesar efectuarea a dou parcurgeri: una descendent, pentru determinarea locului de inserare, i una ascendent, pentru reechilibrare

De aceea, arborii AVL sunt mai puin eficieni dect arborii bicolori

Arbori multici

Un arbore multici este un arbore echilibrat, n care fiecare nod poate avea mai mult de doi fii

Un dezavantaj al acestor arbori este c fiecare nod ocup mai mult memorie dect la arborii binari, deoarece trebuie s memoreze cte un pointer ctre fiecare din fiii si

Concluzii

Meninerea echilibrrii unui arbore binar asigur efectuarea operaiei de cutare a unui nod din arbore ntr-un timp minim

Inserarea unor date deja sortate va genera un arbore cu un grad de dezechilibru maxim, n care cutarea se va efectua ntr-un timp O(N)

Concluzii

Modurile permise, n care pot fi dispuse nodurile dintr-un arbore bicolor, sunt specificate prin reguli de colorare

Aceste reguli se aplic pentru operaiile de inserare i tergere a unui nod

O inversare de culori schimb un nod negru cu doi fii roii, ntr-un nod rou, cu doi fii negri

Concluzii

ntr-o rotaie, un nod este desemnat ca nod din vrf

O rotaie spre dreapta deplaseaz nodul din vrf n locul fiului su drept, iar fiul stng al nodului din vrf, n locul printelui su

O rotaie spre stnga deplaseaz nodul din vrf n locul fiului su stng, iar fiul drept al nodului din vrf, n locul printelui su

Concluzii

Inversrile de culori i, n unele cazuri, rotaiile, se utilizeaz la parcurgerea descendent a arborelui, pentru cutarea locului de inserare

Aceste inversri simplific restabilirea corectitudinii la colorare a arborelui, dup efectuarea inserrii

Concluzii

Dup inserarea unui nod, se verific din nou conflictele de culoare

Dac se detecteaz o nclcare, se execut rotaiile corespunztoare pentru asigurarea corectitudinii arborelui

n urma acestor operaii, arborele devine echilibrat, sau cel puin aproape echilibrat

Concluzii

Adugarea informaiei necesare echilibrrii ntr-un arbore are un impact negativ minor asupra performanelor medii, evitnd n schimb degradarea acestora, n cazul defavorabil n care datele sunt iniial sortate

ARBORI BICOLORIIntroducere IntroducereArbori bicoloriOperaii cu arbori bicoloriInserarea de sus n josInserarea de jos n sus ObservaiiObservaiiObservaiiEchilibrarea arborilorOperaia de inserare Caracteristicile arborilor bicoloriReguli de colorareReguli de colorareObservaiiObservaiiFii inexisteniSlide Number 19ObservaiiRotaiiRotaiiObservaiiObservaiiObservaiiSlide Number 26Un nod care traverseazObservaiiObservaiiSubarbori n micareSlide Number 31Slide Number 32ExempluExempluNotaiiNotaiiObservaiiObservaiiObservaiiInversri de culoare la parcurgerea descendent a arboreluiInversri de culoareSlide Number 42NotaiiObservaiiObservaiiObservaiiObservaiiNoduri roii adiacenteRotaii dup inserarea noduluiSlide Number 50Slide Number 51ObservaiiObservaii3 moduri de dispunere a nodurilorSlide Number 55Slide Number 56Cazul 1 P este negruCazul 2 P este rou i X este exterior Slide Number 593 paiCazul 3 P este rou i X este interiorSlide Number 62Slide Number 63Slide Number 64Pai pentru echilibrarea arboreluiObservaiiObservaiiObservaiiRotaii la parcurgerea descendent Nepot exteriorSlide Number 71Slide Number 72ObservaiiObservaiiNepot interiorSlide Number 76Slide Number 77Slide Number 78Rezolvarea conflictului de culoareObservaiiEficiena arborilor bicoloriEficiena arborilor bicoloriImplementarea inserriiImplementarea inserriiImplementarea inserriiArbori AVLArbori AVLArbori AVLArbori AVLArbori multiciConcluziiConcluziiConcluziiConcluziiConcluziiConcluzii