PDA

Visualizza la versione completa : Trasformazione da Albero 2-3 a B-Albero e viceversa e da Albero RB ad Albero 2-3


dverrastro
22-06-2016, 21:09
Salve a tutti, avrei bisogno che qualcuno mi fornisca 4 algoritmi che permettano di passare:

1) Da Albero 2-3 a B-Albero;
2) Da B-Albero (grado minimo 2) ad Albero 2-3;
3) Da Albero RB ad Albero 2-3;
4) Da Albero 2-3 ad Albero RB;

Ho bisogno di algoritmi generici, non devono essere scritti in un linguaggio particolare. Non vorrei chiedere la cosiddetta "pappa pronta" ma purtroppo non ho il tempo di ragionarci su. Spero che qualcuno sia cos´┐Ż gentile da aiutarmi. Grazie in anticipo :)

dverrastro
26-06-2016, 11:38
Ho provato a scrivere qualcosa


Da 2-3 a B-Albero:



SplitChild(x,y,A)
if key1[y] < x
min = key1[y]
else
min = x
if key2[y] > x
max = key2[y]
else
max = x
if max = x
mid = key2[y]
else if min = x
mid = key1[y]
else
mid = x
z = "nuovo nodo"
key1[z] = mid
left[z] = min
right[z] = max
if n[pi[y]] = 1
"sostituisci y con z"
if n[pi[y]] = 2
SplitChild(mid,pi[y],A)




Da RossoNero a B-Albero



Trasforma(T)
Alloca A23[A]
Alloca N23[z]
key1[x] = key[root[T]]
root[A] = x
IdentificaFigli[root[A],root[T]]


IdentificaFigli[a,t]
if color[left[t]] = red
TrasformaRB[a,t]
else if color[left[t]] = black
TrasformaBB[a,t]


TrasformaRB[a,t]
Alloca N23
key2[a] = key1[a]
key1[a] = key[left[t]]
key1[x] = key[right[t]]
right[a] = x
pi[x] = a
IdentificaFigli[a,left[t]]
IdentificaFigli[right[a],right[t]


TrasformaBB[a,t]
Alloca N23[z]
Alloca N23[y]
key1[z] = key[left[t]]
key1[y] = key[right[t]]
left[a] = x
pi[x] = a
if color[t] = red
middle[a] = y
pi[y] = a
else if color[t] = black
right[a] = y
pi[y] = a



Possono funzionare?

Loading