Bilanciamento Alberi Binari di Ricercadepoli/fi2ae/slides_pw/... · Albero Binario di Ricerca...

1

1

BilanciamentoAlberi Binari di Ricerca

G.T. 10.2.1 e 10.2.2

Alberi AVL (Adel'son-Vel'skii-Landis)

2

Alberi Binari di Ricerca

2

3

Albero Binario di Ricerca

DEFINIZIONE: è un albero binario proprioad ogni nodo interno è associato un Entry (key, elem)è definito l'ordinamento: k(left(v)) ≤ k(v) ≤ k(right(v))

OPERAZIONI:find(k) -> ritorna l’entry con key = kfindAll(k) -> iterator di tutte le entry con key = kinsert(k, x) -> inserisce l’entryremove(e) -> rimuove l’entry, e la ritorna

COMPLESSITA‘ e BILANCIAMENTOO(h(n)) log(n+1) –1

3

5

Albero AVL

DEFINIZIONEAlbero Binario di Ricerca bilanciato

NODO BILANCIATOaltezza sotto-albero sinistro differisce da altezza sotto-albero destro di al più una unità

ALBERO BILANCIATOtutti i nodi sono bilanciati

OPERAZIONIcome in albero binario di ricerca

COMPLESSITA' O(h(n)) O(log(n))

6

AVL Tree - esempio

44

78

8850

48 62

17

32

1

2

4

3

12

1 1

albero binario di ricerca bilanciato

4

7

Altezza di un AVL

L’altezza di un AVL con entry è n )(log nO

Determiniamo - numero minimo di nodi di un AVL di altezza )(hn h

1)1( =n 2)2( =nRisulta: e

)(hn

)1( −hn )2( −hn

)2()1(1)( −+−+= hnhnhn

3≥hRisulta, per :

8

Altezza di un AVL 2

)2()1( −>− hnhnPoiché è:

da:

risulta :

)2()1(1)( −+−+= hnhnhn

)2(2)( −⋅> hnhn

)2(2

)6(8)4(4)2(2)(

ihn

hnhnhnhn

i −⋅>

⋅−⋅>−⋅>−⋅>

per ogni , tale che i 12 ≥− ih

5

9

Altezza di un AVL 3

12

−⎥⎥⎤

⎢⎢⎡= hi

Scelto di modo che risulti

e cioè:

i 212 oih =−

)2(2)( ihnhn i −⋅>sostituendo il valore di nella

risulta:

i

12

12

12

2

)1(222

22)(

−

−⎥⎥⎤

⎢⎢⎡−⎥⎥

⎤⎢⎢⎡

≥

≥⎟⎟⎠

⎞⎜⎜⎝

⎛ +⎥⎥⎤

⎢⎢⎡−⋅>

h

hh

nhhnhn

e passando al logaritmo, risulta: 2)(log2 +< hnh

che implica e 2log2 +< nh )(log nOh =

10

Rotazioni in albero binario di ricerca

6

11

Rotazione di un albero binario

α

X

γ

Y

β

α

X

γ

Y

β

Rotazione destra di x su yRotazione destra di x su y

αα ≤≤ x x ≤≤ ββ ≤≤ y y ≤≤ γγ

la relazione d’ordine rimane invariata

12

Rotazione di un albero binario di ricerca

Rotazione destraRotazione destradi x su ydi x su y

X

γ

Y

α β

X

γ

Y

α

βαα ≤≤ x x ≤≤ ββ ≤≤ y y ≤≤ γγ

7

13

Ulteriori esercizi – Rotazione di nodi

void rightRotate( Position x ) { // RIGHT-ROTATEPosition y = parent(x);

setLeftChild( y, rightChild(x) ); setParent( rightChild(x), y );

if ( isRoot(y) ) { setRoot(x); setNullParent(x); } else if ( onLeft(y) ) {

setLeftChild( parent(y), x ); setParent( x, parent(y) ); } else {

setRightChild(parent(y), x ); setParent( x, parent(y) ); }

setRightChild(x,y); setParent(y,x);

return;}

14



X

γ

Y

α β

X

γ

Y

α

βPosition y = parent(x);

setLeftChild( y, rightChild(x) ); setParent( rightChild(x), y );

8

15


X

γ

Y

α β

X

γ

Y

α

β

if ( isRoot(y) ) { setRoot(x); setNullParent(x); } else if ( onLeft(y) ) {

setLeftChild( parent(y), x ); setParent( x, parent(y) ); } else {

setRightChild(parent(y), x ); setParent( x, parent(y) ); }

16



X

γ

Y

α β

X

γ

Y

α

β

setRightChild(x,y); setParent(y,x);

9

17

Insert in AVL-tree

Come per albero binario di ricerca+

eventuale ripristino del bilanciamentomediante opportune rotazioni

18

AVL Tree - Insert

44

78

8850

48 62

17

32

1

2

4

3

12

1 1

54insertinsert

come per albero binario di ricerca

ww

10

19

AVL Tree - Insert

44

78

8850

48 62

17

32 1

2

5

4

13

12

541

zz

yy

xx

T0 T1

T2

T31°) rotazione a sinistra di X su Y

