STRUCTURI DE DATE - ASE · Reechilibrare arbore AVL prin stergerea unei chei 16 si inserarea cheii...

STRUCTURI DE DATE

Arbori echilibrati

http://www.acs.ase.ro

http://www.itcsolutions.eu

ARBORI BINARI ECHILIBRATI Abordari ale operatiei de echilibrare:

1. Echilibrare perfecta:

• Diferenta dintre nr. noduri SS si SD este 0, pentru fiecare

nod din arbore;

• Toate nodurile frunza sunt pe acelasi nivel;

• Orice nod de pe nivelurile intermediare are doi

descendenti (h – inaltime arbore);

2

23

10 27

18 3 25 29



Implementare operatie:

• Metoda divide et impera;

• Parcurgere sir de chei ordonate crescator si

inserarea valorii din mijloc in arbore;

• Volum mare de calcule: operatii de inserare

si stergere, parcurgere inordine arbore,

reconstructie structura arborescenta.

3

ARBORI BINARI ECHILIBRATI


http://www.itcsolutions.eu 4

ARBORI BINARI ECHILIBRATI void echlibrareArbore(int *chei, int dim, int stanga, int dreapta, NodArbore

*&radacina){

if (dreapta>=stanga){

int mijloc=(dreapta+stanga)/2;

if (dreapta-stanga==1){

radacina =inserareArbore(radacina, chei[stanga]);

radacina = inserareArbore (radacina, chei[dreapta]);

}

else{

if (dreapta==stanga)

radacina = inserareArbore (radacina, chei[stanga]);

else{

radacina = inserareArbore (radacina, chei[mijloc]);

echlibrareArbore (chei,dim,stanga, mijloc-1, radacina);

echlibrareArbore (chei,dim, mijloc+1,dreapta, radacina);

}

}

}

• chei – vector: şirul sortat crescător al valorilor;

• dim – dimensiunea vectorului;

• stanga, dreapta – limitele intervalului curent;

• rădăcina arborelui ce va fi creat.



Mentenanta unei astfel de structuri:

• Grad de complexitate foarte ridicat;

• Recrearea arborelui perfect echilibrat după

fiecare operaţie de inserare sau ştergere cu

metoda echilibrareArb;

5




Abordari ale operatiei de echilibrare

(continuare):

2. Echilibrare imperfecta:

• Diferenta dintre nr. noduri SS si SD este

maxim 1, pentru fiecare nod din arbore;

• Crearea structurii: utilizarea metodei

prezentate anterior, pornind de la un set de

valori sortate crescător sau descrescător;

6




Mentenanta unei astfel de structuri:

• Grad de complexitate acceptabil;

• Metode specifice unor structuri

arborescente echilibrate particulare: AVL,

arbori B, arbori Rosu & Negru;

• Efort de prelucrare mai mic decât volumul

operaţiilor asociat reconstrucţiei arborelui

prin metoda echilibrareArb.

7




Minimizarea efortului de cautare:

• Aranjare echilibrata a valorilor pe ambii

subarbori ai fiecărui nod.

8

23

10

27 18

3

2

23

10 27

18 3

2

23 – 10 – 3 – 2, 4 comparatii 10 – 3 – 2, 3 comparatii




Caracteristici:

• Definit de G.M. Adelson-Velskii şi E.M.

Landis;

• Arbore binar de căutare echilibrat pe

înălţime;

• Arbore binar de căutare este AVL: gradul de

echilibru al fiecărui nod ia valori în mulţimea

{-1,0,1}.

9

ARBORI AVL



Gradul de echilibru al unui nod (GE):

GE = H(SD) – H(SS)

H() – funcţia de calcul a înălţimii unei structuri

arborescente; H(rad) = 1 + max (H(subarbore drept), H(subarbore stâng))

10

ARBORI AVL



• Pentru GE = 0, nodul este echilibrat,

• Pentru GE=1 si GE=-1, nodul descrie un

dezechilibru la dreapta, respectiv la stânga;

situatii acceptate: pentru un număr par de valori

este imposibil sa se definească un arbore binar de

căutare în care toate nodurile sunt perfect

echilibrate.

11

23

10

27 18

3

2

GE = 0

GE = -1 GE = 0

GE = 0 GE = 0 GE = 0

ARBORI AVL



Mentenanta structura arbore AVL:

• Verificarea gradului de echilibru, pentru fiecare

nod în parte;

• Inserare/ştergere afectează structura arborelui şi

conduc la situaţii de dezechilibru;

• Situaţiile de dezechilibru puternic: identificate prin

indicatorul GE care ia valori în mulţimea

{-2,2}.

12

ARBORI AVL



Reechilibrarea arborelui binar de căutare şi

păstrarea caracteristicilor aferente arborilor

AVL:

• rotire simpla la stânga;

• rotire simpla la dreapta;

• dubla rotire la stânga;

• dubla rotire la dreapta.

13

ARBORI AVL



Operatia de echilibrare:

• Inserare: un arbore AVL dezechilibrat va fi

reechilibrat printr-o singură rotaţie;

• Stergere: mult mai complexă, necesitând

minim o rotaţie.

Metoda adecvata de reechilibrare: analiza

gradului de echilibru a nodurilor aflate pe

drumul de la rădăcina arborelui la locaţia

unde a fost inserat/şters un nod.

14

ARBORI AVL



Arbore binar AVL dezechilibrat dupa inserare nod cu

valoare cheie = 1

15

23

10

27 18

3

2

GE = -1

GE = -2 GE = 0

GE = -1 GE = 0 GE = 0

1

GE =0

ARBORI AVL



Aplicare metoda de reechilibrare:

• Se identifica un nod (pivot) în care se

realizează rotirea subarborelui – abordare

bottom-up pornind de la locatia nodului

inserat/sters;

• Reechilibrarea: cat mai aproape de locatia

care a generat dezechilibrul;

• Identificare operatie de rotatie: gradul de

echilibru al nodului pivot si fiu al pivotului

pe directia dezechilibrului.

16

ARBORI AVL



Nodul pivot (cheia 3), are GE = -2: dezechilibru la stânga.

Nodul fiu stânga (cheia 2), are dezechilibru la stânga.

Reechilibrarea se realizează prin operaţia de rotire simplă la

dreapta.

17

X

3

2

Z

?

Y

X

3

2

Z

X - Subarbore drept

pivot

GE = -2

GE = -1

?

Y

Y - Subarbore stang

fiu dreapta pivot

NOD PIVOT

GE = 0

GE = 0

NOD FIU PE

DIRECTIA

DEZECHILIBRULUI

ARBORI AVL



3

2

?

3

2

GE = H1 – (H1 + 2) = -2

GE = H1 – (H1 + 1) = -1

?

NOD PIVOT

GE = 0

GE = 0

H1

H1+1

Z Y

H1

X

H1+1

Z

H1+2

H1

Y

H1

X

H1+1

ARBORI AVL

Procesul de rotire simplă la dreapta



23

10

27 18

2

3

GE = 0

GE = 0 GE = 0

GE = 0

GE = 0 GE = 0

1

GE =0

ARBORI AVL

Arbore AVL reechilibrat



23

10

27

2

30

GE = 1

GE = -1 GE = 2

GE = 0

GE = 1 GE =0

1

Nodul pivot (cheia 23), are GE = 2: dezechilibru la dreapta.

Nodul fiu stânga (cheia 27), are dezechilibru la dreapta.

Reechilibrarea se realizează prin operaţia de rotire simplă la

stanga.

ARBORI AVL



X - Subarbore stâng

pivot 27

23

X

Y

GE = 2

GE = 1

?

Z

Y - Subarbore stang

fiu stânga pivot

NOD PIVOT

Z

27

23

Y

?

X

GE = 0

GE = 0

NOD FIU PE

DIRECTIA

DEZECHILIBRULUI

Procesul de rotire simplă la stânga

ARBORI AVL



27

10

30

2

23

GE = 1

GE = -1 GE = 0

GE = 0 GE = 0 GE =0

1

Arbore AVL reechilibrat

ARBORI AVL



Se inserează în arborele AVL anterior

elementele cu valorile 16, 24, 26. Structura

arborescentă obţinută este:

23

27

10

30

2

23

GE = 2

GE = -1

GE = -2

GE = 1 GE = 0 GE =0

1

24

26

16

GE = 1 GE = 0

GE = 0

Arbore AVL dezechilibrat

ARBORI AVL



• Ultima operatie: inserare nod 26;

• Analiza drumului de la nodul 26 rădăcină

conduce la identificarea pivotului, nodul 27;

• Nodul 27: puternic dezechilibrat la stânga,

nodul fiu, nodul 23, este dezechilibrat slab

pe direcţia opusă;

24

ARBORI AVL



Simulare rotire simplă la dreapta aplicată

pivotului

25

23

10

27

2

16

GE = 2

GE = -1 GE = 2

GE = 0 GE = -1 GE =0

1

24

26

GE = 1

GE = 0

GE = 0

30


ARBORI AVL



Arborele AVL obtinut:

• Este dezechilibrat, dar în sens opus;

• Reechilibrarea: tot cu o rotire simplă, dar în

sens opus: va conduce la obţinerea ipotezei

iniţiale;

• Solutia este ineficienta.

26

ARBORI AVL



Soluţia eficientă:

• Aplicarea unei rotiri duble: constă în două

rotiri simple;

• Prima rotire: scop de a rearanja structura

arborescentă astfel încât direcţiile

dezechilibrului nodului pivot şi a fiului

acestuia să aibă acelaşi sens;

• A doua rotire are ca obiectiv reechilibrarea

arborelui;

27

ARBORI AVL



Soluţia eficientă (continuare):

• Cele două rotaţii sunt aplicate unor noduri

diferite;

• Prima rotaţie: nodului fiu al nodului pivot, pe

direcţia dezechilibrului;

• A două rotire: nodului pivot şi are sens opus

dezechilibrului.

28

ARBORI AVL



Pivotul este nodul 27, puternic dezechilibrat la

stânga.

Etape pentru a reechilibra arborele:

• Se analizează nodul fiu al nodului pivot pe

direcţia dezechilibrului, nodul 23 şi este slab

dezechilibrat la dreapta;

• Reechilibrare printr-o dublă rotaţie (pivotul

şi nodul fiu sunt dezechilibrate pe direcţii

diferite);

29

ARBORI AVL



Etape pentru a reechilibra arborele (cont.):

• Prima rotaţie se aplică nodului fiu; are sens identic

cu dezechilibrul nodului pivot; redefineşte situaţia

pentru aplicarea unei rotaţii simple

• A doua rotaţie se aplică nodului pivot şi are sens

opus dezechilibrului

30

ARBORI AVL



27

10

30

2

23

GE = 2

GE = -1 GE = -2

GE = 1

GE = 0

GE =0

1

24

26

16

GE = 1 GE = 0

GE = 0

27

10

30

2

24

GE = 2

GE = -1 GE = -2

GE = -1 GE = 0 GE =0

1

26

16

23

GE = 0 GE = -1

GE = 0

NOD PIVOT

NOD FIU

A) ROTATIE SIMPLA LA STANGA B) ROTATIE SIMPLA LA DREAPTA

