Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

volte e sono indipendenti. Con un po' di calcoletti scopri che il terzo viene eseguito

n

2

∑ 2

volte perciò ha complessità O(n loglogn).

loglogn i

i=1

for (i = 1; i < (N^2); i *= 2)

for (k = 1; k < N; k *= 3)

for (j = 1; j < (i^2); ++j)

++sum; 4

Smanettando un po' dovrebbe venir fuori che la complessità è O(n ).

In altre strutture di controllo (come while, if, switch) bisogna sempre considerare la

complessità massima per il calcolo. Le funzioni ricorsive invece si possono esaminare

attraverso le EQUAZIONI DI RICORRENZA e procedendo per sostituzione, oppure

effettuando una ANALISI PER LIVELLI. Ma il metodo più bello è il MASTER THEOREM.

Bisogna scrivere l'equazione della funzione nella forma T(n) = aT(n/b) + f(n) con n la

dimensione dell'input, a il numero di chiamate ricorsive nella funzione, n/b la dimensione

della chiamata ricorsiva e f(n) è la complessità del codice della funzione. Si deve

confrontare la funzione n^log a con f(n). A questo punto avremo tre casi:

b

Caso 1: se f(n) è O(n^(log a-ε)) con ε > 0 allora la complessità sarà n^log a (cioè

– b b

f(n) viene superata da n^log a)

b

Caso 2: se f(n) è Ω(n^(log a+ε)) con ε > 0 allora la complessità sarà f(n) (cioè f(n)

– b

supera n^log a)

b

Caso 3: se f(n) è Θ(n^(log a)) allora la complessità sarà logn*f(n)

– b

Prima di vedere il nostro primo tipo di struttura dati, dobbiamo parlare di TIPO DI DATO

ASTRATTO o TDA. Noi sappiamo già che il tipo di una variabile indica i valori che essa

può assumere e le operazioni che vi si possono compiere. Le strutture dati sono una sorta

di tipo, perché ogni struttura può essere rappresentata dai valori che può memorizzare e

dalle operazioni che vi si possono effettuare. Nel caso di una lista queste operazioni

possono essere l'inserimento di un elemento in coda, la rimozione di un elemento, lo

svuotamento ecc... Sono anche “astratte” nel senso che la loro definizione è indipendente

dall'implementazione e dal linguaggio di programmazione usato per realizzarle. Per

esempio una lista rimane tale, che essa sia implementata con un array o con una lista

concatenata. È proprio questo il tipo di dato astratto: un tipo che definisce solo

l'INTERFACCIA e le funzioni disponibili sul tipo di dato, indipendentemente da come è

implementato. Questo significa che se dovessimo cambiare l'implementazione in un

programma già scritto per migliorare le prestazioni, non romperemo i programmi che fanno

uso dell'implementazione vecchia.

In C++ i tipi di dato astratto si possono rappresentare per mezzo delle CLASSI

ASTRATTE, delle particolari classi che:

Specificano solo l'interfaccia

– Non sono istanziabili

– Fungono da classe base per ereditare classi più complesse

Per rendere astratta una classe, basta inserirci almeno una funzione virtuale pura, ovvero

virtual void foo() = 0.

nella forma Faremo anche uso della PROGRAMMAZIONE

GENERICA, in cui una funzione è definita indipendentemente dal tipo di dato che riceve in

ingresso, in quanto esso stesso è un parametro. Ciò si ottiene per mezzo dei template.

Per esempio per definire una funzione che ritorna il massimo tra due elementi potremmo

template <class T> T max(T a, T b)

usare questa dichiarazione:

Ora abbiamo le conoscenze preliminari necessarie per poter parlare di liste. Una LISTA è

una sequenza finita e ordinata di elementi. Ogni elemento nella lista è caratterizzato da

una posizione. Iniziamo a definire una classe astratta per la nostra lista, poi la

specializzeremo fornendo varie implementazioni:

template <class Elem> class List {

public: clear()

virtual void = 0;

insert(const

virtual bool Elem &) = 0;

append(const

virtual bool Elem &) = 0;

remove(Elem

virtual bool &) = 0;

setStart()

virtual void = 0;

setEnd()

virtual void = 0;

prev()

virtual void = 0;

next()

virtual void = 0;

leftLength()

virtual int const = 0;

rightLength()

virtual int const = 0;

setPos(int

virtual bool pos) = 0;

getValue(Elem

virtual bool &) const = 0;

print()

virtual void const = 0;

}

Le due implementazioni standard per una lista sono l'ARRAY e la LISTA CONCATENATA

con puntatori. Vediamo ora la classe lista basata su array.

template <class Elem> // Array-based list

class AList : public List<Elem> {

private:

int maxSize;

int listSize;

int fence;

Elem *listArray;

public:

AList(int size = DefaultListSize) {

maxSize = size;

listSize = fence = 0;

listArray = new Elem[maxSize];

}

void prev() {

if (fence != 0)

--fence;

}

bool setPos(int pos) {

if ((pos >= 0) && (pos <= listSize))

fence = pos;

return (pos >= 0) && (pos <= listSize);

}

};

template <class Elem>

bool AList<Elem>::insert(const Elem &item) {

if (listSize == maxSize)

return false;

for (int i = listSize; i > fence; --i) {

listArray[i] = listArray[i-1]; // Shift Elems up to make room

}

listArray[fence] = item;

++listSize; // Increment list size

return true;

}

template <class Elem>

bool AList<Elem>::append(const Elem &item) {

if (listSize == maxSize)

return false;

listArray[listSize++] = item;

return true;

}

// Remove and return first Elem in right partition

template <class Elem>

bool AList<Elem>::remove(Elem &it) {

if (rightLength() == 0)

return false;

it = listArray[fence]; // Copy Elem

for (int i = fence; i < listSize-1; ++i)

listArray[i] = listArray[i+1]; // Shift them down

--listSize; // Decrement size

return true;

}

Questa è invece l'implementazione con una lista concatenata, dove creiamo una classe in

più per identificare i nodi.

template <class Elem> class Link { // Singly-linked list node

public:

Elem element; // Value for this node

Link *next; // pointer to next node

// constructor with initial value

Link(const Elem &elemval, Link *nextval = nullptr) {

element = elemval;

next = nextval;

}

// constructor without initial value

Link(Link *nextval = nullptr) {

next = nextval;

}

};

Com'è fatta una lista puntata lo sai, ma qui c'è una furbizia in più: è stato aggiunto un nodo

di testa “fittizio” in modo da evitare il controllo dei casi particolari di lista vuota!

// Linked list implementation

template <class Elem> class LList:

public List<Elem> {

private:

Link<Elem> *head; // Point to list header

Link<Elem> *tail; // Pointer to last Elem

Link<Elem> *fence; // Last element on left

int leftcnt; // Size of left

int rightcnt; // Size of right

void init() { // Initialization routine

fence = tail = head = new Link<Elem>;

leftcnt = rightcnt = 0;

}

void removeall() { //Return link nodes to free store

while (head != nullptr) {

fence = head;

head = head->next;

delete fence;

}

}

public:

LList(int size = DefaultListSize) {

init();

}

~LList() {

removeall();

}

};

// Insert at front of right partition

template <class Elem>

bool LList<Elem>::insert(const Elem &item) {

fence->next = new Link<Elem>(item, fence->next);

if (tail == fence)

tail = fence->next;

++rightcnt;

return true;

}

// Append Elem to end of the list

template <class Elem>

bool LList<Elem>::append(const Elem &item) {

tail = tail->next = new Link<Elem>(item, nullptr);

++rightcnt;

return true;

}

// Remove and return first Elem in right partition

template <class Elem>

bool LList<Elem>::remove(Elem &it){

if (fence->next == nullptr)

return false;

it = fence->next->element;

// Remember val

Link<Elem> *ltemp = fence->next; // Remember link node

fence->next = ltemp->next;

// Remove

if (tail == ltemp)

// Reset tail

tail = fence;

delete ltemp;

// Reclaim space

--rightcnt;

return true;

}

// Move fence one step left;