ripristino bilanciamento

ww

20

AVL Tree - Insert

2°) rotazione a destra di X su Z

44

78

88

50

17

32 1

2

5

4

1362

2

zz

yy

xx

481

T0

541

T1

T2T3

ripristino bilanciamento

11

21

AVL Tree - Insert

bilanciamento O.K.44

7850

17

32 1

2

4

2

362

2

zzyy

xx

481

T0

541

T1

T288

1

T3

22

Insert in AVL - caso 1°

W

A

X

B

C

Y

Z

h+1h+1 hh

hhh+2h+2

h+3h+3

A

X

B C

Y

Zh+1h+1

hh hh

h+2h+2

h+1h+1

12

23

Insert in AVL - caso 2° – passo 1

1

A

X

C

D

Y

Z

h+1h+1

hhh+2h+2

h+3h+3

B

hh

hh hh--11

A

X

CD

Y

Z

h+1h+1

hhh+2h+2

h+3h+3

B

hhhh--11

hh

w

24

Insert in AVL - caso 2° – passo 2

2

A

X

CD

Y

Z

h+1h+1

hhh+2h+2

h+3h+3

B

hhhh--11

hh

A

X

CD

Y Zh+1h+1

hh

h+2h+2

B

hh hh--11hh

h+1h+1

13

25

AVL Tree – ristrutturazione a 3 nodi

ridenominazione nel inorder

γ

α β

δXa →

Yb →

Zc →

γα β δ

a (X) c (Z)

b (Y)

26

AVL Tree – ristrutturazione a 3 nodi

ridenominazione nel inorder

α

δ

β γ

Xb →

Ya →

Zc →

γα β δ

a (Y) c (Z)

b (X)

14

27

Inserimento

inserimento nodo W come in BST, ciò può sbilanciare qualche

nodo nel percorso da nodo W a radice :

nel cammino da W a radice

Z primo nodo sbilanciato

Y figlio di Z

X figlio di Y

effettuare ristrutturazione su tre nodi (inorder )

il bilanciamento è ripristinato sia localmente sia globalmente

complessità ribilanciamento: O(1)

28

Remove in AVL-tree

Come per albero binario di ricerca+

eventuale ripristino del bilanciamentomediante opportune rotazioni

15

29

AVL Tree - Remove

44

7850

17

32 1

2

4

2

362

2

481

541

881

remove 32

30

AVL Tree - Remove

44

7850

17

32

1

4

2

362

2

zz

yy

xx

481

T0

541

T1T2

881

T3

0

rotazione a sinistra di Y su Z

remove 32

16

31

AVL Tree - Remove

44

4

3

62

zz

yy

50 2

481

541

T1

17 1

T0

78 2

xx

881

T3

T2

0

risultato finale

32

AVL Tree - Remove

1) come per albero binario di ricerca, rimuovi nodo avente padre W

2) nel cammino dal nodo W alla radice vi può essere un primo nodo sbilanciato, chiamiamolo Z

3) diciamo Y il figlio più alto di Z e X il figlio più alto di Y ( se X non è unico, si prende il nodo che è dalla stessa parte di Y )

4) effettuiamo la ristrutturazione sui tre nodi (X, Y, Z), ciò può ridurre l'altezza dell'albero con radice in b di una unità

5) il bilanciamento viene ripristinato localmente ma non necessariamente a livello globale, un ascendente di b può divenire sbilanciato, ripetere l'operazione . . .

complessità ribilanciamento: O(log n)

17

33

AVL tree

Implementazione

34

Code Fragment 10.7 – G.T. p. 438 1

public class AVLTree extends BinarySearchTreeimplements Dictionary {

public AVLTree( Comparator c ) { super(c); }

protected static class AVLNode extends BTNode {protected int height; // we add a height field to a BTNode// . . . . . . . .// . . . . . . . .

}

18

35

Code Fragment 10.7 – AVLNode 2

protected static class AVLNode extends BTNode{protected int height; // we add a height field to a BTNode

AVLNode( element, BTPosition parent,BTPosition left, BTPosition right) {

super(element, parent, left, right);height = 0;if ( left != null )

height = Math.max( height, 1 + ((AVLNode) left).getHeight());if (right != null)

height = Math.max(height, 1 + ((AVLNode) right).getHeight());} // we assume that the parent will revise its height if neededpublic void setHeight(int h) { height = h; }public int getHeight() { return height; }

}

36

Code Fragment 10.7 – AVLTree 3

//Creates a new binary search tree node (overrides super's ver.)protected BTPosition createNode ( element,

BTPosition parent, BTPosition left, BTPosition right) {

return new AVLNode(element, parent, left, right); }

