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

di
dverrastro
il
3 risposte
D
dverrastro
Pochi posts
Iscritto da
giu, 2016
Messaggi:
4

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

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. Spero che qualcuno sia così gentile da aiutarmi. Grazie in anticipo

3 Risposte

  • M.A.W. 1968
    M.A.W. 1968
    Utente Attivo
    Iscritto da
    ott, 2011
    Messaggi:
    321

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

    In generale riteniamo ben poco etico rispondere a simili richieste: a maggior ragione quando replicate su numerosi forum, come in questo caso.

    L'unica indicazione concreta che si possa seriamente fornire è quella di cercare la risposta in un buon manuale di algoritmica.
  • D
    dverrastro
    Pochi posts
    Iscritto da
    giu, 2016
    Messaggi:
    4

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

    Mi dispiace ma purtroppo sono in crisi e ho agito in questa maniera sperando che qualcuno abbia la pazienza di aiutarmi
  • D
    dverrastro
    Pochi posts
    Iscritto da
    giu, 2016
    Messaggi:
    4

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

    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?
Devi accedere o registrarti per scrivere nel forum
3 risposte