// no change if left is empty

template <class Elem>

void LList<Elem>::prev() {

Link<Elem> *temp = head;

if (fence == head)

return; // No prev Elem

while (temp->next!=fence)

temp=temp->next;

fence = temp;

--leftcnt;

++rightcnt;

}

// Set the size of left partition to pos

template <class Elem>

bool LList<Elem>::setPos(int pos) {

if ((pos < 0) || (pos > rightcnt+leftcnt))

return false;

fence = head;

for(int i = 0; i < pos; ++i)

fence = fence->next;

return true;

}

Dal codice si possono subito notare quali sono i vantaggi e gli svantaggi tra le due

implementazioni:

L'array è veloce nell'accesso agli elementi, avendo complessità costante O(1), ma

– l'inserimento e la rimozione richiedono una complessità lineare O(n).

La lista concatenata invece ha le caratteristiche opposte: è veloce nell'inserire e

– rimuovere elementi, ma richiede più tempo nell'accesso.

In termini di spazio, l'array è di dimensione statica, perciò la memoria viene sprecata se gli

elementi sono pochi. Nel caso della lista concatenata invece c'è un nodo per ogni

elemento, che però occupa più spazio dovendo anche memorizzare il puntatore.

Esistono delle estensioni della lista concatenata, due delle quali sono la FREE LIST e la

LISTA PUNTATA DOPPIA.

Le operazioni di new e delete sono costose per il sistema, come potremmo evitare di

usarle? Idea! Usiamo la classe Link per contenere una free list, ovvero quando si elimina

un elemento, lo si inserisce nella free list. Quando vogliamo creare un elemento, lo

preleviamo dalla free list. Se questa è vuota, allora facciamo new.

// Singly-linked list node with freelist

template <class Elem> class Link {

private:

static Link<Elem> *freelist; // Head

public:

Elem element; // Value for this node

Link *next; // Point to next node

Link(const Elem &elemval, Link *nextval = nullptr) {

element = elemval;

next = nextval;

}

Link(Link *nextval =nullptr) {

next = nextval;

}

void * operator new(size_t); // Overload

void operator delete(void *); // Overload

};

template <class Elem>

Link<Elem> *Link<Elem>::freelist = nullptr;

template <class Elem>

// Overload for new

void *Link<Elem>::operator new(size_t) {

if (freelist == nullptr)

return ::new Link;

Link<Elem> *temp = freelist; // Reuse

freelist = freelist->next;

return temp; // Return the link

}

template <class Elem>

// Overload delete

void Link<Elem>::operator delete(void *ptr) {

((Link<Elem> *)ptr)->next = freelist;

freelist = (Link<Elem> *)ptr;

}

Nella lista doppia ogni nodo contiene anche il puntatore all'elemento precedente. Questo

velocizza le operazioni di cancellazione.

// Doubly-linked list link node

template <class Elem> class Link {

public:

Elem element; // Value for this node

Link *next; // Pointer to next node

Link *prev; // Pointer to previous node

Link(const Elem &e, Link *prevp = nullptr, Link *nextp = nullptr) {

element=e;

prev=prevp;

next=nextp;

}

Link(Link *prevp = nullptr, Link *nextp = nullptr) {

prev = prevp;

next = nextp;

}

};

L'aggiunta di un secondo puntatore aumenta ancora di più lo spazio occupato. Un modo

per ovviare a questo è usare le proprietà fighissime dello XOR per cui (L^R)^R = L e

(L^R)^L = R. In pratica ogni nodo non contiene due puntatori ma ne contiene uno solo che

è lo XOR bit a bit dei due puntatori. Scorrendo la lista e usando le proprietà logiche dello

XOR possiamo ricavare tutti i puntatori che ci servono (non mostriamo l'implementazione

perché è un casino ma almeno l'idea c'è).

Un tipo particolare di lista è la PILA, in cui le uniche operazioni possibili sono l'inserimento

di un elemento in testa (PUSH), la rimozione dell'elemento in testa (POP) e la lettura

dell'elemento in testa (TOP). Può essere implementata come una doppia lista puntata e un

