Precedente :: Successivo |
Autore |
Messaggio |
dverrastro Comune mortale
Registrato: 22/06/16 19:12 Messaggi: 4
|
Inviato: 22 Giu 2016 20:05 Oggetto: Trasformazione da Albero 2-3 a B-Albero e viceversa e da Alb |
|
|
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 |
|
Top |
|
|
dverrastro Comune mortale
Registrato: 22/06/16 19:12 Messaggi: 4
|
Inviato: 26 Giu 2016 10:36 Oggetto: |
|
|
Ho provato a scrivere qualcosa
Da 2-3 a B-Albero:
Codice: | 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
Codice: | 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? |
|
Top |
|
|
|
|
Non puoi inserire nuovi argomenti Non puoi rispondere a nessun argomento Non puoi modificare i tuoi messaggi Non puoi cancellare i tuoi messaggi Non puoi votare nei sondaggi
|
|