NOD PIVOT

24

27

2

23

GE = 1

GE = -1 GE = 0

GE = -1 GE = 0 GE =0

1

26 30 16

GE = 0 GE = 0 GE = 0

C) ARBORE REECHILIBRAT

10

ARBORI AVL



Reechilibrare arbore AVL prin stergerea unei

chei 16 si inserarea cheii 25.

32

24

27

2

23

GE = 2

GE = -1 GE = 2

GE = -1 GE = -1 GE =0

1

26 30

25

GE = -1

GE = 0

GE = 0

10


ARBORI AVL



Există două noduri, 24 şi 10, ce descriu

dezechilibre puternice, GE = 2, la dreapta.

Analiza drumului de la noul nod inserat la

rădăcină arborelui, stabileşte ca fiind pivot

nodul cu valoarea 24.

33

ARBORI AVL



Reechilibrarea presupune:

• Rotaţie simpla la dreapta în nodul fiu al

pivotului 27; dacă pivotul are ambii fii atunci

rotaţia se face in direcţia dezechilibrului;

• Rotaţie simpla la stânga, în sens opus

dezechilibrului, în nodul pivot;

34

ARBORI AVL



24

27

2

23

GE = 2

GE = -1 GE = 2

GE = -1 GE = -1 GE =0

1

