Strutture Dati

INTERSEZIONE

type Intersection(LA, LB){

if(head[LA]==null)

return (head[LA])

if(head[LB]==null)

return (head[LB])

PA=head[LA]

while(PA!=null){

PB=head[LB]

while((PB!=null)&&(key(PA)!=key(PB)))

PB=Next(PB)

if(PB!=null)

ListInsert(I, PA)

PA=Next(PA)

}

head[LA]=null

head[LB]=null

}

DIFFERENZA

type Difference(LA, LB){

if(head[LA]==null)

return (head[LA])

if(head[LB]==null)

return (head[LA])

PA=head[LA]

while(PA!=null){

PB=head[LB]

while((PB!=null)&&(key(PA)!=key(PB)))

PB=Next(PB)

if(PB==null)

ListInsert(D, PA)

PA=Next(PA)

}

head[LA]=null

head[LB]=null

}

UNIONE ORDINATA

type UnionOrder(LA, LB){

if(head[LB]==null)

return (head[LA])

if(head[La]==null)

return (head[LB])

if(key(head[LA])<key(head[LB]))

Assembla(head[LA], UnionOrder(Next(head[LA]), head[LB]))

if(key(head[LA])>key(head[LB]))

Assembla(head[LB], UnionOrder(head[LA], Next(head[LB])))

if(key(head[LA])==key(head[LB]))

Assembla(head[LA], UnionOrder(Next(head[LA]), Next(head[LB])))

}

INTERSEZIONE ORDINATA

type IntersectionOrder(LA, LB){

if(head[LA]==null)

return (head[LA])

if(head[LB]==null)

return (head[LB])

if(key(head[LA])<key(head[LB]))

Assembla(null, IntersectionOrder(Next(head[LA]), head[LB]))

if(key(head[LA])>key(head[LB]))

Assembla(null, IntersectionOrder(head[LA], Next(head[LB])))

if(key(head[LA])==key(head[LB]))

Assembla(head[LA], IntersectionOrder(Next(head[LA]), Next(head[LB])))

}

DIFFERENZA ORDINATA

type DifferenceOrder(LA, LB){

if(head[LA]==null)

return (head[LA])

if(head[LB]==null)

return (head[LA])

if(key(head[LA])<key(head[LB]))

Assembla(head[LA], DifferenceOrder(Next(head[LA]), head[LB]))

if(key(head[LA])>key(head[LB]))

Assembla(null, IntersectionOrder(head[LA], Next(head[LB])))

if(key(head[LA])==key(head[LB]))

Assembla(null, DifferenceOrder(Next(head[LA]), Next(head[LB])))

}

Genericamente con le operazioni senza aver ordinato prima i tempi sono di O(n*m),

considerando n ≈ m il tempo è O(n²); avendo ordinato prima i tempi invece sono di

O(n+m) a cui vanno aggiunti i tempi di ordinamento O(nlogn) e O(mlogm) per un

totale di O(nlogn + mlogm + n+m), considerando n ≈ m il tempo è O(2nlogn + 2n)

approssimabile a O(nlogn).

ALBERI

albero

Un viene definito ricorsivamente dicendo che è albero se è vuoto o ha per figli

degli alberi.

Si costruisce sul concetto di grafo con le particolari condizioni di non orientato,

nodi key

connesso e aciclico. Gli elementi dell’albero sono detti e sono costituiti da una

e da dei puntatori ad altri nodi. L’albero si sviluppa in verticale e il nodo da cui parte

root figli

che sta al vertice è detto . Da questo nodo si sviluppano altri nodi detti che a

loro volta potranno avere dei figli; i nodi che terminano l’albero, ovvero quelli senza

foglie profondità

figli sono detti nodi . Ogni nodo ha una sua (P) che corrisponde al

altezza

livello su cui si trova, la profondità massima dell’albero viene definita come (H).

completo

Un albero è se ogni nodo ha sempre 2 figli, eccetto quelli che si trovano

sull’ultimo livello, l’altezza sarà logH. variabile

Per controllare che un albero sia bilanciato per ogni nodo viene usata una

