Trasformazione da Albero 2-3 a B-Albero e viceversa e da Albero RB ad Albero 2-3

[dverrastro]

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

 

[Mursey]

Solitamente qui non si risolvono i problemi direttamente ma lo si fa insieme discutendo, però chiudo un occhio e aspettiamo e vediamo se trovi una anima buona che ti dà una mano...

 

[dverrastro]

Ti ringrazio. Di solito non chiedo la risoluzione di problemi su internet ma stavolta sono veramente in difficoltà

 

[dverrastro]

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?