Alberi e grafi

Gli alberi sono grafi, in cui individuiamo una radice, dei figli e dei padri.

Heap

Un albero che soddisfa la "proprietà di heap":

max heap se X è un genitore di Y, allora X.key $\ge$ Y.key
min heap se X è un genitore di Y, allora X.ky $\le$ Y.key

Gli heap vengono utilizzati in situazioni tipo:

code con priorità
ordinare vettori

Implementazione Heap Binari

Heap implementati come vettori. Figlio sx del n-esimo nodo $2n$, figlio dx del n-esimo nodo $2n +1$ .

Max Heapify e complessità

Funzione che trasforma un array in un heap. Idea: spingo elementi in fondo al vettore scambiandoli con i padri. NB: negli Heap il massimo/minimo (a seconda del tipo di Heap) lo si ottiene sempre con $O(1)$ .

Cancellazione/inserimento in $O(log(n))$
Accodamento/estrazione in $O(log(n))$
creazione =$O(n)$

BUILD-MAX-HEAP(A){
	A.heapSize := A.length 
	for i := A.length/2 downto 1 
		MAX-HEAPIFY(A, i)
}

che costa $O(n)$; è "lunghina" la dimostrazione che costa questo e non $O(n log(n))$.

MAX-HEAPIFY(A, max){
	(A, i) 
	l := LEFT(i) 
	r := RIGHT(i) 
	
	if l <= A.heapSize and A[l] > A[i] 
		max := l 
	else 
		max := i 
	
	if r <= A.heapSize and A[r] > A[max] 
		max := r 
		
	if max != i then 
	swap(A[i],A[max]) 
	
	MAX-HEAPIFY(A, max)
}

che costa $O(log(n))$ .

Operazioni:

INSERISCI(A,k){
	A.heapSize := A.heapSize+1;
	A[A.heapSize] = k;
	i = A.heapSize;
	while(i>1 && A[parent(i)] < A[i]){
		swap(A[parent(i)],A[i]);
		i <- parent[A];
	}
}

CANCELLA-MAX(A){
	if(A.heapSize < 1) return ;
	max := A[1];
	swap(A[1],A[A.heapSize]);
	A.heapSize := A.heapSize-1;
	MAX-HEAPIFY(A, 1)
	return max;
}

BT - Binary Tree

BST - Binary Search Tree

Degli alberi di ricerca sono alberi binari in cui sussiste una certa relazione tra i padri e i figli. Questa relazione, se sensata, ci permette di navigare e quindi cercare meglio nell'albero. Gli alberi possono essere binari o non binari a seconda del numero della prole di ciascun nodo. In questo corso ci concentreremo principalemente su quelli binari. Un albero binario di ricerca è un albero binario nel quale: la key di ogni nodo $X$, se $Y$ è un nodo del sottoalbero sinistro di $X$, vale che $X.key$ $\ge$ $Y.key$ . Mentre se $Z$ è un nodo del suo sottoalbero destro vale $Z.key \ge X.key$ .

{width=50%}

I BST sono la concretizzazione in struttura della ricerca binaria. Molto efficienti, ma devono essere correttamente bilanciati! Se ad esempio un nodo finisce per diventare una lista (caso pessimo) non abbiamo alcun tipo di vantaggio! Ricordati che c'è differenza tra BT e BST !

Complessità BST

$O(h)$(altezza albero) = $\Theta(log(n))$ (se completo/bilanciato) o $\Theta(n)$ (un ramo solo è ovviamente lineare).
Tutte le operazioni sui BST (SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR, INSERT, DELETE) hanno tempo di esecuzione che è $O(h)$

Quando usare BST:

il BST ad esempio mi permette di accedere all’elemento più vicino se quello cercato non è in lista
Non sono interessato all’accesso diretto. Mi interessa poter ricavare il minimo/massimo e/o predecessore successore, e se non presente l’elemento più vicino.
Il vantaggio principale è quello di combinare ordine e efficienza in ricerca/inserimento/eliminazione,usando solo la memoria necessaria.
La ricerca del max/min su un BST è meno efficiente di quella su uno HeapTree ($O(1)$) , ma io posso implementare un puntatore che punta sempre al max/min, facendo diventare max/min $O(1)$. Se però una voltra trovato il max/min devo eliminarlo dall’albero, dovrò comunque performare un’operazione di costo $log(n)$.

Attraversamento simmetrico

Restituisce i nodi ordinati se l’albero è un BST:

Prima si visita il sottoalbero sinistro e si restituiscono i suoi nodi
Si restituisce la radice
Si visita il sottoalbero destro e si restituiscono i suoi nodi. (ricorsivamente)

INORDER-TREE-WALK(x)
	if x != NIL
		INORDER-TREE-WALK(x.left)
		print x.key
		INORDER-TREE-WALK(x.right)

Anticipato (preorder tree walk) • in preorder, la radice è restituita prima dei sottoalberi • Posticipato (postorder tree walk) • in postorder, la radice è restituita dopo i sottoalberi

Ricerche

TREE-SEARCH(x, k)
	if x = NIL or k = x.key
		return x
	if k < x.key
		return TREE-SEARCH(x.left, k)
	else return TREE-SEARCH(x.right, k)

Minimo (foglia più a sinistra)

TREE-MINIMUM(x)
	while x.left != NIL
		x := x.left
	return x

Massimo (foglia più a destra)

TREE-MAXIMUM(x)
	while x.right != NIL
		x:= x.right
	return x

Successore e Predecessore

Il successore di un oggetto $x$ in un BST è l’elemento $y$ tale che $y$.key è la più piccola tra le chiavi che sono più grandi di $x$.key, cioè è il minimo del sottoalbero destro di $x$. Se il sottoalbero di $x$ è vuoto, il successore di $x$ è il primo elemento $y$ che si incontra risalendo nell’albero da $x$ tale che $x$ è nel sottoalbero sinistro di $y$: salgo dai “right” finchè non risalgo da un “left”.

TREE-SUCCESSOR(x)
	if x.right != NIL
		return TREE-MINIMUM(x.right)
	y := x.p
	while y != NIL and x = y.right
		x := y
		y := y.p
	return y

Il predecessore di un oggetto $x$ in un BST è l’elemento $y$ tale che $y.key$ è la più grande tra le chiavi che sono più piccole di $x.key$, cioè è il massimo del sottoalbero sinistro di $x$. Se il sottoalbero di $x$ è vuoto, il predecessore di $x$ è il primo elemento $y$ che si incontra risalendo nell’albero da $x$ tale che $x$ è nel sottoalbero destro di $y$: salgo dai “left” finchè non risalgo da un “right”. Codice analogo al SUCCESSORE.

Operazioni su BST

Inserimento

L'inserimento è molto semplice: scendere nell'albero fino a che non si raggiunge il posto in cui il nuovo elemento deve essere inserito, ed aggiungere questo come foglia.

TREE-INSERT(T, z)
	y := NIL
	x := T.root
	while x != NIL
		y := x
		if z.key < x.key
			x := x.left
		else x := x.right
	
	z.p := y
	if y = NIL //l'albero T e' vuoto
		T.root := z
	else if z.key < y.key
		y.left := z
	else y.right := z

Eliminazione

Quando cancelliamo un oggetto $z$ da un albero, abbiamo 3 possibili casi. Il nodo $z$ da cancellare:

non ha sottoalberi
ha 1 sottoalbero: ysy, si sposta l'intero sotto albero
ha 2 sottoalberi: sbattella, dobbiamo trovare il successore del nodo da cancellare $z$. Copiare la chiave del successore in $z$ e quindi cancellare il successore. Cancellare il successore potrebbe richiedere di spostare in sù il sottoalbero destro ma ysy. (notare che il successore è il minimo del sottoalbero, quindi al più avrà un sottoalbero destro).