sbilanciamento differenza dell’altezza tra il sottoalbero SX e DX

che controlla la del

nodo; se questo valore è positivo l’albero è sbilanciato a desta, mentre se negativo è

sbilanciato a sinistra, in caso sia uguale a 0, l’albero risulta bilanciato. Se il valore

supera |2| effettuata una rotazione

viene sul albero in modo che la variabile

sbilanciamento torni ad essere uguale a 0. Le performance restano ottimizzate se non

è necessario ruotare tante volte l’albero.

Alberi Binari di Ricerca

In particolare consideriamo gli (Search Binary Tree), in cui

ogni nodo può avere massimo 2 figli e ogni nodo avrà elementi minori a sinistra e

maggiori a destra.

IMPLEMENTAZIONE IN PSEUDO-CODICE

STAMPA ELEMENTI

Non ricorsivamente , è anche possibile stampare per livello.

void Stampa(P){ //stampa scorrendo da sx a dx, usa le pile come appoggio

if(P==null)

return ( )

else{ Push(S, P)

while(not(SE(S))){

P=Pop(S)

Println(key(P))

if(Right(P)!=null)

Push(S, Right(P))

if(Left(P)!=null)

Push(S, Left(P))

}

}

}

void Stampa(P){ //stampa per livello, usa le code come appoggio

if(P==null)

return ( )

else{ EnQueue(Q, P)

while(not(EQ(Q))){

P=DeQueue(Q)

Println(key(P))

if(Right(P)!=null)

EnQueue(Q, Right(P))

if(Left(P)!=null)

EnQueue(Q, Left(P))

}

}

}

Ricorsivamente, più semplice ma non è possibile stampare per livello.

void Stampa(P){

if(P!=null){

Stampa(Left(P))

Println(key(P))

Stampa(Right(P))

}

}

VISITE ELEMENTI

È possibile stampare gli elementi di un SBT secondo tre tipologie di ordine:

 Anticipato [ROOT, SX, DX]

 Simmetrico [SX, ROOT, DX]

 Posticipato [SX, DX, ROOT]

void Ant(T){

Println(key(T))

Ant(Left(T))

Ant(Right(T))

}

void Simm(T){

Simm(Left(T))

Println(key(T))

Simm(Right(T))

}

void Post(T){

Post(Left(T))

Post(Right(T))

Println(key(T))

}

INSERIMENTO ELEMENTO

L’inserimento di un nuovo elemento in un SBT avviene confrontando il valore da

inserire di volta in volta coi nodi dell’albero e spostandosi nei nodi sinistri se il valore

da inserire è più piccolo, viceversa nei nodi destri.