26 30

25

GE = -1

GE = 0

GE = 0

10

NOD PIVOT

NOD FIU

A) ROTATIE SIMPLA LA DREAPTA

24

26

2

23

GE = 2

GE = -1 GE = 2

GE = -1 GE = 1 GE =0

1

25 27

30

GE = 0

GE = 0

GE = 1

10

NOD PIVOT

NOD FIU

B) ROTATIE SIMPLA LA STANGA

26

27

2

24

GE = 1

GE = -1 GE = 0

GE = 0 GE = 1

1

25 30

GE = 0

GE = 0

GE = 0

10

23

GE =0

C) ARBORE REECHILIBRAT

ARBORI AVL



Situaţii dezechilibru arbori AVL (operatia de inserare)

Grad

echilibru

nod pivot

Nod fiu

analizat

Grad echilibru

nod fiu

Rotire

+2 dreapta +1 Simplă la stânga

+2 dreapta -1 Dublă la stânga: rotire simplă

la dreapta în fiul din dreapta

al pivotului; rotire simplă la

stânga în pivot.

-2 stânga -1 Simplă la dreapta

-2 stânga +1 Dublă la dreapta: rotire

simplă la stânga în fiul din

stânga al pivotului; rotire

simplă la dreapta în pivot.

ARBORI AVL



