RB-Alberi

[enigmagame]

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.

[Marvin]

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

[enigmagame]

Ciao... si e tu?
Si, come dici tu è una struttura dati dinamica.

[Marvin]

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

[ilprincipe1984]

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;

[enigmagame]

No io come RB intendo un Albero Rosso-Nero.
Marvin grazie mille del pdf, ci sto' dando un'occhiata!