// Returns the height of a node (call back to an AVLNode)protected int height (Position p) {

return ( (AVLNode ) p ).getHeight();}

19

37

Code Fragment 10.7 – 4

//Sets the height of an internal node (call back to an AVLNode)// called only if p is internalprotected void setHeight( Position p ) {

( (AVLNode ) p ).setHeight( 1 + Math.max( height(left(p)), height(right(p)) ) );

}

//Returns whether a node has balance factor between -1 and 1protected boolean isBalanced(Position p) {

int bf = height( left(p)) - height(right(p) );return ( (-1

20

39


protected void rebalance( Position zPos ) {if( isInternal(zPos) ) setHeight(zPos);while ( ! isRoot(zPos) ) { //traverse up the tree towards the root

zPos = parent(zPos); setHeight(zPos);if ( ! isBalanced(zPos) )

{ // perform a 3node restruct. at zPos's tallest grandchildPosition> xPos = tallerChild( tallerChild(zPos));

// tri-node restructure (from parent class)zPos = restructure(xPos); setHeight( left(zPos) ); //recompute heightssetHeight( right(zPos)); setHeight( zPos );

} //end if} // end while

} //end method

40


public Entry insert (K k, V v) throws InvalidKeyException {Entry toReturn =

super.insert(k, v); // calls our new createNoderebalance (actionPos); // rebalance up from the insertion positionreturn toReturn;

}

public Entry remove (Entry ent) throws InvalidEntryException {

Entry toReturn = super.remove(ent);if (toReturn != null) // we actually removed something

rebalance (actionPos); // rebalance up the treereturn toReturn;

}

21

41

BinarySearchTree - restructure 1.1

protected Position restructure(Position x ) {

BTPosition a, b, c, t1, t2, t3, t4;

Position y = parent(x); // assumes x has a parent

Position z = parent(y); // assumes y has a parent

boolean xLeft = (x == left(y));

boolean yLeft = (y == left(z));

Position xx = (Position)x,

yy = (Position)y,

zz = (Position)z;

42


if ( xLeft && yLeft ) { a = xx; b = yy; c = zz; t1 = a.getLeft(); t2 = a.getRight();t3 = b.getRight(); t4 = c.getRight();

}else if ( ! xLeft && yLeft ) {

a = yy; b = xx; c = zz; t1 = a.getLeft(); t2 = b.getLeft();t3 = b.getRight(); t4 = c.getRight();

}

t3

t1 t2

t4Xa →Yb →

Zc →

t1

t4

t2 t3

Xb →

Ya →

Zc →

22

43


else if ( xLeft && ! yLeft) { a = zz; b = xx; c = yy; t1 = a.getLeft(); t2 = b.getLeft();t3 = b.getRight(); t4 = c.getRight();

}else { // right-right

a = zz; b = yy; c = xx; t1 = a.getLeft(); t2 = b.getLeft(); t3 = c.getLeft(); t4 = c.getRight();

}

44


// put b at z's placeif ( isRoot(z) )

{ root = b; b.setParent(null); }else {

BTPosition zParent = (BTPosition) parent(z);if ( z == left(zParent) ) {

b.setParent(zParent);zParent.setLeft(b);

}else { // z was a right child

b.setParent(zParent);zParent.setRight(b);

}}

23

45


// place the rest of the nodes and their childrenb.setLeft(a); a.setParent(b);b.setRight(c); c.setParent(b);

a.setLeft(t1); t1.setParent(a); a.setRight(t2); t2.setParent(a);

c.setLeft(t3); t3.setParent(c);c.setRight(t4); t4.setParent(c);

// Reset the location-aware entries( (BSTEntry) a.element() ).pos = a;( (BSTEntry) b.element() ).pos = b;( (BSTEntry) c.element() ).pos = c;return b; // the new root of this subtree

}

T3T1 T2 T4

a c

b

Bilanciamento Alberi Binari di Ricercadepoli/fi2ae/slides_pw/... · Albero Binario di Ricerca...

Documents

Transcript of Bilanciamento Alberi Binari di Ricercadepoli/fi2ae/slides_pw/... · Albero Binario di Ricerca...