Discussioni su argomenti di Informatica
09/01/2006, 16:44
Ciao a tutti, vi propongo questa domanda di Algoritmi e Strutture dati.
Si proponga un algoritmo efficiente per estrarre il secondo elemento più piccolo da un RB-albero. Non sono ammessi campi aggiuntivi.
Un algoritmo simile secondo voi è sensato? (Lo scrivo in pseudo codice con commenti).
RB-SECMINIMUM(T,x) \\Come parametri prende un RB-albero T, e il puntatore x alla radice
while LEFT[x] div NIL \\Div sta per diverso
x = LEFT[x]
y = P[LEFT[x]] \\Questo è il secondo elemento più piccolo (il padre di left[x])
RB_DELETE(T,y) \\ Algoritmo per cancellare il nodo e risistemare le proprietà degli RB-alberi
RETURN(y)
Che dite?
PS: Purtroppo non riesco ad allineare correttamente il codice, comunque la procedura RB_DELETE e il return sono esterni al ciclo while.
09/01/2006, 19:58
Hey Enigma!tutto bene?:)
ora sono di fretta..gli do un'occhio dopo..
vediamo se mi ricordo qlc..se non sbaglio la struttura degli alberi è simile a quella di una lista dinamica (pila,coda)..??
avevo fatto qlc per Info A
Ciao!
Marvin
10/01/2006, 08:10
Ciao... si e tu?
Si, come dici tu è una struttura dati dinamica.
10/01/2006, 14:34
Allora..prova a vedere sul mio disco remoto
http://mio.discoremoto.virgilio.it/marvin_public/
ti ho messo un pdf...
prova a vedere un po'
se non te lo apre chiamami in msn..
Marvin
12/01/2006, 18:39
Ciao, sono un nuovo arrivato! se un RB è un BST ...Binary Search Tree...
ti propongo questo algoritmo! Lo scrivo utilizzando...circa la sintassi dell'Ada, ma non ci vuole niente a scriverlo in C, C++...in qualsiasi linguaggio tu voglia:D
Supponiamo una struttura di tipo Albero con due puntatori, destra e sinistra per i due figli.
Il secondo elemento più piccolo è il successore dell'elemento più piccolo. L'elemento più piccolo è tutto a sinistra, il suo successore è il figlio destro , e se non ne ha è il padre.
function secondo_elemento(A:Albero) return Albero is
begin
if A=null then
return null;
elsif A.sinistra.sinistra=null then
return Max(A.sinistra.destra, A )
else
return secondo_elemento(A.Sinistra)
end if;
end function;
12/01/2006, 19:49
No io come RB intendo un Albero Rosso-Nero.
Marvin grazie mille del pdf, ci sto' dando un'occhiata!
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.