puntatore alla cima oppure come array. I vantaggi e svantaggi delle due implementazioni

sono ovvi. In entrambi i casi le operazioni di inserimento e rimozione hanno complessità

costante O(1). L'implementazione con array permette di mantenere due pile in un unico

array se le loro dimensioni sono inversamente proporzionali l'una dall'altra (esempio

heap/stack nell'architettura dei calcolatori).

Infine la CODA è un tipo di lista in cui l'inserimento avviene in un estremo (ENQUEUE) e

la rimozione nell'altro (DEQUEUE). Anche qui sono possibili le implementazioni via lista

puntata (nulla in particolare da aggiungere) oppure come array. Nel caso dell'array

dovremmo scegliere in quale estremo effettuare l'inserimento e in quale la rimozione,

considerando che una delle due operazioni avrebbe complessità costante e l'altra lineare.

Ma con una furbata possiamo rendere tutto costante! Teniamo un indice di inizio e un

indice di fine e modifichiamo solo questi indici nelle operazioni di enqueue e dequeue.

Quando i posti terminano, ricominciamo dalla posizione iniziale utilizzando l'operatore

modulo. Ovvero usiamo un ARRAY CIRCOLARE. Bellissimo. L'unico problema è capire

quando la coda è piena e non c'è più spazio per altri elementi: si può decidere se contare

il numero di elementi in coda o usare una variabile booleana.

Gli ALBERI sono la prima struttura dati non lineare che ci permetterà di fare tante cose

belle. Partiremo dall'albero binario (l'esempio più semplice) con le sue implementazioni,

per poi estenderci agli alberi generici, agli alberi n-ari, agli alberi binari di ricerca e agli

heap o code di priorità. Questa struttura è non lineare perché ad ogni elemento sono

associati più successori. Lo scopo è ridurre la complessità delle operazioni da O(n) a

O(logn).

La definizione di albero è ricorsiva: è un insieme finito di nodi che può essere vuoto

oppure essere composto da una radice e due sottoalberi, che a loro volta sono

alberi. Li distinguiamo come SOTTOALBERO SINISTRO e SOTTOALBERO DESTRO

(oppure, in nonnesco, ALBERU MASCHJ e ALBERU FEMMN).

Il PERCORSO è la sequenza di nodi da attraversare per passare da un nodo A a un nodo

B. Il numero di archi attraversati rappresenta la LUNGHEZZA del percorso.

La PROFONDITÀ di un nodo è la lunghezza del percorso che collega quel nodo alla

radice. La radice ha profondità 0.

L'ALTEZZA di un albero è il numero di livelli che lo compongono, ovvero la profondità del

nodo più profondo più 1.

Un nodo senza figli è detto FOGLIA oppure NODO ESTERNO.

I nodi con almeno un figlio sono detti NODI INTERNI.

Un albero è PIENO se tutti i nodi hanno zero o due figli.

Un albero è COMPLETO se tutti i livelli tranne l'ultimo sono pieni mentre l'ultimo livello è

riempito da sinistra (senza buchi in mezzo).

Per induzione si può dimostrare un teorema per valutare lo spazio occupato da un albero.

Dovremmo contare quanti sono i puntatori che puntano ad un nodo e quanti sono nulli (e

rappresentano quindi spazio sprecato). Sulle foglie abbiamo sempre due puntatori nulli,

mentre nei nodi interni uno o due puntatori sono occupati. Il minimo numero di foglie è nel

caso di una lista lineare, dove solo l'ultimo nodo è una foglia, mentre gli altri hanno tutti un

puntatore occupato. Il numero massimo di foglie si ha nel caso di un albero pieno, cioè

tutti i nodi hanno o zero o due puntatori occupati. Si dimostra che, in un albero pieno, le

foglie sono il numero di nodi interni più uno. Quindi se per esempio i nodi interni sono

10 avrai 11 foglie. Un corollario ci dice che in un albero binario non vuoto (di

qualunque forma, non necessariamente pieno) il numero di puntatori nulli è il

numero di nodi presenti nell'albero più uno. Si ottiene questa affermazione sostituendo