TREE-DELETE(T, z)
	if z.left = NIL or z.right = NIL
		y := z
	else y := TREE-SUCCESSOR(z)
	
	if y.left != NIL
		x := y.left
	else x := y.right

	if x != NIL
		x.p := y.p
	if y.p = NIL
		T.root := x
	else if y = y.p.left
		y.p.left := x
	else y.p.right := x
	
	if y != z
		z.key := y.key
	
	return y

Possibile implementazione di Binary Trees

Un albero generale può essere rappresentato con una struttura a puntatori in cui ogni nodo $x$ ha 4 attributi: $x.key$ è la chiave, $x.p$ è il puntatore al padre, $x.fst$ è il puntatore al figlio più a sinistra, e $x.sibling$ è il puntatore al fratello a destra.

Fusione di due alberi binari di ricerca in uno bilanciato

Un algoritmo per costruire un albero bilanciato:

Si effettua visita "in ordine" dei due alberi $T_1$ e $T_2$, ottenendo due liste ordinate $L_1$ e $L_2$ .
Si fondono le due liste in un array ordinato.
Si crea un BST partendo dall'elemento centrale dell'array, poi ricorrendo sui due sottoarray rimanenti.

Quindi le complessità risultanti sono entrambe lineari nel numero dei nodi presenti nei sottoalberi: $S(n) = T(n) = (n)$, dove $n = n_1+n_2$ .

Alberi rosso-neri

Complessità $\rightarrow$ come un BST completo .

Quando usare i RB trees:

Il BST è molto vulnerabile a un caso comune: creare un albero troppo lungo a destra e a sinistra. Il modo per risolverlo è usare un RB (red and black tree) o simil alberi tipo gli alberi AVL (di Adelson-Velskii e Landis) . Questi alberi sono esattamente equivalenti ai BST ma sono bilanciati: nessun ramo è più lungo del doppio dell’altro. Conviene quasi sempre aggiungere questa nota nei temi.

Gli RB sono BST che si 'bilanciano' più facilmente. Proprietà degli alberi rosso-neri:

Ogni nodo è rosso o nero
la radice è nera
le foglie (NIL) sono tutte nere,
I nodi rossi hanno solo figli neri, quindi i nodi rossi possono avere come padri solo nodi neri.
Per ogni nodo $X$, tutti i cammini da $X$ alle sue foglie discendenti contengono lo stesso numero di nodi neri. (è la condizione più stringente).

Viene impiegato un tag rosso e uno nero sui nodi e vengono utilizzate rotazioni di nodi per mantenere la completezza.

Operazioni su RB trees

All’inserimento ogni nodo è rosso. Quindi, se anche il padre del nodo appena inserito è rosso, sistemo l’albero in modo che rispetti le regole dei colori.

Rotazioni:

LEFT-ROTATE(T,x)
	y := x.right
	x.right := y.left 
	if y.left != T.nil
		y.left.p := x
	y.p := x.p //attacca il padre di x a y
	if x.p = T.nil
		T.root := y
	else if x = x.p.left
		x.p.left := y
	else x.p.right := y
	y.left := x //mette x a sinistra di y
	x.p := y

Inserimento

Quasi sempre problemi con $2$ rossi consecutivi e in pratica ricoloro propagando la nuova colorazione.