Din arborele AVL de mai jos, se şterge nodul

50.

37

47

35

50 37

22

16

42

31

9 27 32

29 GE =0

GE =0 GE =0

GE =0

GE =0 GE = -1

GE = -1 GE = -1

GE = 1

GE = 1

GE = -1

GE = -1 47

35 stiva

ARBORI AVL



47

35

37

22

16

42

31

9 27 32

29 GE =0

GE =0 GE =0 GE =0 GE = -1

GE = -1 GE = -1

GE = 1

GE = 1

GE = -2

GE = -1 35 stiva

42

35

37

22

16 47

31

9 27 32

29 GE =0

GE =0

GE =0

GE =0 GE = -1

GE = -1 GE = -1

GE = 1

GE = 0

GE =0

GE = -2

Structură arborescenta de tip AVL dezechilibrată prin

aplicarea unei rotaţii duble (1. stanga in 37, 2. dreapta

in 42)

ARBORI AVL



Printr-o rotaţie la dreapta în nodul cu valoarea

35 considerat pivot, arborele AVL este

reechilibrat.

Deoarece stiva a fost golită, operaţie de

ştergere se consideră încheiată

39

GE =0

GE = -1

42

35

37

22

16 47 31

9 27 32

29 GE =0

GE =0

GE =0

GE =0 GE = -1

GE = -1 GE = -1

GE = 1

GE = 0

GE =0

GE = -2

GE =0

42

35

37

22

16

47

31

9

27 32

29

GE =0 GE =0

GE =0

GE = -1

GE =0

GE = 1

GE = 0

GE =0

(1)

(2)

Structură arborescenta de tip AVL

ARBORI AVL



Situaţii de dezechilibru diferite de ipotezele analizate

la operaţia de inserare

40

GE =0

19

17

16 20

23

GE =0

GE = 1

GE = 0

GE =0 GE =0

19

17

20

23

GE = 2

GE = 0

GE =0

GE = -1

19

20

23 17

GE = 0

GE =0

GE = -1

Ştergere din structură arborescenta de tip AVL

Pivotul are un grad de echilibru +2, iar nodul fiu de pe direcţia

dezechilibrului are un echilibru 0.

Soluţia este data de o rotaţie simplă în pivot la stânga.

ARBORI AVL



Caracteristici:

• Tipologie de arbori binari de căutare

echilibraţi;

• Definiţi de Rudolf Bayer în 1972 sub forma

de arbori simetrici;

• Nodurile sunt plasate în mod simetric în

subarborii stânga sau dreapta.

41

ARBORI ROSU&NEGRU



Factorul cel mai important este dat de culoarea

fiecărui nod:

• Fiecare nod are una dintre cele două culori, roşu

sau negru;

• Nodul rădăcină este întotdeauna negru;

• Ambele noduri fiu ale unui nod părinte roşu sunt

negre; un nod roşu nu poate avea ca părinte decât

un nod negru;

• toate drumurile de la rădăcină la oricare din

nodurile frunză conţin acelaşi număr de noduri

negre.

42

ARBORI ROSU&NEGRU



23

15

27 18

3

2

Structură arborescenta de tip Roşu & Negru

ARBORI ROSU&NEGRU

STRUCTURI DE DATE - ASE · Reechilibrare arbore AVL prin stergerea unei chei 16 si inserarea cheii...

Documents

Transcript of STRUCTURI DE DATE - ASE · Reechilibrare arbore AVL prin stergerea unei chei 16 si inserarea cheii...