Ordinamento Albero vs Array

[Giova411]

Propongo un esercizietto.
Io penso d'averlo risolto in tempo lineare e vorrei confrontarmi con qualcuno per fare esercizio.

Abbiamo un albero di ricerca B ed un array ordinato A. Entrambi contengono n/2 elementi. Vogliamo ottenere una lista ordinata degli elementi contenuti in A ed in B.

[Giova411]

TREE min(TREE t)
 while t.left() != nil do
   t <-- t.left()
 return t
-- * --

TREE succerssorNode(TREE t)
 if t= nil then return t
 if t.right != nil then return min(t.right)
 TREE p <-- t.parent
 while p != nil and t=p.right do
   t <-- p
   p <-- p.parent
 return p
-- * --

ARRAYLIST Creaarray(TREE b, ARRAYLIST B)
  if b = nil then return B
  if b != nil then
   TREE u <-- min(b)
    while u != nil do
      B.insert(u)
      u <-- successorNode(u)
 return B
-- * --

LIST FondiAlberoArray(TREE b, ARRAYLIST A)
 ARRAYLIST B <-- new ARRAYLIST
 B <-- Creaarray(b, B) 
 LIST D <-- new LIST
 integer i,j,k 
 i=j=k=1
 while i<B.size() AND j< A.size() do
   if (B[i]<A[j]) then D[k++]= B[i++]
   else D[k++]=A[j++]
 while (i<B.size()) do
   D[k++]=B[i++]
 while (j<A.size())
   D[k++]=A[j++]
 return D

Ovviamente, come avrete capito, non sono MAI sicuro della soluzione.
Se qualcuno batte un colpo meglio per tutti

E GRAZIE!!!!

ERRORI A' GOGO'
Ho visto dopo le castronate con elementi di tipo LIST...
Ho modificato all'ultimo poiché avevo, per semplicità, usato ARRAY[]

[apatriarca]

Considerando che la visita di tutti i nodi di un albero di ricerca si può fare in tempo lineare e che il merge tra due successioni ordinate si può anch'esso fare in tempo lineare direi che è abbastanza semplice vedere come sia possibile fare l'intera operazione in tempo lineare.

[Giova411]

Apa l'idea mia è visitare in ordine l'albero e memorizzare in un array i valori. Poi facciamo un merge tra due vettori raddoppiando la dimensione. Però ho un po' di difficoltà col codice... Che ne pensi?

 
integer i,j,k
 i=j=k=1
 while i<B.size() AND j< A.size() do
   if (B[i]<A[j]) then D[k++]= B[i++]
   else D[k++]=A[j++]
 while (i<B.size()) do
   D[k++]=B[i++]
 while (j<A.size())
   D[k++]=A[j++]

questo forse potevo scriverlo:
Merge(A,B)?

[onlyReferee]

Ciao Giova411
Piccola variazione: giustissima l'idea di memorizzare in un array i valori presenti nei nodi nell'albero. Puoi però memorizzare questi ultimi e quelli dell'altro array ordinato direttamente in un unico array di dimensione $n$. Successivamente richiami la procedura merge dell'algoritmo mergesort e sei a posto.

[Giova411]

LIST Creaarray(TREE b, LIST B)
  if b = nil then return B
  if b != nil then
   TREE u <-- min(b)
    while u != nil do
      B.insert(B.next(B.tail()), u)
      u <-- successorNode(u)  
 return B
-- ^ --
LIST FondiAlberoArray(TREE b, ARRAY[] A, integer size)
 LIST B <-- new LIST[1..size]
 B <-- Creaarray(b, B)
 LIST C <-- new LIST[1..size]
 integer i <-- 1
 while i<=size do
   C.insert(C.next(C.tail()), A[i])
   i++
 size = size * 2
 LIST D <-- new LIST[1..size]
 D = Merge(C,B)
 return D

Non sono sicuro con gli inserimenti in LIST << B.insert(B.next(B.tail()), u)>> e <)>>
Quindi <> mi risolve in O(n) come noto e si presuppone che faccia la fusione corretta come in MergeSort?
Nelle restanti parti rimango sempre con complessita lineare se non sbaglio. Allora Apa mi ha confermato che si puo' fare tutto in O(n) (direi anche "teta di enne" visto che minimo tutti gli n li devo vedere)
Only il codice tu lo riesci a fare più snello ed elegante?

Siete Grandi ragazzi!!! =)

[onlyReferee]

Ciao Giova411
Ti riposto qui di seguito i commenti alle modifiche più il tuo codice modificato. Per quanto riguarda Creaarray l'istruzione

if b = nil then return B