caso1: zio del nodo appena inserito è rosso. Ricoloro di nero padre, zio e nonno (quest'ultimo solo se radice).
caso2 e caso3: lo zio del nodo è inserito si effettua una rotazione (o sinistra o destra). La riparazione va sempre effettuata sul nodo appena inserito.

Ad ogni modo la riparazione del RB tree è sempre $O(log(n))$ , così come quella di cancellazione.

RB-INSERT(T, z)
	y := T.nil // y padre del nodo considerato
	x := T.root // nodo considerato
	while x != T.nil
		y := x
		if z.key < x.key
			x := x.left
		else x := x.right
	z.p := y
	if y = T.nil
		T.root := z //l'albero T e' vuoto
	else if z.key < y.key
		y.left := z
	else y.right := z
	z.left := T.nil
	z.right := T.nil
	z.color := RED
	RB-INSERT-FIXUP(T, z)

RB-INSERT-FIXUP(T, z)
	if z = T.root
		T.root.color = BLACK
	else x := z.p // x e' il padre di z
		if x.color = RED
			if x = x.p.left // se x e' figlio sin.
				y := x.p.right // y e' fratello di x
				if y.color = RED
					x.color := BLACK // Caso 1
					y.color := BLACK // Caso 1
					x.p.color := RED // Caso 1
					RB-INSERT-FIXUP(T,x.p) // Caso 1
				else if z = x.right
					z := x // Caso 2
					LEFT-ROTATE(T, z) // Caso 2
					x := z.p // Caso 2
					x.color := BLACK // Caso 3
					x.p.color := RED // Caso 3
					RIGHT-ROTATE(T, x.p) // Caso 3
				else 
					y := x.p.left
					LEFT-ROTATE(T, y)

Eliminazione

RB-DELETE(T, z) 
	if z.left = T.nil or z.right = T.nil 
		y := z 
	else y := TREE-SUCCESSOR(z) 
	if y.left != T.nil 
		x := y.left 
	else x := y.right 
	x.p := y.p 
	if y.p = T.nil 
		T.root := x 
	else if y = y.p.left 
		y.p.left := x 
	else y.p.right := x 
	if y != z 
		z.key := y.key 
	if y.color = BLACK
		RB-DELETE-FIXUP(T,x)
	return y

RB-DELETE-FIXUP(T, x)
	if x.color = RED or x.p = T.nil 
		x.color := BLACK // Caso 0 
	else if x = x.p.left // x e' figlio sinistro 
		w := x.p.right // w e' fratello di x 
		if w.color = RED 
			w.color := BLACK // Caso 1 
			x.p.color := RED // Caso 1 
			LEFT-ROTATE(T,x.p) // Caso 1 
			w := x.p.right // Caso 1 
		
		if w.left.color = BLACK and w.right.color = BLACK
			w.color := RED // Caso 2 
			RB-DELETE-FIXUP(T,x.p) // Caso 2 
			
		else if w.right.color = BLACK 
			w.left.color := BLACK // Caso 3 
			w.color := RED // Caso 3 
			ROTATE-RIGHT(T,w) // Caso 3 
			w := x.p.right // Caso 3 
			
			w.color := x.p.color // Caso 4 
			x.p.color := BLACK // Caso 4 
			w.right.color := BLACK // Caso 4 
			ROTATE-LEFT(T,x.p) // Caso 4 
	
	else (/*come precedente else scambiando right/left*/)

La cancellazione è ancora più complicata:

caso 0: $x$ è rosso, quindi si cancella!
caso 1: $x$ è nero, con fratello $w$ rosso. Scambi i colori $w.p$ e $w$, e fai una leftRotate su $x.p$ . Ora $x$ ha un fratello $w$ nero: diventa uno tra i casi 2,3,4 .
caso 2: $x$ è nero, $x.p$ qualsiasi colore, $x$ ha un fratello $w$ nero e nipoti neri. Colori fratello $w$ di rosso e chiami la riparazione con cancellazione su $x.p$ .
caso 3: $x$ è nero, con fratello $w$ nero, e nipote destro nero ($x.p$ può essere qualsiasi colore) , scambi di colore $w$ e $w.left$ , RightRotate su $w$ -> caso 4 .
caso 4: $x$ è nero, $w$ nero, e nipote destro rosso ($x.p$ e $w.left$ possono essere qualsiasi colore). $w$ prende il colore di $w.p$ , $w.right$ diventa nero. Invoco LeftRotate su $w.p$ .

Gli RB sono strutture molto utilizzate per la gestione di alberi binari di ricerca e corrispondono ad alcune classiche implementazioni che si possono trovare nelle librerie dei linguaggi più usati tipo $Java$ o implementazione standard di $C++$.

Colorazione albero in RB

Una condizione necessaria e sufficiente perché un BST possa essere colorato in modo da diventare un albero rosso-nero è che, nell’intero albero e in ogni suo sottoalbero il rapporto tra le lunghezze minime e massime dei cammini che dalla radice raggiungono le foglie non superi mai 2 (che è anche la definizione di albero bilanciato).

Grafi, loro rappresentazione e gestione (visita in ampiezza, visita in profondità)

Struttura dati più flessibile. Elementi legati da una generica relazione. Grafi come generalizzazione di BST, RB trees, heaps, liste.

Se un grafo ha $|V|$ nodi ha al più $|V^2|$ vertici.

Grafo connesso $\rightarrow$ se esiste almeno un arco tra ogni coppia di nodi.
Grafo aciclico $\rightarrow$ grafo privo di cicli.

Possibili implementazioni:

Liste : $\Theta(|V|+|E|)$
Una lista per ogni nodo, la quale contiene tutti i nodi adiacenti al primo nodo.
Matrice $\Theta(|V|)^2$
La più semplice da implementare. Una matrice quadrata di dimensione $V$ in cui ogni elemento è 1 o 0 a seconda ci sia il rispettivo arco tra i vertici.

Confronto implementazioni:

Le liste di adiacenza sono in generale migliori quando $|E| \ne \Theta(|V|^2)$, cioè quando il grafo è sparso. Se il grafo è completo (o quasi), tanto vale usare una matrice di adiacenza... infatti usando le liste per un grafo quasi completo ($E$ dell'ordine di $V^2$) la rappresentazione diventa nell'ordine di $V^2log_2(V)$, contro $V^2$ della rappresentazione in matrice.

Visita in ampiezza (Breadth-First Search)

Complessità: $O(|V|+|E|)$

Politica FIFO (coda)
Visito tutti i nodi a distanza 1 da s (sorgente)
Quando visito un nodo u, salvo la sua distanza da s in un attributo u.dist
'Coloro' i nodi che visito (bianco se è da visitare, grigio se è già stato visitato, ma bisogna completare la visita dei nodi adiacenti, nero dopo che abbiamo visitato tutti i suoi nodi adiacenti)

I nodi da visitare sono in una coda (inizialmente solo s) e ad ogni iterazione, cancello dalla coda un elemento u e ne visito i nodi adiacenti che sono ancora bianchi (la cui distanza da s sarà u.dist+1).

L'algoritmo per poter essere eseguito necessita di array/liste di appoggio:

Lista di adiacenza, che contiene la lista dei nodi adiacenti al generico nodo.
Array stato che contiene lo stato ("visitato", "non visitato", "in corso di visita") del generico nodo.
Distanza che contiene la distanza del generico nodo dal nodo "sorgente".
Array che contiene il predecessore del nodo 'u' nell'albero BFS.
Coda che contiene i nodi "in corso di visita".

Visita in ampiezza $\rightarrow$ diventa un algoritmo di ricerca, inserendo un controllo ad ogni nuovo nodo. E’ possibile risolvere il problema di trovare il percorso più breve che conduce un nodo ad un altro. Può essere calcolato tramite una visita in ampiezza del grafo che inizia dal nodo sorgente e termina quando il nodo incontrato è quello di destinazione. La distanza si ricava tenendo traccia di quante volte si è espanso l’ orizzonte di visita nella ricerca in ampiezza.

BFS(G, s) 
	for each u in G.V – {s} 
		u.color := WHITE 
		u.dist := infinity 
		s.color := GREY 
		s.dist := 0 
		Q := empty  
		ENQUEUE(Q, s) 
	
	while Q != empty 
		u := DEQUEUE(Q) 
		for each v in u.Adj 
			if v.color = WHITE 
				v.color := GRAY 
				v.dist := u.dist +1 
				ENQUEUE(Q, v) 
		u.color := BLACK

L'algoritmo in breve:

all'inizio tutti i nodi sono bianchi, tranne la sorgente s, che è grigio
manteniamo i nodi di cui dobbiamo ancora visitare i nodi adiacenti in una coda che è gestita con politica FIFO
all'inizio la coda contiene solo s
a ogni iterazione del ciclo, eliminiamo dalla coda un elemento u, e ne visitiamo i nodi adiacenti che sono ancora bianchi (cioè che devono essere ancora visitati)
Si noti che, se u.dist è la distanza del nodo u da s, la distanza dei nodi bianchi adiacenti ad u è u.dist+1

Visita in profondità (Depth-First Search)

Complessità: $\Theta(|V | + |E|)$ (occhio al $\Theta$)

Usa una politica LIFO (stack)
Tiene traccia di quando un nodo è aggiunto alla pila ($u.d$) e di quando viene tolto ($u.f$)

La visita di un grafo in profondità corrisponde a visitare i nodi incontrati percorrendo un cammino (il più lungo possibile) che a partire da un nodo di partenza arriva in un nodo avente tutti i nodi ad esso adiacenti già visitati. A questo punto si risale il cammino fino al primo nodo che possiede un vertice adiacente non visitato e si ricomincia il processo di visita con lo stesso criterio. Una implementazione ricorsiva di tale metodo è diretta.

DFS(G) 
	for each u in G.V 
		u.color := WHITE 
		time := 0 
	
	for each u in G.V 
		if u.color = WHITE 
			DFS-VISIT(u)

DFS-VISIT(u) 
	u.color := GRAY 
	time := time + 1 
	u.d := time 
	for each v in u.Adj 
		if v.color = WHITE 
			DFS-VISIT(v) 
	
	u.color := BLACK 
	time := time + 1 
	u.f := time

Ordinamento Topologico

Dato in input un DAG (directed acyclic graph) un ordinamento topologico è una lista che rappresenta l'ordine delle connessioni. In particolare, l'ordinamento lineare dei nodi del grafo è tale che se nel DAG c’è un arco $(u, v)$, allora il nodo $u$ precede $v$ nell’ordinamento. L’ordinamento ottenuto rispetta la precedenza tra nodi. C'è stato un tema d'esame un anno nel quale si richiedeva l'ordinamento topologico di un grafo che rappresentava dipendenze di programmi tra loro: un programma C poteva essere eseguito solo dopo la fine del programma C ... e così via.

{width=50%}

L'idea per l'algoritmo si basa su DFS:

Visito il DAG con un algoritmo DFS
Quando coloro un nodo $u$ di nero, inserisco $u$ in testa alla lista
Una volta visitati tutti i nodi, ottengo un ordinamento topologico

Ha la stessa complessità di DFS, cioè $$TTS = O(|V | + |E|)$$

TOPOLOGICAL-SORT(G): 
	L := NIL 
	for u in G.V 
		u.color := WHITE 
	for u in G.V 
		if u.color = WHITE 
			TOPSORT-VISIT(L, u) 
	return L

TOPSORT-VISIT(L, u) 
	u.color := GRAY 
	for v in u.Adj 
		if v.color = WHITE 
		TOPSORT-VISIT(L, v) 
	crea l'elemento di lista x 
	x.key := u 
	LIST-INSERT(L, x) 
	u.color := BLACK

Rilassamento di un lato

Se $d[v] > d[u]+w(u,v)$ allora $d[v] := d[u]+w(u,v)$ e $Predecessore[v] := u$ . Cioè ci accorgiamo che il costo per raggiungere $v$ è minore se lo raggiungiamo attraverso $u$ .

Bellman-Ford

Rilasso un passo alla volta partendo da s
Ad ogni passo avanzo nei cammini
Al $|V|-1$-esimo passo sicuramente avrò toccato tutti i nodi raggiungibili
non converge se ci sono cicli negativi

BELLMAN-FORD(adj, s) { 
	V := vettore dei nodi di adj 
	// dopo allocazione d e Pi si inizializza
	for i:=0 to adj.length-1 
		d[i]:= infinity; 
		Pi[i]:=NIL  //predecessore/parent
	d[s]:=0 
	
	for i:=1 to adj.length-1 // ripete |V|-1 volte
		for each u in V 
			for each v in adj[u] 
				RELAX(u, v, adj, d, Pi) 
	
	return (d, Pi) }

dove RELAX è proprio il rilassamento di un lato.

RELAX(u, v, adj, d, Pi) 
if d[v] > d[u] + adj[u][v] 
	d[v] := d[u] + adj[u][v] 
	Pi[v] := u

Algoritmo di Floyd

Dato un grafo orientato, per cui ogni nodo ha un solo successore dato un nodo di partenza si determina se esiste un ciclo. Idea: usiamo due riferimenti $t$ e $l$ (tartarughina e leprotto) che spostiamo a ogni passo, il leprotto ciclando incontrerà la tartarughina che va più lenta. Chiamiamo $C$ la lunghezza del ciclo e $T$ quella della “pista” che lo precede.

FloydLT(G,x)
t <- x.succ
l <- x.succ.succ 

while l != t
	t <- t.succ
	l <- l.succ.succ

T <- 0 
t <- x 

while l != t
	t <- t.succ
	l <- l.succ
	T++

C <- 0 
l <- t  //forse dovrebbe essere t.succ ? 

while l != t 
	l <- l.succ
	C++

return T,C

La complessità temporale: $\Theta(T + C - r + T + C) = \Theta(2(T + C) - r)$ mentre la spaziale: $\Theta(1)$ .

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

12.Alberi e grafi.md

12.Alberi e grafi.md

Alberi e grafi

Heap

Implementazione Heap Binari

Max Heapify e complessità

BT - Binary Tree

BST - Binary Search Tree

Complessità BST

Attraversamento simmetrico

Ricerche

Minimo (foglia più a sinistra)

Massimo (foglia più a destra)

Successore e Predecessore

Operazioni su BST

Inserimento

Eliminazione

Possibile implementazione di Binary Trees

Fusione di due alberi binari di ricerca in uno bilanciato

Alberi rosso-neri

Operazioni su RB trees

Inserimento

Eliminazione

Colorazione albero in RB

Grafi, loro rappresentazione e gestione (visita in ampiezza, visita in profondità)

Confronto implementazioni:

Visita in ampiezza (Breadth-First Search)

Visita in profondità (Depth-First Search)

Ordinamento Topologico

Rilassamento di un lato

Bellman-Ford

Algoritmo di Floyd

Files

12.Alberi e grafi.md

Latest commit

History

12.Alberi e grafi.md

File metadata and controls

Alberi e grafi

Heap

Implementazione Heap Binari

Max Heapify e complessità

BT - Binary Tree

BST - Binary Search Tree

Complessità BST

Attraversamento simmetrico

Ricerche

Minimo (foglia più a sinistra)

Massimo (foglia più a destra)

Successore e Predecessore

Operazioni su BST

Inserimento

Eliminazione

Possibile implementazione di Binary Trees

Fusione di due alberi binari di ricerca in uno bilanciato

Alberi rosso-neri

Operazioni su RB trees

Inserimento

Eliminazione

Colorazione albero in RB

Grafi, loro rappresentazione e gestione (visita in ampiezza, visita in profondità)

Confronto implementazioni:

Visita in ampiezza (Breadth-First Search)

Visita in profondità (Depth-First Search)

Ordinamento Topologico

Rilassamento di un lato

Bellman-Ford

Algoritmo di Floyd