i puntatori nulli con delle foglie. In questo modo ci riconduciamo al caso dell'albero binario

pieno e grazie al teorema enunciato possiamo contare il numero di puntatori nulli!

Iniziamo a vedere quali sono le funzioni di un ADT per l'albero:

template <class Elem>

class BinNode {

public:

// Return the node's element

&val()

virtual Elem = 0;

// Set the node's element

setVal(const

virtual void Elem &) = 0;

// Return the node's left child

*left()

virtual BinNode const = 0;

// Set the node's left child

setLeft(BinNode

virtual void *) = 0;

// Return the node's right child

*right()

virtual BinNode const = 0;

// Set the node's right child

setRight(BinNode

virtual void *) = 0;

// Return true if the node is a leaf

isLeaf()

virtual bool = 0;

};

Ci sono diversi ALGORITMI DI ATTRAVERSAMENTO di un albero:

IN PROFONDITÀ cioè scendendo nei livelli, con tre ordini diversi:

– ORDINE SIMMETRICO: visito prima il sottoalbero di sinistra, poi il nodo

– corrente, poi il sottoalbero di destra LVR

CON PREORDINE: visito per primo il nodo corrente, VLR

– CON POSTORDINE: visito per ultimo il nodo corrente, LRV

A LIVELLI cioè esaminando ogni livello alla volta

L'implementazione in profondità è una cagata. Prendi sto codice e scambiando le righe

ottieni ognuna delle tre possibili varianti.

template <class Elem>

void preorder(BinNode<Elem> *subroot) {

if (subroot == nullptr)

return;

visit(subroot);

preorder(subroot->left());

preorder(subroot->right());

}

È bene sapere che il controllo del puntatore nullo va fatto dopo essere entrati nel nodo.

Non si fa un controllo e poi eventualmente si entra. Questo permette di usare lo stesso

codice per radice e sottoalberi senza distinzione di casi particolari.

L'attraversamento in profondità è utile per contare i nodi di un albero. È molto facile il

codice, ma basta aggiungere qualche caratteristica per complicare tutto e rendere

l'esercizio interessante.

L'attraversamento a livelli sembra difficile ma con una coda è una passeggiata! Indichiamo

con Q la coda e k il nodo. Guarda, poche righe sono:

Q.enqueue(radice);

while (!Q.empty()) {

visit(k = Q.dequeue());

Q.enqueue(k->left());

Q.enqueue(k->right());

}

L'implementazione classica è quella lista puntata con due puntatori. In alcuni casi può

essere utile fare distinzione tra nodi interni e foglie. Per esempio nell'albero delle

espressioni matematiche, solo gli operatori binari hanno dei puntatori agli operandi. Gli

operandi non hanno figli quindi non ha senso inserire dei puntatori nei loro nodi. In questo

caso è utile il polimorfismo e il dynamic binding: si può creare un nodo virtuale base da cui

far discendere il nodo per gli operatori e il nodo per gli operandi. Il puntatore in ogni nodo

sarà di tipo generico verso la classe base.

L'overhead richiesto per i puntatori è di circa 2/3 contro 1/3 per i dati. Se distinguiamo i

nodi interni dalle foglie le formule cambiano, dipende un po' da come l'albero è conciato.

L'albero binario completo ha un'implementazione interessante perché permette l'uso di un

array! Ogni indice coincide con l'elemento in quella posizione nell'albero seguendo l'ordine

in ampiezza per livelli! Per ogni elemento puoi identificare in modo univoco i parenti vari,

giocando un po' con gli indici. Ovviamente risparmi un sacco di spazio in memoria.

La prima applicazione di albero binario è il BINARY SEARCH TREE o BST. È un albero

con la seguente proprietà: ogni nodo è associato ad una chiave K, tutti i nodi del

sottoalbero di sinistra hanno chiave minore di K, tutti i nodi del sottoalbero di destra hanno

chiave maggiore o uguale a K. Un BST con gli stessi elementi può avere forme diverse,

perché dipende un po' tutto dal nodo di partenza e dall'ordine con cui i nodi vengono