boolean SBT_Insert(T, x){

if(Root(T==null){

Root(T)=x

return true

}

else{ P=Root(T)

PA=null

while(P!=null){

PA=P

if(key(P)>key(x))

P=Left(P)

else P=Right(P)

}

if(key(PA)>key(x))

Left(PA)=x

else Right(PA)=x

}

}

RIMOZIONE ELEMENTO

La rimozione di un elemento da un SBT può avvenire secondo tre differenti modalità

in base alle caratteristiche del nodo da rimuovere:

 se è una foglia, viene rimossa direttamente senza creare problemi;

 se ha un solo figlio, il nodo viene rimosso e si fa un collegamento tra il padre e il

figlio del nodo da rimuovere, sostanzialmente si fa scalare il nodo figlio;

 se ha due figli, la key del nodo viene sostituita con la key del suo successore, e

poi viene eliminato il nodo successivo richiamando ricorsivamente il metodo che

rientrerà nei precedenti casi.

void SBT_Delete(T, x){

if((Left(x)==null)&&(Right(x)==null)){ //x nodo foglia

if(Parent(x)==null)

Root(T)=null

else{ if(x==Left(Parent(x)))

Left(Parent(x))=null

else Right(Parent(x))=null

}

}

else{ if((Left(x)==null)||(Right(x)==null))

Contrazione(T, x)

else{ S=SBT_Succ(x)

key(x)=key(S)

SBT_Delete(T, S)

}

}

}

void Contrazione(T, x){

if(Parent(x)==null){

if(Left(x)!=null){

Root(T)=Left(x)

Parent(Left(x))=null

}

else{ Root(T)=Right(x)

Parent(Right(x))=null

}

}

else{ if(x=Left(Parent(x)){

if(Left(x)!=null){

Left(Parent(x)=Left(x)

Parent(Left(x)=Parent(x)

}

else{ Left(Parent(x)=Right(x)

Parent(Right(x)=Parent(x)

}

}

else{ if(Left(x)!=null){

Right(Parent(x)=Left(x)

Parent(Left(x)=Parent(x)

}

else{ Right(Parent(x)=Right(x)

Parent(Right(x)=Parent(x)

}

}

}

}

RICERCA ELEMENTO

La ricerca in un SBT viene effettuata tramite la key dei nodi.

type SBT_Search(P, k){

if((P==null)||(key(P)==k)

return (P)

else{ if(key(P)>k)

r=SBT_Search(Left(P), k)

else r=SBT_Search(Right(P), k)

}

}

ELEMENTO MINIMO e ELEMENTO MASSIMO

Vengono cercati l’elemento con la chiave minore che si trova continuando a scorrere

verso sinistra nei nodi, e l’elemento con la chiave maggiore continuando a scorrere

verso destra.

type SBT_Min(T){

P=root(T)

if(P==null)

return(P)

else{ while(Left(P)!=null)

P=Left(P)

return (P)

}

}

type SBT_Max(T){

P=root(T)

if(P==null)

return(P)

else{ while(Right(P)!=null)

P=Left(P)

return (P)

}

}

ELEMENTO PRECEDENTE e ELEMENTO SUCCESSORE

Per un nodo viene cercato l’elemento subito più piccolo, il precedente, e subito più

grande, il successore.

type SBT_Prec(P){

if(Left(P)!=null){

R=SBT_Max(Left(P))

return(P)

}

else{ while((Parent(P)!=null)&&(P!=(Right(Parent(P)))

P=Parent(P)

return (Parent(P))

}

}

type SBT_Succ(P){

if(Right(P)!=null){

R=SBT_Min(Right(P))

return(P)

}

else{ while((Parent(P)!=null)&&(P!=(Left(Parent(P)))

P=Parent(P)

return (Parent(P))

}

}

HEAP

heap struttura ad albero rappresentabile array

L’ è una speciale anche attraverso un ,

accedere direttamente nodo

così da poter ad ogni dell’albero. Per essere un heap

binario quasi completo

l’albero deve essere e , ovvero tutti i livelli devono essere

completi, eccetto l’ultimo che può anche essere incompleto, che deve essere completato

ordinamento

andando da sinistra a destra senza spazi vuoti. Esiste una sorta di che

padre sempre maggiore dei figli

consiste nel avere il nodo , ed è quindi possibile sapere

elemento massimo radice minimo

a priori la posizione del che sta nella , mentre il si

foglia Nell’array

trova sicuramente in una . gli elementi saranno disposti come radice-

gli

sinistro-destro, e accodati i figli di sinistro e poi quelli di destro, sostanzialmente

elementi vengono scritti livello per livello da sinistra a destra . Dalla posizione del

elemento padre è possibile trovare quella dei figli facendo 2*posizione (figlio sinistro) e

il successivo(figlio destro); se un nodo non ha uno o entrambi i figli, ha comunque le

caselle predisposte ma lasciate vuote.

HEAPSORT

L’heapsort è un algoritmo di ordinamento che a partire da un array disordinato lo va

ad ordinare in modo crescente. Si divide in due fasi:

 BuildHeap, crea un heap, andando a creare un primo ordinamento parziale;

 Ciclo fino a finire gli elemento del albero

il massimo(prima posizione) è scambiato con l’ultimo elemento

o è decrementata la dimensione del heap

o è chiamato il metodo Heapify che risistema l’albero in modo che sia un

o heap.

void Heapify(A, k){

largest=k

if((Left(x)<=heapSize(A))&&(A[Left(x)]>A[largest]))

largest=Left(k)

if((Right(x)<=heapSize(A))&&(A[Right(x)]>A[largest]))

lar