Tra tutti gli alberi di copertura, quello il cui costo è minimo.
In un grafo con tutti archi di costo diverso, l'MST è unico, ma può essere radicato in tanti modi quanti sono i vertici
title: Regola Blue
Considerato un taglio S: $V = V_1 \cup V_2, V_1 \cap V_2 = \emptyset$
$$S = \{e = (l,r) : l \in V_1, r \in V_2\}$$
Si applica se S non ha archi blue, colora di blue l'arco di costo minimo in S
title: Regola Rossa
Considera un ciclo $C$.
Si applica se $C$ non ha archi rossi, colora di rosso l'arco di peso massimo in $C$
Soddisfa il seguente invariante dopo ogni scelta:
while exists e in E not colored:
applica la regola blue o rossa
return MST = {e : color(e) = blue}
- ordino gli archi in senso crescente rispetto
$w(e)$ in L: - Foresta di alberi costituiti da un solo vertice
Visita tutti gli archi in L e per ogni arco procede come segue:
- se
$v_1$ e$v_2$ non appartengono allo stesso albero della foresta -> coloro$e$ di blue$$MST = MST \cup e=(v_1,v_2)$$ - se
$v_1$ e$v_2$ appartengono allo stesso albero -> coloro$e$ di rosso e lo escludo dal MST
test(v1, v2): //appartengono allo stesso albero
dfs-visit(v1):
verifico se v2 è raggiungibile da v1
mantengo un insieme per ogni albero della foresta
union(Sa, Sb) fonde i due insiemi Sa e Sb
find(vi) ritorna l'insieme in cui si trova vi
kruskal(G = (V, E); w):
L = archi ordinati
MST = empty
Crea |V| insiemi, un insieme per ciascun vertice
for e = (vi, vj) nell'ordine L:
if find(vi) == find(vj):
e = (vi, vj) rosso
else
union(find(vi), find(vj))
MST = MST + {vi, vj}
Ordinamento :
Union:
Find:
La complessità ultima dipende dalla struttura dati che rappresenta gli insiemi
RELAX di Prim è diverso da quello di [[a2. Grafi pesati#Relax|Dijkstra]]
relax(u, v, w(u, v)):
if d(v) > w(u, v):
d(v) = w(u, v)
P(v) = u
Per tutto il resto l'algoritmo di Prim è lo stesso dell' [[a2. Grafi pesati#Dijkstra|algoritmo di Dijkstra]]
prim(G = (V, E), w: E -> R):
INITIALIZE
Q = {d(v) : for v in V}
sol = empty
while Q not empty:
u = extract-min(Q)
sol = sol + u
for v in Adj(u) and v not in sol:
relax (u, v, w(u, v))
title: Come posso trasformare i pesi negativi in pesi non negativi e mantenere le posizioni
I pesi degli archi possono trasformarsi sempre in pesi non negativi usando la regola
$$\hat w(e) = w(e) + |min(w(e)) : w(e) < 0|$$
Dopo la trasformazione MST è lo stesso, il peso del problema originale è lo stesso del problema modificato
Rappresentiamo un albero binario come una linked list i cui nodi sono gli oggetti della lista, ogni oggetto ha una chiave univoca e dei puntatori che indicano gli oggetti vicini.
Dato un albero T, la sua radice ($T.root$) ha padre $x.p = NIL$.
I figli a sinistra e a destra sono rappresentati dagli attributi $left$ e $right$, se non hanno figli l'attributo è $NIL$.
![[binarytree.png|center]]
Per gli alberi con
![[binarytree2.png|center]]
Ogni nodo è connesso al suo parent
In un albero binario di ricerca le chiavi sono sempre memorizzate in modo da soddisfare una proprietà:
Dato $x$ nodo in un albero binario di ricerca:
- se $y$ è un nodo nel sottoalbero a __sinistra__ di $x$ allora $y.key \leq x.key$
- se $y$ è un nodo nel sottoalbero a __destra__ di $x$ allora $y.key \geq x.key$
![[binarytree3.png|center]]
Grazie a questa proprietà possiamo stampare tutte le chiavi in modo ordinato semplicemente tramite algoritmo ricorsivo
INORDER-TREE-WALK(x):
if x not NIL:
INORDER-TREE-WALK(x.left)
print x.key
INORDER-TREE-WALK(x.right)
esistono anche algoritmi chiamati preorder-tree-walk che stampa la radice prima dei valori dei suoi sottoalberi, e postorder-tree-walk che stampa la radice dopo i valori dei suoi sottoalberi
Tree-search(x, k):
if x == NIL or k == x.key:
return x
elseif k < x.key:
return Tree-search(x.left, k)
else:
return Tree-search(x.right, k)
Iterative-tree-search(x k):
while x not NIL and k not x.key:
if k < x.key:
x = x.left
else:
x = x.right
return x
Tree-minimum(x):
while x.left not NIL:
x = x.left
return x
Tree-maximum(x):
while x.right not NIL:
x = x.right
return x
Tree-successor(x):
if x.right not NIL:
return Tree-minimum(x.right)
else:
y = x.p
while y not NIL and x == y.right:
x = y
y = y.p
return y
Tree-predecessor è simmetrico a Tree-successor.
Queste operazioni cambiano la rappresentazione dell'albero.
Tree-insert(T, z):
x = T.root
y = NIL
while x not NIL:
y = x
if z.key < x.key:
x = x.left
else:
x = x.right
z.p = y
if y == NIL:
T.root = z
elseif z.key < y.key:
y.left = z
else:
y.right = z
Transplant(T, u, v):
if u.p == NIL:
T.root = v
elseif u == u.p.left;
u.p.left = v
else:
u.p.right = v
if v not NIL:
v.p = u.p
Tree-delete(T, z):
if z.left == NIL:
transplant(T, z, z.right)
elseif z.right == NIL:
Transplant(T, z, z.keft)
else:
y = Tree-minimum(z.right)
if y not z.right:
Transplant(T, y, y.right)
y.right = z.right
y.right.p = y
Transplant(T, z, y)
y.left = z.left
y.left.p = y
^6d280d
La ricerca di un albero binario è efficiente se la dimensione è piccola, altrimenti non è più veloce delle linked list. Gli alberi rosso-neri sono uno dei tanti schemi "bilanciati" per garantire un'eseccuzione in tempo
Un albero rosso-nero è un albero binario di ricerca con un bit extra per memorizzare il suo __colore__, l'albero è approssimativamente bilanciato e la sua altezza con $n$ nodi è al più $2\log(n+1)$ che è $O(\log n)$
Questi alberi rispettano le seguenti proprietà:
- Ogni nodo è rosso o nero
- La root è nera
- Ogni foglia (NIL) è nera
- Se un nodo è rosso, allora entrambi i suoi figli sono neri
- Per ogni nodo, tutti i percorsi semplici dal nodo alle foglie discendenti contengono lo stesso numero di nodi neri
Per rappresentare NIL si usa un nodo a parte (T.NIL) di colore nero.
Dato che l'altezza dell'albero è $O(\log n)$ allora anche le operazioni sugli alberi binari impiegano al più $O(\log n)$.
Dato che queste operazioni modificano la struttura dell'albero, potrebbero invalidare le 5 proprietà
Per ristabilire le proprietà che vengono modificate, i colori e i puntatori devono cambiare. Per cambiare i puntatori si utilizza la rotazione che può essere a sinistra o a destra.
![[rotation.png|center]]
Per inserire un nodo in un albero rosso-nero mantenendo le proprietà bisogna modificare [[#^6d280d|Tree-insert]]
RB-insert(T, z):
x = T.root
y = T.NIL
while x not 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
elseif 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)
Ci sono 4 differenze tra i 2 algoritmi:
- Tutte le istanze di NIL sono rimpiazzate da T.NIL
- Per mantenere la struttura corretta
$z.left$ e$z.right$ diventano T.NIL - z viene colorato di rosso
- Dato che colorando di rosso z si potrebbe generare una violazione delle proprietà, viene chiamato RB-INSERT-FIXUP per ripristinare le proprietà rosso-nere
Descrivendo la stuttura di un albero rosso-nero bisogna riferirsi spesso al fratello di un nodo genitore (nodo zio).
title: Quali violazioni delle proprietà possono verificarsi al chiamare di RB-INSERT-FIXUP?
le proprietà che possono essere violate sono 2:
2. La radice deve essere di colore nero
4. Un nodo rosso non può avere un figlio rosso
Sia
![[rn-caso1.png|center]]
Lo zio di
Lo zio di
![[rn-caso23.png|center]]
![[esempio_rn.png|center]]