inseriti. Una caratteristica bella è che se lo attraversi in ordine LVR ottieni gli elementi già

in ordine! Inoltre anche la ricerca di un elemento è veloce perché è equivalente ad una

ricerca binaria. Tuttavia l'efficienza del BST dipende da quanto è bilanciato l'albero. Se è

bilanciato infatti è efficiente con complessità O(logn). Nel peggiore dei casi diventa una

lista per cui ha complessità lineare.

La ricerca e l'inserimento sono facili e ci arrivi da solo come funzionano. La cancellazione

è un po' più complicata perché devi sistemare i puntatori... Mettiamo caso che dobbiamo

cancellare il nodo R figlio di S, si verificano tre casi:

R non ha figli, per cui il puntatore di S punterà a NULL

– R ha un figlio, per cui il padre punterà ad esso

– R ha due figli, l'approccio più intelligente è sostituire il nodo con uno dei sottoalberi

– in modo da preservare la caratteristica di un BST, ovvero lo si può sostituire con:

La chiave minore del sottoalbero di destra, oppure

– La chiave maggiore del sottoalbero di sinistra

Un altro approccio alla cancellazione è quello “pigro”: si segnano i nodi da cancellare

come eliminati tramite un flag, ma non si eliminano fisicamente. Vuol dire che gli algoritmi

di ricerca devono considerare questi flag e i nodi virtualmente cancellati sono un overhead

in termini di spazio. È quindi necessario ogni tanto ripulire e sistemare l'albero.

Le prestazioni di un BST dipendono molto dal bilanciamento. La ricerca nel caso medio

ha un costo O(logn), ma se l'albero è sbilanciato è O(n). L'inserimento di N nodi ha un

2

costo O(nlogn) nel caso medio ma è ben O(n ) nel caso di un albero sbilanciato.

L'attraversamento invece è sempre O(n).

template <class Key, class Elem>

bool BST<Key, Elem>::findhelp(BinNode<Elem> *subroot, const Key &K, Elem &e) const {

if (subroot == nullptr)

return false;

else if (K < subroot->val())

return findhelp(subroot->left(), K, e);

else if (K > subroot->val())

return findhelp(subroot->right(), K, e);

else {

e = subroot->val();

return true;

}

}

template <class Key, class Elem>

BinNode<Elem> *BST<Key, Elem>::inserthelp(BinNode<Elem> *subroot, const Elem &val) {

if (subroot == nullptr) // Empty: create node

return new BinNodePtr<Elem>(val, nullptr, nullptr);

if (val < subroot->val())

subroot->setLeft(inserthelp(subroot->left(), val));

else subroot->setRight(inserthelp(subroot->right(), val));

// Return subtree with node inserted

return subroot;

}

template <class Key, class Elem>

BinNode<Elem> *BST<Key, Elem>::removehelp(BinNode<Elem> *subroot, const Key &K, BinNode<Elem>

*&t) {

if (subroot == nullptr)

return nullptr;

else if (K < subroot->val())

subroot->setLeft(removehelp(subroot->left(), K, t));

else if (K > subroot->val())

subroot->setRight(removehelp(subroot->right(), K, t));

}

I BST sono alberi utili e facili da implementare, che hanno il difetto però di diventare

sbilanciati col tempo e quindi di perdere in prestazioni. Alcune varianti rendono

l'inserimento e la cancellazione più costosi per rendere l'albero costantemente bilanciato.

Una variante interessante è il K-D TREE utilizzato per chiavi multidimensionali (per

esempio punti nello spazio). In questi alberi si introduce il DISCRIMINATORE ovvero la

variabile da utilizzare per il confronto nella scelta del sottoalbero. Ad ogni livello si alterna il

discriminatore tra le variabili utilizzando l'operatore modulo.

Ci sono tantissime versioni di alberi che cercano di mantenere il bilanciamento. Uno di

questi è l'AVL, che ha la proprietà di essere un BST in cui il sottoalbero di sinistra e il

sottoalbero di destra hanno un'altezza che differisce al massimo di 1. Per ottenere questo

