Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
Trasformazione da Albero 2-3 a B-Albero e viceversa e da Alb
Nuovo argomento   Rispondi    Indice del forum -> Programmazione
Precedente :: Successivo  
Autore Messaggio
dverrastro
Comune mortale
Comune mortale


Registrato: 22/06/16 19:12
Messaggi: 4

MessaggioInviato: 22 Giu 2016 20:05    Oggetto: Trasformazione da Albero 2-3 a B-Albero e viceversa e da Alb Rispondi citando

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 Smile
Top
Profilo Invia messaggio privato
dverrastro
Comune mortale
Comune mortale


Registrato: 22/06/16 19:12
Messaggi: 4

MessaggioInviato: 26 Giu 2016 10:36    Oggetto: Rispondi

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
Profilo Invia messaggio privato
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Programmazione Tutti i fusi orari sono GMT + 1 ora
Pagina 1 di 1

 
Vai a:  
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