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

di il
3 risposte

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

  • 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.
  • 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
  • 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