è inutile (banalmente fai un controllo subito dopo che, se falso ritorna direttamente $B$). Poi, nell'insert in teoria se passi semplicemente $B$ ed $u$ ti inserisce l'elemento $u$ in coda ed a noi sta bene dato che eseguiamo una visita degli elementi già ordinati. Qua però dovrei sapere come è implementato questo metodo per essere sicuro.
Non ho capito inoltre francamente perché passi $B$ alla procedura se poi glielo ritorni... Basta che ti crei la lista all'interno e poi una volta che ci hai inserito i nodi la ritorni. Piuttosto è più utile passare size, la dimensione della lista che vuoi ti venga ritornata nel caso tu voglia allocare subito lo spazio per la stessa.
Passiamo a FondiAlberoArray.
Qui te ne basta una sola di lista, in cui poi ci vai ad inserire i nodi di volta in volta. La lista è utile perché anche per aggiungere nuovi elementi non hai problemi di dimensione prefissata come nel caso degli array. Difatti non ho ben compreso come mai quando dichiari la lista ne preallochi anche lo spazio necessario... Infine nella versione standard della procedura merge alla stessa bisogna passare nell'ordine l'array (lista) da ordinare e nell'ordine left, center e right che denotano rispettivamente gli indici degli elementi sinistro, mediano e destro delimitanti le due sequenze da fondere. Trattandosi di pseudocodice (almeno da come ho capito) gli indici degli array qui li ho assunti da $1$ (primo elemento) a size (ultimo elemento).

LIST Creaarray(TREE b, integer size)
  LIST B <-- new LIST[1..size]
  if b != nil then
   TREE u <-- min(b)
    while u != nil do
      B.insert(B.tail(), u)
      u <-- successorNode(u)  
 return B
-- ^ --
LIST FondiAlberoArray(TREE b, ARRAY[] A, integer size)
 TotSize <-- size * 2
 LIST B <-- new LIST[1..TotSize]
 B <-- Creaarray(b, size)
 integer i <-- 1
 while i<=size do
   B.insert(B.tail(), A[i])
   i++
 Merge(B, 1, size, TotSize)
 return B

Parliamo della complessità...
Ora, poiché la complessità della procedura Creaarray è $\Theta(n / 2)$ e quella di FondiAlberoArray è $\Theta(n / 2) + \Theta(n / 2) + \Theta(n)$ (dove l'ultima di queste tre complessità è quella di merge) allora abbiamo una complessità totale pari a $\Theta(n)$.

[Giova411]

Grazie Only!
Solo che non ho capito, in FondiAlberoArray sovrascrivi nella lista B dopo che l'hai rimpita, con Creaarray, fino a size?
Ecco poi che non capisco benissimo il Merge del solo B. (Capito che usi alla lettera quello di MergeSort, io ne avevo fantasticato uno fittizio )
Usi il fatto che da 1 a metà hai una parte ordinata e da metà fino alla fine un'altra parte ordinata?

B = Merge(B, 1, size, TotSize)

Hai ragione che non ho specificato l'insert!
Nelle LIST insert prevede due parametri: posizione p e elemento da inserire:

POS insert(POS p, ITEM v)

Deve POS è equivalente al tipo LIST per semplicità.
Da qui il dubbio di come inserire!!!!
Infatti avevo scritto

B.insert(B.next(B.tail()), u)

poiché volevo tenere l'ordine dato dell'albero che è ordinato: mantengo lo stesso ordine che avevo nell'albero poiché inserisco un NUOVO elemento in FONDO alla lista.

[onlyReferee]

"Giova411":Grazie Only!
Solo che non ho capito, in FondiAlberoArray sovrascrivi nella lista B dopo che l'hai rimpita, con Creaarray, fino a size?
[...]

Sì, perché so già che l'albero ha dimensione size come l'array di partenza. Gliela passo in input alla funzione soltanto perché così so già il numero degli elementi (difatti se vedi poi nella funzione Creaarray la utilizzo).

"Giova411":
[...]
Ecco poi che non capisco benissimo il Merge del solo B. (Capito che usi alla lettera quello di MergeSort, io ne avevo fantasticato uno fittizio )
Usi il fatto che da 1 a metà hai una parte ordinata e da metà fino alla fine un'altra parte ordinata?
[...]

Esatto, per la precisione il codice lo trovi qui. Ora il $B$ mi contiene tutti gli elementi che devo ordinare ed appunto la prima metà e la seconda so già che sono ordinate. E' sufficiente solo fondere assieme (da cui "merge") le due parti.

"Giova411":
[...]
Hai ragione che non ho specificato l'insert!
Nelle LIST insert prevede due parametri: posizione p e elemento da inserire:

POS insert(POS p, ITEM v)

Deve POS è equivalente al tipo LIST per semplicità.
Da qui il dubbio di come inserire!!!!
Infatti avevo scritto

B.insert(B.next(B.tail()), u)

poiché volevo tenere l'ordine dato dell'albero che è ordinato: mantengo lo stesso ordine che avevo nell'albero poiché inserisco un NUOVO elemento in FONDO alla lista.

Trovi nel mio post precedente il codice modificato. Per inserirlo in fondo alla lista però dovresti teoricamente scrivere come ho fatto io. In teoria scrivere B.next(B.tail()) equivale a denotare una lista vuota poiché l'ultimo elemento chiaramente punta a nil.

[Giova411]

ESAUSTIVO ONLY
GRAZIE DAVVERO