risultato può applicare una rotazione singola o una rotazione doppia dei nodi. Non

vediamo l'implementazione perché è un po' complicatuccia (bisogna incasinarsi coi

puntatori) ma è bene citarlo. Un altro esempio è la SKIP LIST in cui ogni nodo può avere

più puntatori: uno all'elemento successivo, uno a due elementi successivi, un altro a

quattro elementi successivi e così via. Si fa in modo che tutti i nodi abbiano un puntatore,

che la metà dei nodi ne abbia due, che un quarto dei nodi ne abbia tre eccetera.

All'aumentare dei nodi la probabilità di una skip list di essere meno efficiente di un BST

decresce esponenzialmente. Anche di questo non vediamo l'implementazione ma è bene

conoscerlo.

Un tipo di albero che invece ci interessa particolarmente è lo HEAP o CODA DI

PRIORITÀ. È una struttura dati in cui si possono fare due operazioni: inserire un oggetto e

rimuovere l'oggetto con chiave maggiore. Le altre strutture viste finora non sono adatte

perché hanno tutte complessità lineare o logaritmica per la ricerca dell'elemento con

chiave maggiore. Sarebbe bello avere una struttura dati che fa entrambe le cose a tempo

costante, perché sembrerebbe più che fattibile. Per definizione lo heap è un albero

binario completo con ordinamento parziale, ovvero il padre ha chiave maggiore dei figli

(MAXHEAP) o dualmente il padre ha chiave minore dei figli (MINHEAP). L'ordinamento è

parziale perché sappiamo la relazione padre-figlio ma non tra fratelli come avviene nel

BST classico. Dal punto di vista logico lo heap è un albero, ma abbiamo visto che un

albero binario completo può essere implementato efficientemente come array e questo è

ciò che avviene! Dato un elemento in posizione i, il padre è l'elemento in posizione

floor(i/2) mentre i figli sono in posizione 2*i e 2*i+1 (questo vale se contiamo da 1, nei

linguaggi di programmazione in cui contiamo da 0 dobbiamo aggiungere 1 ad ogni indice).

La costruzione di un heap si fa applicando l'algoritmo di SIFTDOWN: ovvero quando si

inserisce un elemento si parte dagli indici alti, si guardano i figli e si scambia il valore con il

figlio che ha valore più grande del padre (se esiste) e si fa scendere il valore fino al livello

corretto. Siccome le foglie non hanno figli, non si parte dal fondo ma da metà array. A

questo punto se vogliamo l'elemento con maggiore priorità ci basta prendere la radice. Per

aggiornare lo heap la radice viene sostituita con l'ultimo elemento dell'array e si applica lo

siftdown a quel nodo.

Il costo di una singola chiamata a siftdown è logaritmico, mentre l'intera costruzione di uno

heap è la somma delle chiamate a siftdown che è lineare, quindi la costruzione è

O(nlogn). La rimozione dell'elemento massimo richiede la chiamata a siftdown per cui è

logaritmica. Lo heap è una struttura efficiente solo per queste operazioni, ma fa schifo

nella ricerca di un elemento arbitrario. D'altronde è solo una coda con priorità eh :P

template <class Elem, class Comp>

void maxheap<Elem, Comp>::siftdown(int pos) {

while (!isLeaf(pos)) {

int j = leftchild(pos);

int rc = rightchild(pos);

if ((rc<n) && Comp::lt(Heap[j], Heap[rc]))

j = rc;

if (!Comp::lt(Heap[pos], Heap[j]))

return;

swap(Heap, pos, j);

pos = j;

}

}

void buildHeap() {

// Heapify contents of Heap

for (int i = n/2-1; i >= 0; --i)

siftdown(i);

}

template <class Elem>

bool maxheap<Elem>::removemax(Elem &it) {

if (n == 0)

return false; // Heap is empty

it = Heap[0];

Heap[0] = Heap[--n];

if (n != 0)

siftdown(0);

return true;

}

Dagli alberi binari possiamo passare agli ALBERI GENERICI, ovvero alberi con un

numero arbitrario di figli. Non cambia nulla concettualmente. Solo aggiungiamo due termini

tecnici che sono OUT DEGREE di un nodo (il numero di figli) e FORESTA (una collezione

di alberi).

// General tree node ADT

template <class Elem> class GTNode {

public:

GTNode(const Elem &); // Constructor

~GTNode(); // Destructor

Elem value(); // Return value

bool isLeaf(); // TRUE if is a leaf

GTNode *parent(); // Return parent

GTNode *leftmost_child(); // First child

GTNode *right_sibling(); // Right sibling

void setValue(Elem &); // Set value

void insert_first(GTNode<Elem> *n);

void insert_next(GTNode<Elem> *n);

void remove_first(); // Remove first child

void remove_next(); // Remove sibling

};

template <class Elem> class GenTree {

private:

void printhelp(GTNode *); // Print helper function

public:

GenTree(); // Constructor

~GenTree(); // Destructor

void clear(); // Send nodes to free store

GTNode *root(); // Return the root

void newroot(Elem &, GTNode<Elem> *, GTNode<Elem> *); // Combine two subtrees

void print(); // Print a tree

};

L'attraversamento è simile a quello degli alberi binari, solo che si effettua solo in

preordine o postordine, mentre quello in ordine non è definito.

template <class Elem>

void GenTree<Elem>::preorder(GTNode<Elem> *subroot) {

if (subroot->isLeaf())

cout << "Leaf: ";

else

cout << "Internal: ";

cout << subroot->value() << "\n";

for (GTNode<Elem> *temp = subroot->leftmost_child(); temp != nullptr; temp = temp->right_sibling())

preorder(temp);

}

Da questo algoritmo di attraversamento si può già vedere una delle possibili

implementazioni per la gestione di più figli, ed è questa la parte rilevante negli alberi

generici: come indicare i rapporti di parentela.

LISTA DEI FIGLI: ogni nodo è un record contenente il dato, il puntatore al padre e il

– puntatore alla lista dei figli. È veloce per trovare i figli ma non i fratelli, per questo si

usa poco.

FIGLIO DI SINISTRA E FRATELLO DI DESTRA: ogni nodo è un record che

– contiene il dato, il puntatore al padre, al figlio di sinistra e al fratello di destra.

Risolve i problemi dell'implementazione precedente e ogni nodo ha dimensione

costante (non devi elencare tutti i figli). Permette agilmente anche l'unione di più

alberi cambiando pochi puntatori.

NODI DINAMICI: ogni nodo è un record con il dato e un array dinamico di puntatori

– ai figli. Non mi piace.

Infine ci sono gli ALBERI N-ARI che contengono un numero prefissato di figli. Non

differiscono proprio in niente rispetto agli alberi binari se non nel numero di figli. Le

applicazioni sono interessanti. Per esempio in grafica per memorizzare i punti di una figura

bidimensionale si usano i QUADTREE: lo spazio viene diviso in quattro quadranti a loro

volta divisibili in quattro quadranti più piccoli finché un quadrante non ha i pixel tutti dello

stesso colore e viene memorizzato come foglia. Si fa la stessa cosa in 3D con gli

OCTREE. Un'altra applicazione interessante è il TRIE ALFABETICO per memorizzare

parole, dove ogni nodo può avere un numero massimo di figli che dipende dal numero di

caratteri dell'alfabeto usato. Per questo sono utilizzati per implementare il T9 dei vecchi

telefoni :D


ACQUISTATO

4 volte

PAGINE

33

PESO

563.04 KB

AUTORE

fiorixf2

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica (COMO - CREMONA - MILANO)
SSD:
Docente: Comai Sara
A.A.: 2017-2018

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher fiorixf2 di informazioni apprese con la frequenza delle lezioni di Algoritmi e strutture dati e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Politecnico di Milano - Polimi o del prof Comai Sara.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in ingegneria informatica (como - cremona - milano)

Robotica - Elementi introduttivi
Dispensa
Controllo di posizione e velocità
Dispensa
Formulario Elettrotecnica
Appunto
Cinematica - Elementi
Dispensa